2

是否可以使用 DAWG 存储与每条路径相关的辅助信息，例如英语中单词的频率？如果是，那我该怎么做？

4

3 回答 3

2

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

于 2012-12-24T20:29:12.390 回答
2

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

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

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

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

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

您可能尝试存储此信息的另一种选择是将通过 DAWG 的每条路径扩展到其自己的分支，以便不同单词的节点始终不同。但是，这种方法的问题在于，您正在有效地将 DAWG 转换回 trie，这会显着增加所涉及的内存使用量。

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

希望这可以帮助！

于 2012-12-24T21:38:19.250 回答
0

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

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

于 2017-12-08T05:10:56.430 回答