问题标签 [dawg]

在我的应用程序中，我需要使用字典，有很多单词（110 000），所以我决定使用 trie，但每次加载 trie 需要 9 秒。即使对于我的模拟器来说，这也很多。最近我读过关于 DAWG（直接 Acyclinc Word Graph）或 Minimal Acyclinc Finite State Automaton DAWG wiki什么会影响负载性能，但我找不到创建 DAWG 或 Trie 到 DAWG 算法的算法的一个很好的解释。我也找不到任何用java编写的示例，所以我请你帮忙。提前致谢

如何找到我在 python 中安装的 dwag 版本？通常是包名。版本可以解决问题，但 dawg 似乎缺乏相关方法。

在 Javascript 中在浏览器中实现 DAWG 或 GADDAG 的第一步是什么（不会超载内存）？具体来说，我想将此数据结构移植到浏览器中的交互式拼字游戏中，以便人类可以与计算机对战。

这台计算机实现了 Eric Sink ( http://ericsink.com/downloads/faster-scrabble-gordon.pdf )提出的 DAWG/GADDAG 结构。

我已经用 Python 编写了代码，该代码成功地计算了基于 GADDAG 的最佳下一步行动，但鉴于浏览器中的内存限制，我现在正在努力弄清楚如何将其移植到 Javascript/HTML 中。目前在 Python 中，此 GADDAG 结构占用约 800 MB。

我是否必须事先将 DAWG/GADDAG 构建为文本文件，然后将文本文件加载到浏览器中？或者我应该在客户端实现它？我试图找出将这种数据结构加载到交互式浏览器游戏中的所有不同方法。

我试图在安装后运行一个包，但收到此错误：

ImportError: /home/brownc/anaconda3/lib/python3.5/site-packages/dawg.cpython-35m-x86_64-linux-gnu.so: undefined symbol: _ZTVNSt7__cxx1118basic_stringstreamIcSt11char_traitsIcESaIcEEE

该dawg....gnu.so文件是二进制文件，因此在 sublime 中打开时不会提供太多信息。我对二进制文件知之甚少，无法进入并删除该行或修复它。有没有我不知道的简单解决方法？

所以我写了一个代码来构造一个dawg。我想知道一个词是否存在于一种语言中？经过大量搜索，我发现最好的方法是使用 dawg。这里

如果一个词存在，最好的查找方法是什么。考虑我想在反应原生应用程序中实现拼字游戏。我知道节点的数量可以最小化，但有什么诀窍。1-将节点和边保存在单独的文件中？如何？2-每次将大文本转换为dawg并在其中搜索？请帮忙

我需要DAWG为我的拼字游戏 IA 创建一个图形。

多次搜索后，我找到了两三个解释如何创建的站点DAWG：

https://progaide.com/question/12331755-algorithme-de-cr-ation-de-dawg-facile

如何创建 DAWG？

https://codes-sources.commentcamarche.net/faq/10903-compression-d-un-dictionnaire-sous-forme-de-dawg

但是，我不是很了解它。

我需要使用 .txt 中的字典（大约 400.000 个单词，如法语字典）创建此图，以优化对法语中存在的不同单词的搜索。

现在我在我的 .txt 中有一个简单的搜索，但它真的很慢，我认为实现这个的真正好方法是一个 .txt 文件DAWG。

我的 IA 可以将第一个单词放在 player1 的字母上，但在另一轮游戏中，我需要分析一个带有 8 个字母而不是 7 个字母的单词，我认为在进阶之前最好的选择是优化我的研究。对我来说，最好的解决方案是，DAWG但如果您有任何其他解决方案，我是开放的。

感谢您阅读我，我希望我的英语是可以理解的。

PS：如果需要.txt，我可以给你。没问题（是一本真正的完整法语拼字游戏词典）

我正在尝试使用以下规则实现一个小游戏：给定一组随机字母（例如 10 个），我想找到可以从这些字母中形成的所有可能单词。我为此使用了标准字典。

字母可以多次使用，并不是所有的字母都必须使用，只要是4个字符以上的单词即可。我认为这类似于解决字谜，只是允许多次使用字母。

例如给定的字母：qrbdtes 可能的词：bedders、甜点等。

为了寻找支持 O(1) 的数据结构来检查一个提议的单词是否在字典中，我找到了这篇论文，随后还在这里找到了一个有效的 Java DAWG 实现。

这就是我卡住的地方： 当尝试生成可以从这些字母中创建的可能单词列表时，我想知道使用 DAWG 实现是否遗漏了一些东西。我在这里看到其他线程建议使用 Trie 并递归地遍历节点，但我希望我可以用 DAWG 做类似的事情。

我目前正在使用的实现是遍历字典中的所有单词，然后跳过任何包含不属于先前分配的字母的字母的单词。这可行，但速度很慢，遍历字典中的所有单词 * 最坏情况下约 20 个字母。

我尝试实现递归单词匹配，但由于实现不公开对其 Node 实现的访问权限，但我可以在本地更改它。

如果无法访问节点，我可以使用 dawg.contains(letter)，但由于需要多次使用字母，我想知道这是否真的有帮助。例如，我会从'A' 开始，然后是'AA'，...停止在例如20 A's。

使用 Trie 会更容易吗？找到匹配的单词仍然相当快，但更容易生成可能的单词列表？

是否有其他 DAWG 库公开节点遍历或具有 ref 实现来生成所有可能的单词？

感谢您的任何帮助或指点！

我正在使用 DAWG（有向无环字图）编写文件压缩项目。程序必须执行两个操作：

1. 读取所有文件并压缩它们
2. 解压所有文件

（您不能以任何方式更改存档）

我的程序读取文件并将它们分成块（1 个块 = 8 个字节）。之后，将每个块插入 DAWG。主要问题是解压缩文件。为此，您需要遍历所有块（首先通过 DAWG 并收集第一个块，然后是第二个块，等等）

我想出的只是在每个顶点中存储v一个数组Node* d[NUMBER_OF_BLOCKS]，其中d[b]是指向块编号的下一个顶点的指针b。但是这种方法会占用大量内存（>1 MB 每个顶点，如果有很多块），因此没有压缩。是否可以在不占用大量内存的情况下存储压缩文件并解压缩所有文件？