文本打包算法
|
我打赌有人之前已经解决了这个问题,但我的搜索结果是空的.
我想将一个单词列表打包到一个缓冲区中,跟踪每个单词的起始位置和长度.诀窍是我想通过消除冗余来有效地打包缓冲区. 示例：娃娃娃娃屋 这些可以简单地作为玩具屋打包到缓冲区中,记住玩偶是从位置0开始的四个字母,玩偶屋是0处的九个字母,而房子是3处的五个字母. 到目前为止我想出的是： >将最长的单词排序为最短的:(娃娃屋,房子,洋娃娃) 由于长词通常包含较短的单词,因此效果很好,但应该可以做得更好.例如,如果我将单词列表扩展为包含ragdoll,那么我的算法会出现娃娃屋,它比ragdollhouse效率低. 这是一个预处理步骤,所以我对速度并不十分担心. O(n ^ 2)很好.另一方面,我的实际列表有数万个单词,所以O(n！)可能是不可能的. 作为旁注,这个存储方案用于TrueType字体的`name’表中的数据,参见. http://www.microsoft.com/typography/otspec/name.htm 解决方法
这是最短的超字符串问题：找到包含一组给定字符串作为子字符串的最短字符串.根据
this IEEE paper(你可能无法访问它),解决这个问题正是NP完全的.但是,可以使用启发式解决方案.
作为第一步,您应该找到所有字符串作为其他字符串的子字符串并删除它们(当然您仍然需要以某种方式记录它们相对于包含字符串的位置).使用generalised suffix tree可以有效地找到这些完全包含的字符串. 然后,通过重复合并具有最长重叠的两个字符串,可以保证生成长度不小于最小可能长度的4倍的解.应该可以通过使用两个基数树来快速找到重叠大小,如Zifre在Konrad Rudolph’s answer的评论所建议的那样.或者,您可能能够以某种方式使用广义后缀树. 对不起,我无法为您找到一个不错的链接 – 似乎没有维基百科页面,或任何有关此特定问题的公开信息.尽管没有提供建议的解决方案,但是简要地提到了here. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |