4

我有一个大文件，每行一个单词。整个文件已排序，我现在需要压缩它。我可以简单地使用 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
[...]

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

PS 我虽然关于使用 Trie 并且我实现了它。Trie 的最终大小是内存几乎与列表本身一样大，并且加载列表的时间非常长。由于这些原因，我决定不走那条路。

4

2 回答 2

6

您似乎在考虑诸如front compression之类的东西，其中每个条目都是该条目与前一个条目共享的最左边字符数，然后是剩余的未共享字符。使用您的数据的示例：

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

结果仍然需要 gzipping（或其他压缩）。

于 2012-06-27T05:43:58.140 回答
1

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

该功能会是什么样子？不确定，你必须尝试一下。

这个想法是连续单词之间的差异很小（就信息而言）。

这与视频压缩中使用的概念想法（无论如何是其中一种技术）相同 - 连续帧将非常相似。

于 2012-06-27T05:28:12.673 回答