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中的单词。如果必须这样做，最好使用不同的数据结构。

希望这能有所帮助！

Answer 2

是的，一般来说，有向无环权重图(DAWG)可以通过节点、边或更复杂的结构来注释，例如给定的路径，我将采用节点和边的序列。您可以对现有结构进行子类化以包含此信息，或者，如果这不可能，您可以从结构散列到注释。

Answer 3

是的你可以。从dawg开始到单词结束的每条路径都是唯一的，并且该路径可以作为整数进行索引。然后可以将该索引号映射到辅助信息。

在这里看论文：http://www.ic.unicamp.br/~reltech/1992/92-01.pdf在这里看一个好的实现：https://github.com/WojciechMula/pyDAWG/blob/master/dawg_mph.c#L37