有效地存储同词排列

Question

我有一个关于字典存储的问题。

我在读Trie数据结构，到目前为止，我已经读到它作为前缀树工作得很好。但是，我来到Trie-DS是为了看看它是否能有效地减少通过同一个单词形成的字母排列的存储。

对于ex：单词“ant”、“tan”和NAT有相同的字母，但根据Trie的说法，它继续为这些单词创建两个独立的路径。我可以理解Trie是用来存储前缀和减少冗余的。但有人能帮我减少这里的冗余吗。我想的一种方法是改变Trie的行为，因为每个节点都有一个“单词完成”的状态；此外，如果我把‘字开始’的状态，我可以使这工作如下：

A
N - A - T
T - A - N

现在，每次我都可以检查单词是否从这里开始，直到最后。

这有道理吗？如果这是可行的呢？或者他们有什么更好的方法来做到这一点？

谢谢

Answer 1

如果向每个节点添加一个状态字段，那么树的内存开销（假设为8位字符）将增加一个可能不是微不足道的部分。

我明白您希望减少DS中的字母数量，但您必须考虑如果某些内容是其他内容的子集会发生什么，例如ANTAN将如何表示。考虑作为全连通图节点的最小字符数（128）。显然所有的词都存储在这个图中，但是它不适合存储任何特定的词。没有办法说出单词在哪里结束。存储在trie中的信息不仅仅是字母，而是完整的、适当终止的单词。

如果你按照你的建议添加一个标记，你将如何编码这个：增压，超级，鲈鱼。您将word_starts设置为S和P，word_ends设置为R和h，您怎么知道SUPERCH和PER不包含？您可以使用一个非零标签，并为单词的开头和结尾分配数字对:S:1，P:2，R:1，H:2。为了确保开始和结束可以出现在同一个字母上，您必须使用特定的位作为标签。

然后你可以使用清液作为最小平面表示，N:001A:000T:011A:100N:010T:100。在最坏的情况下，这需要标记的#字位：A,AA,aaa....但是，如果要将其存储在树中，则必须查找另一个标记，这不是树所支持的操作。所以我看不出使用标记的好方法。

从信息理论的角度来看，我认为关键的问题是如何正确地对一个词的长度、顺序和内容进行编码，并以一种独特的方式对它们的每一种可能的组合进行编码。

我本来只想发表评论，但有点冗长。我不确定这是否回答了你的问题，但我希望它能有所帮助。