如何压缩排序后的单词列表？
如何压缩排序后的单词列表？
提问于 2012-06-27 13:20:50
我有一个很大的文件，每行只有一个单词。整个文件都已排序，现在我需要压缩它。我可以简单地使用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
[...]什么算法可以让我使用我所描述的那种压缩来压缩我的单词列表？还有其他办法可以压缩数据吗？
附注:我考虑过使用Trie，但我实现了它。Trie的最终内存大小几乎和列表本身一样大，加载列表的时间非常长。出于这些原因，我决定不走那条路。
回答 2
Stack Overflow用户
发布于 2012-06-27 13:43:58
您似乎在考虑类似于front compression的东西，其中每个条目都是该条目与前一个条目共享的最左边的字符数的计数，后面是剩余的未共享的字符。使用您的数据的示例：
0, ABAISSAT
8, ES
6, E
7, E
etc.结果仍然需要need (或其他压缩)。
Stack Overflow用户
发布于 2012-06-27 13:28:13
您可以创建一个函数来计算两个连续单词之间的差异，将其应用于整个列表并对其进行GZIP压缩(此外，您还需要将第一个单词保存为起点)。
这个函数会是什么样子呢？不确定，你必须尝试一下。
这个想法是，连续单词之间的差异将很小(在信息方面)。
这与视频压缩中使用的概念相同(无论如何，这是一种技术)--连续的帧将非常相似。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11219872
复制相关文章
相似问题
腾讯云开发者
