Linux 정렬 유틸리티를 사용하여 고정 바이트 오프셋으로 이진 키-값 쌍을 정렬하는 방법은 무엇입니까?

Linux 정렬 유틸리티를 사용하여 고정 바이트 오프셋으로 이진 키-값 쌍을 정렬하는 방법은 무엇입니까?

20GB를 정렬하고 싶어요바이너리30바이트 키와 20바이트 값이 연속적으로 배치된 파일입니다.모든 것이 한 줄에 있습니다.정렬에서 비교를 위해 사용해야 하는 키 길이와 레코드 크기를 지정하고 싶습니다. 이렇게 하면 키가 움직일 때 키와 관련된 값도 움직입니다.

이상적으로는 어떤 방식으로든 파일을 수정하고 싶지 않습니다(예: 키와 값 사이에 구분 기호 추가). 파일은 KVKVKVKVKVKV한 줄의 이진 파일처럼 보입니다.

20GB 파일의 첫 번째 200B에 대한 Hexdump:

# hexdump -n 200 -C 20gbUnsorted
00000000  54 65 73 74 69 6E 67 31  32 33 65 08 00 60 83 6b  |Testing123e..`.k|
00000010  39 2c d5 8b 8f 5e 55 96  18 55 e7 9b 87 f0 22 83  |9,...^U..U....".|
00000020  a4 66 b6 aa b1 f9 e0 ca  cf 1e 26 b3 29 2a fd 10  |.f........&.)*..|
00000030  64 bb 18 b5 6a c0 7d 6f  65 6b 1d 2f 43 0d 57 bd  |d...j.}oek./C.W.|
00000040  e7 e4 7d 81 f3 6a 6d d2  67 94 8b bc 23 97 bf e2  |..}..jm.g...#...|
00000050  8c 33 4e 4a d8 2b 8e 70  16 62 93 cf aa 01 16 bf  |.3NJ.+.p.b......|
00000060  da 3b b1 ab 95 e0 e4 82  62 b3 ed fe 04 47 b5 7f  |.;......b....G..|
00000070  77 b1 3a 35 87 fb e7 90  42 e3 c4 06 d6 8e 9f d2  |w.:5....B.......|
00000080  c7 f3 f6 39 0d 9d 0d ce  13 fb 83 42 e1 52 81 2e  |...9.......B.R..|
00000090  99 4b 4b 40 3a 16 7a 2a  7c 93 c3 84 1d e1 93 0a  |.KK@:.z*|.......|
000000a0  0d b2 07 f4 eb 9e 04 b5  9e d8 77 d9 a1 a0 67 a1  |..........w...g.|
000000b0  01 fa 8d 8d 4c 04 5b ee  a3 00 6f b4 20 50 a4 e6  |....L.[...o. P..|
000000c0  5b b3 cc 40 83 eb b2 ad                           |[..@....|
000000c8

저는 리눅스를 사용하고 있습니다.

답변1

보기 흉하지만 제대로 작동합니다.

hexdump -v -e '50/1 "%02x " "\n"' file.bin | sort | xxd -p -r > file-sorted.bin

hexdump행당 50바이트씩 그룹화하고 해당 sort행에 대해 일반 작업을 수행한 다음 xxd -r.

처음 30바이트만 정렬하는 데에는 신경 쓰지 않습니다. 왜냐하면 동일하면 순서가 공개되고 계속해서 값별로 정렬하기로 선택하기 때문입니다.

답변2

IMO에서는 바이너리 파일을 쉽게 읽고 쓸 수 있는 프로그래밍 언어로 관리하는 것이 더 쉽습니다. (난해한) 예를 들어, Tcl:

tclsh <<'END_TCL'
    set fh [open file.bin rb]
    while {true} {
        set kv [read $fh 50]
        if {[string length $kv] != 50} break
        lappend kvs $kv
    }
    close $fh

    set fh [open file_sorted.bin wb]
    foreach kv [lsort $kvs] {puts -nonewline $fh $kv}
    close $fh
END_TCL

입력 파일은 다음과 같습니다.

$ ls -l file.bin
-rw-r--r-- 1 glennj glennj 200 Apr 20 16:07 file.bin

$ od -c -w50 file.bin
0000000   T   e   s   t   i   n   g   1   2   3   e  \b  \0   ` 203   k   9   ,   � 213 217   ^   U 226 030   U   � 233 207   �   " 203   �   f   �   �   �   �   �   �   � 036   &   �   )   *   � 020   d   �
0000062 030   �   j   �   }   o   e   k 035   /   C  \r   W   �   �   �   } 201   �   j   m   �   g 224 213   �   # 227   �   � 214   3   N   J   �   + 216   p 026   b 223   �   � 001 026   �   �   ;   �   �
0000144 225   �   � 202   b   �   �   � 004   G   � 177   w   �   :   5 207   �   � 220   B   �   � 006   � 216 237   �   �   �   �   9  \r 235  \r   � 023   � 203   B   �   R 201   . 231   K   K   @   : 026
0000226   z   *   | 223   � 204 035   � 223  \n  \r   �  \a   �   � 236 004   � 236   �   w   �   �   �   g   � 001   � 215 215   L 004   [   �   �  \0   o   �       P   �   �   [   �   �   @ 203   �   �   �
0000310

출력 파일은 다음과 같습니다.

$ ls -l file_sorted.bin
-rw-r--r-- 1 glennj glennj 200 Apr 20 16:11 file_sorted.bin

$ od -c -w50 file_sorted.bin
0000000 030   �   j   �   }   o   e   k 035   /   C  \r   W   �   �   �   } 201   �   j   m   �   g 224 213   �   # 227   �   � 214   3   N   J   �   + 216   p 026   b 223   �   � 001 026   �   �   ;   �   �
0000062   T   e   s   t   i   n   g   1   2   3   e  \b  \0   ` 203   k   9   ,   � 213 217   ^   U 226 030   U   � 233 207   �   " 203   �   f   �   �   �   �   �   �   � 036   &   �   )   *   � 020   d   �
0000144   z   *   | 223   � 204 035   � 223  \n  \r   �  \a   �   � 236 004   � 236   �   w   �   �   �   g   � 001   � 215 215   L 004   [   �   �  \0   o   �       P   �   �   [   �   �   @ 203   �   �   �
0000226 225   �   � 202   b   �   �   � 004   G   � 177   w   �   :   5 207   �   � 220   B   �   � 006   � 216 237   �   �   �   �   9  \r 235  \r   � 023   � 203   B   �   R 201   . 231   K   K   @   : 026
0000310

호기심에 다음과 같은 질문에서 입력 파일(bash)을 만들었습니다.

for hx in \
    54 65 73 74 69 6E 67 31  32 33 65 08 00 60 83 6b \
    39 2c d5 8b 8f 5e 55 96  18 55 e7 9b 87 f0 22 83 \
    a4 66 b6 aa b1 f9 e0 ca  cf 1e 26 b3 29 2a fd 10 \
    64 bb 18 b5 6a c0 7d 6f  65 6b 1d 2f 43 0d 57 bd \
    e7 e4 7d 81 f3 6a 6d d2  67 94 8b bc 23 97 bf e2 \
    8c 33 4e 4a d8 2b 8e 70  16 62 93 cf aa 01 16 bf \
    da 3b b1 ab 95 e0 e4 82  62 b3 ed fe 04 47 b5 7f \
    77 b1 3a 35 87 fb e7 90  42 e3 c4 06 d6 8e 9f d2 \
    c7 f3 f6 39 0d 9d 0d ce  13 fb 83 42 e1 52 81 2e \
    99 4b 4b 40 3a 16 7a 2a  7c 93 c3 84 1d e1 93 0a \
    0d b2 07 f4 eb 9e 04 b5  9e d8 77 d9 a1 a0 67 a1 \
    01 fa 8d 8d 4c 04 5b ee  a3 00 6f b4 20 50 a4 e6 \
    5b b3 cc 40 83 eb b2 ad                         
do printf "\x$hx"; done > file.bin

답변3

그러면 파일이 16진수로 읽을 수 있는 30바이트 및 20바이트 문자열로 덤프됩니다.

cat mybinaryfile.bin | LC_ALL=C hexdump -v -e '50/1 "%02x " "\n"' | \
while read -r line ; do echo 'K="'"${line::89}"'", V="'"${line:90}"'"' ; done

LC_ALL 항상 읽을 수 있는 문자 집합으로 출력됩니다.

hexdump: -v는 동일한 행 억제를 비활성화합니다. -e는 형식 문자열을 활성화합니다. 즉, "50바이트 청크로 나누고 개행 문자(\n)로 끝나는 내용을 인쇄합니다. 50바이트 청크 내에서 한 번에 1바이트씩 10진수(x) 형식으로 인쇄합니다. 필요한 경우 앞에 0이 붙는 2자 너비(thetwo)("_p"에서 "x"를 변경하면 16진수 대신 인쇄 가능한 문자가 표시됩니다.)

이 50바이트 라인을 읽고 30바이트 및 20바이트 청크로 나누는 동안 이는 bash 인수 확장을 사용하여 먼저 89번째 문자(예: '"line::89}"' 외부의 모든 문자를 잘라낸 다음)를 통해 달성됩니다. 90번째 문자 "${line:90}" 이전의 모든 문자를 끕니다.

지금 정렬하세요. 법선 추가

| sort

물론 첫 번째 열을 기준으로 정렬하지만

| sort -t , -k 2,2

을 필드 구분 기호로 식별하고 -k 2,2는 두 번째(값) 필드를 기준으로 정렬하도록 정렬에 지시합니다.

따라서 읽을 수 있는 출력이 값별로 정렬된 전체 명령은 다음과 같습니다.

cat mybinaryfile.bin | LC_ALL=C hexdump -v -e '50/1 "%02x " "\n"' | \
while read -r line ; do echo 'K="'"${line::89}"'", V="'"${line:90}"'"' ; done | \
sort -t , -k 2,2

건배.

내 커널을 사용한 예:

sudo dd if=/boot/vmlinuz-5.13.0-25-generic bs=512 count=1 2>/dev/null | \
LC_ALL=C hexdump -v -e '50/1 "%_p" "\n"' | while read -r line ; do \
echo 'K="'"${line::29}"'", V="'"${line:30}"'"' ; done | sort -t , -k 2,2
K="..........U.", V=""
K=".........N}..................", V="...... ... ........."
K=".............................", V=".................. ."
K="....>.............. .P`......", V="..................."
K="...........P}.....X..........", V="...................."
K="...............setup...;.....", V=".;.................."
K="MZ.............1....@.. .t...", V="......1............."
K=".P`.reloc.. ....=.. ....=....", V="[email protected]"
K="t. ....=.. ....=.............", V="@..B.text.....}..>.."
K="press any key to reboot......", V="E..d..............."
K="..............Use a boot load", V="r....Remove disk and"

