假设你有一个巨大的字符串集合:
{'Ape','Bed','Car','Desk','Edge',...}
您需要将该集合写入文件。但字符串出现的顺序是任意的(您只需存储/检索该集合)。
由于集合可能非常大,您想要压缩它,例如使用gzip
。我对一些使得压缩比率优化的排序方式感兴趣。按字母顺序排序似乎是一个有价值的候选方案,因为这意味着如果gzip
压缩一个“帧”,那么它将看到许多以相同子字符串开头的字符串:例如在开头,它可以较短地编码AAA
,而在结尾处,ZZY
可能会被编码短。
我已经通过排序字符串运行了一些测试。例如,测试集strings
(92,274个字符串)生成:
-rw-rw-r-- 1 willem willem 296K Jan 19 18:52 strings_norm.gz
-rw-rw-r-- 1 willem willem 419K Jan 19 18:52 strings_shuf.gz
-rw-rw-r-- 1 willem willem 241K Jan 19 19:00 strings_norm.7z
-rw-rw-r-- 1 willem willem 374K Jan 19 19:01 strings_shuf.7z
其中_norm
是排序后的列表,_shuf
是它的乱序对应。这些字符串最初使用utf-8进行简单编码,并在单词之间添加了换行符。一个更易于访问的测试集可能是大多数Linux发行版上找到的美国字典(可能位于/usr/share/dict/american-english
; 99,171个单词):
-rw-rw-r-- 1 willem willem 208K Jan 19 19:40 american_norm.7z
-rw-rw-r-- 1 willem willem 250K Jan 19 19:39 american_norm.gz
-rw-rw-r-- 1 willem willem 352K Jan 19 19:40 american_shuf.7z
-rw-rw-r-- 1 willem willem 439K Jan 19 19:40 american_shuf.gz
这些是使用以下方式生成的:
sort /usr/share/dict/american-english | gzip > american_norm.gz
shuf /usr/share/dict/american-english | gzip > american_shuf.gz
sort /usr/share/dict/american-english | 7z a american_norm.7z -si
shuf /usr/share/dict/american-english | 7z a american_shuf.7z -si
如您所见,使用
gzip
可以额外获得 29%-43% 的压缩率,而使用 7z
可以获得 35%-40% 的压缩率。首先要注意的是,通过排序,这两种压缩算法的表现更好,因此假设虽然压缩率会有所不同,但可以说存在“好”的排序和“坏”的排序:几乎所有压缩算法在某些排序方式下都能获得更好的压缩率。当然,可能会出现“洗牌”数据集表现更好的情况,但这种情况的概率可能不是很高。我想知道是否存在更高级的方法。毕竟,通过排序,字符串可能以相同的子串开头,但另一种排序方式可能会发现具有共同大子串的字符串,例如 apple
、apples
、dapple
、pineapple
等。问题可能是 - 像大多数有趣的问题一样 - NP-hard,但我想知道是否存在一些启发式方法,我们可以利用它们来优化字符串压缩,而字符串的顺序并不重要。
狗 狗狗 小狗 点 点缀 猫 车 Zeta Alpha
? - chux - Reinstate Monica