javascript - 有向无环词图(dawg)的空间效率是多少？是否有 javascript 实现？

Question

我有一个关键字字典，我想在 Web 应用程序的客户端提供自动完成/建议功能。 ajax 周转引入了过多的延迟，因此最好将整个单词列表存储在客户端上。

该列表可能有数十万个单词，也可能有几百万个。我做了一些研究，发现 dawg 结构可以提供空间和查找效率，但我找不到真实世界的数字。

此外，请随时提出实现相同功能的其他可能性。

Answer 1

我最近为文字游戏程序实现了 DAWG。它使用的字典包含 270 万个波兰语单词。源纯文本文件大小约为 33MB。在二进制文件中表示为 DAWG 的相同单词列表仅占用 5MB。实际大小可能会有所不同，因为它取决于实现，因此顶点数 - 154k 和边数 - 411k 是更重要的数字。

尽管如此，如上所述，JavaScript 无法处理如此庞大的数据量。尝试处理几 MB 的数据会使 JavaScript 解释器挂起几分钟，实际上挂起整个浏览器。