c++ - DAWG 可以用来存储单词相关信息吗？

Question

DAWG 能否用于存储与每个路径相关的辅助信息，例如一个词在英语中的频率？如果是，那我该怎么做？

Answer 1

通常，您不能像在 trie 或其他数据结构中那样在 DAWG 中存储每个词的信息。这样做的原因是 DAWG 中的多个不同词可能都共享节点，因此存在一个词的信息“泄漏”到其他词的信息的风险。

举个简单的例子，假设我们有一个包含单词“is”、“as”、“i”和“a”的 DAWG。在这种情况下，DAWG 将如下所示:

                     START
                  a /     \ i
                   ACC    ACC
                 s  \     / s                        
                      ACC

请注意，表示单词“as”和“is”的节点是完全相同的节点。因此，如果您尝试用信息注释单词“as”，则保存该信息的节点也将与“is”的节点相同，这意味着“as”和“is”都将获得相同的信息信息集。

您可以尝试通过在节点中存储“as”和“is”的映射来解决这个问题，该映射从以该节点结尾的单词映射到关于该单词的额外信息，但这会显着增加内存使用量DAWG。您现在正在存储单词中的每个字符，因此您的内存使用量将会增加(请记住，DAWG 的全部目的是减少存储一组单词所需的内存使用量)。您最好只存储一个从单词映射到信息的哈希表。

您可能尝试存储此信息的另一种选择是将通过 DAWG 的每条路径扩展到它自己的分支中，这样不同单词的节点总是不同的。不过，这种方法的问题在于，您实际上是在将 DAWG 转换回 trie，这会显着增加所涉及的内存使用量。

简而言之，没有一种直接的方法可以在不显着增加内存使用量的情况下使用元信息对 DAWG 中的单词进行注释。如果必须这样做，最好使用不同的数据结构。

希望这对您有所帮助!