如何压缩一个已排序的单词列表？

Question

我有一个包含每行一个单词的大文件。整个文件已经排序好了，现在我需要对其进行压缩。我可以简单地使用 GZIP 进行压缩，结果不错。但是我想知道是否有可能更好地压缩，因为我们正在处理一个已排序的单词列表。

以下是我的已排序单词列表的一部分：

[...]
ABAISSAT
ABAISSATES
ABAISSE
ABAISSEE
ABAISSEES
ABAISSEMENT
ABAISSEMENTS
ABAISSENT
ABAISSER
ABAISSERA
ABAISSERAI
ABAISSERAIENT
ABAISSERAIS
[...]

使用前缀来压缩文件是否比GZIP获得更好的结果？

[...]
ABAISS AT ATES E EE EES EMENT EMENTS ENT ER ERA ERAI ERAIENT ERAIS
[...]

有什么算法可以让我使用所描述的压缩方法来压缩单词列表？还有其他的压缩数据的想法吗？

P.S. 我考虑过使用 Trie 并实现了它。Trie 的最终内存大小几乎与列表本身一样大，加载列表的时间非常长。因此，出于这些原因，我决定不走这条路。

- Martin

---

你可以尝试，但通常情况下，它不会比GZIP实现的效果更好，或者只是稍微好一点点。 - nhahtdh

您希望压缩文件的目的是什么？您只是想节省磁盘空间吗？您是否希望以编程方式操作压缩结构？您的目标是什么？ - Shredderroy

Bzip和7zip通常比gzip具有更好的压缩率。 - Shredderroy

目标是文件必须尽可能小，因为它最终将出现在移动设备上。 - Martin

gzip/bzip 压缩后的大小是多少？这还不够小吗？如果不够小，那它需要再压缩多少呢？此外，由于这是一个移动设备，运行时开销如何？我可以想象一个 稍微大一点的 文件，其运行时需求（或其他属性比如“字搜索性”）更少可能会更有优势...例如，一个基于数组的 trie（不需要完全加载的 trie）可能会更“好”。 - user166390

Answer 1

您似乎在想类似前缀压缩的东西，其中每个条目是与前面条目共享的最左字符数的计数，后跟其余未共享的字符。以下是使用您的数据的示例：

0, ABAISSAT
8, ES
6, E
7, E
etc.

结果仍需要进行gzip压缩（或其他压缩方式）。

- mgkrebbs

Answer 2

您可以创建一个函数来计算两个连续单词之间的差异，将其应用于整个列表并进行GZIP压缩（此外，您需要将第一个单词保存为起始点）。

这个函数会是什么样子呢？不确定，您需要进行实验。

这个想法是，连续单词之间的差异会很小（从信息角度来看）。

这在视频压缩中也使用了相同的概念思想（其中一种技术）- 连续帧将非常相似。

- Jon Burgess

---

请参考 https://dev59.com/BnRB5IYBdhLWcg3wv5xA#523785，该链接提供了一个类似的应用于整数的算法。显然，在两个整数之间找到差异比在两个字符串之间更容易确定函数。 - Jon Burgess