Adr*_*thy 7 algorithm text packing
我打赌有人之前已经解决了这个问题,但我的搜索结果是空的.
我想将一个单词列表打包到一个缓冲区中,跟踪每个单词的起始位置和长度.诀窍是我想通过消除冗余来有效地打包缓冲区.
示例:娃娃娃娃屋
这些可以简单地打包到缓冲区中dollhouse,记住doll是从位置0开始的四个字母,在0处dollhouse是九个字母,house在3处是五个字母.
到目前为止我想出的是:
由于长词通常包含较短的单词,因此效果很好,但应该可以做得更好.例如,如果我将单词列表扩展为包含ragdoll,那么我的算法会出现dollhouseragdoll效率低于ragdollhouse.
这是一个预处理步骤,所以我对速度并不十分担心.O(n ^ 2)很好.另一方面,我的实际列表有数万个单词,所以O(n!)可能是不可能的.
作为旁注,这个存储方案用于TrueType字体的`name'表中的数据,参见.http://www.microsoft.com/typography/otspec/name.htm
j_r*_*ker 13
这是最短的超字符串问题:找到包含一组给定字符串作为子字符串的最短字符串.根据这篇IEEE论文(你可能无法访问它),解决这个问题正是NP完全的.但是,可以使用启发式解决方案.
作为第一步,您应该找到所有字符串作为其他字符串的子字符串并删除它们(当然您仍然需要以某种方式记录它们相对于包含字符串的位置).使用通用后缀树可以有效地找到这些完全包含的字符串.
然后,通过重复合并具有最长重叠的两个字符串,可以保证生成长度不小于最小可能长度的4倍的解.应该可以通过使用两个基数树来快速找到重叠大小,正如Zifre关于Konrad Rudolph的回答的评论所建议的那样.或者,您可以以某种方式使用通用后缀树.
对不起,我无法为您找到一个不错的链接 - 似乎没有维基百科页面,或任何有关此特定问题的公开信息.这里简要提及,但没有提供建议的解决方案.