![如何使用 Linux 排序实用程序按固定字节偏移量对二进制键值对进行排序?](https://linux22.com/image/204894/%E5%A6%82%E4%BD%95%E4%BD%BF%E7%94%A8%20Linux%20%E6%8E%92%E5%BA%8F%E5%AE%9E%E7%94%A8%E7%A8%8B%E5%BA%8F%E6%8C%89%E5%9B%BA%E5%AE%9A%E5%AD%97%E8%8A%82%E5%81%8F%E7%A7%BB%E9%87%8F%E5%AF%B9%E4%BA%8C%E8%BF%9B%E5%88%B6%E9%94%AE%E5%80%BC%E5%AF%B9%E8%BF%9B%E8%A1%8C%E6%8E%92%E5%BA%8F%EF%BC%9F.png)
我想排序 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 文件。
现在您有一堆较小的、单独排序的文件,我们需要将它们重新组合在一起。幸运的是,这一步(相对)简单,最重要的是不关心数据大小。
如果您有两个单独排序的序列,那么将它们组合成一个排序序列所需要做的就是查看两个顶部元素,并且始终只取第一个排序元素。执行此操作只需要三个打开的文件(两个您正在读取的文件,一个用于写入结果),以及足够的内存来容纳两个顶部元素。
不幸的是,我不知道有任何工具可以为您执行此操作,因此您可能必须自己编程。