假设你有一个巨大的字符串集合：
{'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