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

Question

我有一个关键字字典，我想在web应用程序的客户端提供自动补全/建议。ajax的转变引入了太多的延迟，因此将整个单词列表存储在客户端上会很好。

这个列表可能有几十万个单词，也可能有几百万个。我做了一点研究，看起来dawg结构可以提供空间和查找效率，但我找不到真实的数字。

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

Answer 1

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

尽管如此，如上所述，JavaScript仍然无法处理这些数据量。尝试处理几MB的数据将使JavaScript解释器挂起几分钟，从而有效地挂起整个浏览器。

Answer 2

我对“几百万”和"JavaScript“这两个事实感到畏缩。JS的目的是打乱小块数据，而不是兆字节。想象一下，用户需要等待多长时间才能加载您的页面！

在您的情况下，AJAX的周转速度如此之慢肯定是有原因的。谷歌每天处理数十亿个AJAX请求，而且它们的类型很快(只要在www.google.com上试试就知道了)。所以在你的设置中一定有什么东西坏了。找到它并修复它。

Answer 3

您的解决方案听起来很实用，但是您可能仍然想看看，例如，jQuery的自动完成实现，看看它们是如何处理延迟的。