☰

Linuxソートユーティリティを使用して固定バイトオフセットでバイナリキーと値のペアをソートする方法は？

tag-icon • tag-icon sort
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

私はLinuxを使用しています。

答え1

見苦しいですが正常に動作します。

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

hexdump1行に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）形式で印刷します。幅（「_p」で「x」を変更すると、16進数ではなく印刷可能な文字が表示されます。）

この50バイトの行を読み、30バイトと20バイトのチャンクに分割する間、これはbash引数拡張を使用して最初の89番目の文字（「line::89}」の外側のすべての文字を切り取った後）で達成されます。 。 90番目の文字 "${line:90}"より前のすべての文字をドラッグします。

今並べ替えてください。法線を追加

| sort

もちろん、最初の列に基づいて並べ替えますが、

| sort -t , -k 2,2

をフィールド区切り文字として識別し、-k 2,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のメソッドを使用できますが、ファイル全体を一度に読み取るのではなく、最初の1000万のKey-Valueペア（またはコンピュータが一度に処理できるすべての項目）を読み取り、並べ替えてtempfile1にダンプします。 。その後、データはRAMから消去され、次のブロックを読み取ってソートした後、tempfile2にダンプされます。 20 GB ファイルを読み取るまでこの操作を繰り返します。

これで、個別にソートされた小さなファイルの束があるので、もう一度クリーンアップする必要があります。幸いなことに、このステップは（比較的）簡単で最も重要なことは、データサイズが重要ではないことです。

2つの別々にソートされたシーケンスがある場合、それらを1つのソートされたシーケンスに結合するには、2つの最上位要素を調べて、常に最初のソートされた要素のみを取得します。これを行うために必要なのは、3つの開いているファイル（2つの読み取りファイルと1つの結果を書き込む）と2つの親要素を保持するのに十分なメモリだけです。

残念ながら、これを行うツールはないので、自分でプログラムする必要があるかもしれません。

関連情報