답변4

데이터의 크기를 고려하면 분할 정복 접근 방식을 사용하는 것이 좋습니다.

파일을 관리 가능한 덩어리로 분할합니다. 예를 들어 @glenn jackman의 방법을 사용할 수 있지만 전체 파일을 한 번에 읽는 대신 처음 천만 개의 키-값 쌍(또는 컴퓨터가 한 번에 처리할 수 있는 모든 항목)을 읽은 다음 정렬하여 tempfile1에 덤프합니다. 그런 다음 데이터는 RAM에서 지워지고 다음 블록을 읽고 정렬한 후 tempfile2에 덤프됩니다. 20GB 파일을 읽을 때까지 이 작업을 반복합니다.

이제 개별적으로 정렬된 더 작은 파일 묶음이 있으므로 다시 정리해야 합니다. 다행스럽게도 이 단계는 (상대적으로) 쉽고 가장 중요한 것은 데이터 크기가 중요하지 않다는 것입니다.

두 개의 개별적으로 정렬된 시퀀스가 ​​있는 경우 이를 하나의 정렬된 시퀀스로 결합하려면 두 개의 최상위 요소를 살펴보고 항상 첫 번째 정렬된 요소만 가져오면 됩니다. 이를 수행하는 데 필요한 것은 열려 있는 파일 3개(읽는 파일 2개와 결과를 쓰는 파일 1개)와 상위 요소 2개를 보관할 수 있는 충분한 메모리뿐입니다.

안타깝게도 이 작업을 수행하는 도구가 없으므로 직접 프로그래밍해야 할 수도 있습니다.

관련 정보