如何使用 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

我正在使用Linux。

答案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

这会将您的文件以十六进制转储为可读的 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 个字节,格式为十六进制(x),两个字符宽(thetwo),如果需要的话,可以加一个前导零作为前缀。 (如果更改“_p”中的“x”,您将获得可打印字符而不是十六进制。)

while 读取这些 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 的方法,但不要立即读取整个文件,只需读取前 1000 万个键值对(或者您的计算机一次可以处理的任意数量),然后对它们进行排序,并将它们转储到 tempfile1。然后从 RAM 中清除数据,读取下一个块,对其进行排序,然后转储到 tempfile2。重复此操作,直到读完 20GB 文件。

现在您有一堆较小的、单独排序的文件,我们需要将它们重新组合在一起。幸运的是,这一步(相对)简单,最重要的是不关心数据大小。

如果您有两个单独排序的序列,那么将它们组合成一个排序序列所需要做的就是查看两个顶部元素,并且始终只取第一个排序元素。执行此操作只需要三个打开的​​文件(两个您正在读取的文件,一个用于写入结果),以及足够的内存来容纳两个顶部元素。

不幸的是,我不知道有任何工具可以为您执行此操作,因此您可能必须自己编程。

相关内容