如何更有效地将词汇存储在数组中？

Question

我有一个词汇表，a，放弃，...，z。

出于某种原因，我将使用array而不是Trie来存储它们。

因此，一个简单的方法可以是：wordA\0wordB\0wordC\0。。。word\0

但是我认为有一些更经济的记忆方法。

由于like很可能是的子字符串，我们只能存储like的第一个位置和长度，而不是字符串本身。因此，我们生成一个“大字符串”，其中包含词汇表中的每个单词，并使用位置[i]和长度[i]来获取i-第四个单词。

例如，词汇表包含三个单词：ab、cd和bc。我将abcd构造为“大字符串”。

position[0] = 0, length[0] = 2

position[1] = 2, length[1] = 2

position[2] = 1, length[2] = 2

那么，如何生成“大字符串”是这个问题的关键，有什么好的建议吗？

我认为这个问题类似于TSP问题（旅行商问题），它是一个NP问题。




Answer 1

你要找的搜索关键字是“dictionary”。i、 e.可用于存储单词列表的数据结构，并测试字典中是否存在其他字符串。

您的想法比单独存储每个单词更紧凑，但远不如良好的数据结构（如DAWG）紧凑。正如您所注意到的，如何最佳地选择如何重叠字符串并不明显。您所做的有点像无损压缩方案（如gzip）所做的。如果您不需要根据紧凑型词典检查单词，可以使用gzip或LZMA来压缩已排序的单词列表。让他们的算法找到冗余并紧凑地表示。

我在字典里查找了一个最近引起我兴趣的SO答案：内存受限的字符串外部排序，并将重复项组合在一起

对于一个不需要动态添加新词的词典来说，有向无环词图是一个不错的选择。通过跟随图形节点，将字符串与其匹配，直到到达一个点，该点没有与下一个字符匹配的边，或者到达输入字符串的末尾，并发现DAWG中的节点被标记为有效的单词结尾。（而不仅仅是一些单词的前缀的子字符串）。有一些算法可以在合理的时间内从简单的单词字典数组中构建这些状态机。

只有当整个单词是另一个单词的子字符串，或一个单词的结尾，另一个单词的开头时，您的方法才能利用冗余。DAWG可以在任何地方利用公共子字符串，并且匹配单词的速度也相当快。可能与二进制搜索数据结构的速度相当，尤其是当巨大的字符串太大而无法放入缓存时。（一旦开始超过缓存大小，数据结构的紧凑性就开始超过代码的复杂度以提高速度。）

不太复杂但仍然有效的是Trie（或Radix Trie），其中公共前缀被合并，但单词中的公共子串稍后不会再次收敛。

如果您根本不需要修改DAWG或Trie，那么可以将其高效地存储在单个内存块中，而不是动态分配每个节点。您没有说为什么不想使用Trie，也没有承认存在其他比普通Trie更好的数据结构。