问题标签 [dawg]

有人知道是否可以修改 Aho-Corasick 字符串匹配算法以用于 DAWG（有向无环词图）而不是 Trie 吗？

我对尝试和 DAWG（直接非循环词图）很感兴趣，并且我已经阅读了很多关于它们的内容，但我不明白输出 trie 或 DAWG 文件应该是什么样子。

• trie 应该是嵌套字典的对象吗？每个字母在哪里被分成字母等等？
• 如果有 100k 或 500k 条目，在这样的字典上执行查找会很快吗？
• 如何实现由多个单词组成的单词块，用-或空格分隔？
• 如何将单词的前缀或后缀链接到结构中的另一部分？（对于 DAWG）

我想了解最好的输出结构，以便弄清楚如何创建和使用一个。

我也很感激DAWG和trie的输出应该是什么。

我不想看到带有相互链接的气泡的图形表示，我想知道一旦一组单词变成尝试或 DAWG 后的输出对象。

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

我需要能够快速检查给定的单词是否在我的字典（英语单词表）中。我只关心检查成员的速度（不添加或删除元素），内存使用并不是真正的问题。

最初我使用的是这样的集合：

我的程序大约花了。在测试输入上运行 4 秒。然后，我尝试通过使用 DAWG ( http://pypi.python.org/pypi/pyDAWG ) 来优化事物，而不是通过预先计算 DAWG 并对其进行酸洗：

在相同的测试输入上，程序运行了大约 40 秒（包括几秒钟来加载我不关心的 DAWG）。我希望使用 DAWG 能让事情运行得更快！

也许我错过了一些关于 python 如何散列事物的理解 - 一个集合已经是我将获得的最好的（O（1）成员资格测试？）而不是 DAWG 或 Trie？DAWG 会只节省内存而不是计算吗？

非常感谢！

我只是为一个词汇构建了一个trie，然后我发现有许多分支共享相同的结构。我想将它们组合在一起成为一个DAWG。

我将使用什么算法将 trie 转换为 DAWG？

我正在寻找创建一个 DAWG 结构来验证用户输入的单词。这将在 Android 应用程序中使用。我最好的选择是在应用程序外部序列化 DAWG 结构，然后在开始时加载它吗？还是有更好的方法来使用 DAWG？

dawgdic是一个很棒的 DAWG 库，但它有一个明显的缺点，因为它是静态的（不可更新），并且必须以按字母顺序排序的字符串构造。如果构建 DAWG 的原始数据很大（几千兆字节），则 DAWG 的初始构建涉及对大量字符串进行排序可能需要太多资源。

是否有提供内存高效结构的库，dawgdic允许从未排序的字典进行构造？

我目前正在研究 DAWG，但我还没有找到一种构建无环自动机的好方法。

所以基本上，我想做的是：

它基本上是一棵树，其中状态的数量减少了。我会将它与数字一起使用，但概念完全相同。

我想知道最快的方法是什么，我的实际计划是构建左图所示的图形，然后查看低级别的状态，并在它们相似时合并它们。

虽然，我不确定这是最好的方法，但有没有人知道如何构建它。

问候。

我正在尝试将长字符串的各个部分存储在一个有效的树状结构中，我已经搜索过，但大多数实现都是用于在单词中搜索......让我试着用一个例子来解释我的意思，如果我有：

我最初的想法是这应该看起来像这样

据我搜索，真正有效的搜索树（例如 DAWG 和 Tries）用于将单词存储为字符，我不知道应该如何使用它。有任何想法吗？

提前非常感谢！

编辑：就持久性而言，我不需要存储树，所以我想只要程序运行就将它保存在内存中。

Edit2：就儿童的存储而言，我最终使用了HybridDictionaries，它比字典更有效，现在一切都运行得非常快，非常感谢大家！

我想为动态字符串实现一个字符串查找数据结构，它将支持有效的搜索和插入。目前，我正在使用 trie，但如果可能的话，我想减少内存占用。 这篇 Wikipedia 文章描述了一个 DAWG/DAFSA，它通过压缩后缀显然会比 trie 节省大量空间。然而，虽然它会清楚地测试一个字符串是否合法，但我不清楚是否有任何方法可以排除非法字符串。例如，使用单词“cite”和“cat”，其中“t”和“e”是终端状态，DAWG/DAFSA 将如下所示：

并且“cit”和“cate”将被错误地识别为没有一些元信息的合法字符串。

问题：

1) 是否有一种首选方法可以在 DAWG/DAFSA 中存储有关字符串/路径（例如合法性）的元信息？

2）如果 DAWG/DAFSA 与要求（高效搜索/插入和存储元信息）不兼容，那么最好使用什么数据结构？最小的内存占用会很好，但也许不是绝对必要的。