如何实现一个简单的自动完成功能？

Question

我想实现一个简单的类（用Java），它允许我注册和取消注册字符串，并根据当前的字符串集自动完成给定的字符串。所以，界面将是：

• 无效添加（字符串）
• 无效删除（字符串）
• 字符串完整（字符串）

就算法和数据结构而言，做到这一点的最佳方法是什么？

Answer 1

您应该考虑使用 PATRICIA trie 作为数据结构。在谷歌上搜索“patricia trie”，你会发现很多信息......

Answer 2

您所追求的数据结构称为三元搜索树。

www.javaworld.com/javaworld/jw-02-2001/jw-0216-ternary.html 有一个很棒的 JavaWorld 示例

Answer 3

它必须是某种可以按排序顺序维护的列表。您还必须编写自己的搜索算法，该算法将为您提供列表中与您的搜索模式匹配的第一个元素的索引。然后从该索引迭代，直到第一个不匹配的元素，您就得到了可能完成的列表。

我会看看 树列表 来自公共收藏。它具有从列表中间快速插入和删除的时间，您需要这样做才能保持排序顺序。从支持该列表的树中编写搜索函数可能相当容易。

Answer 4

对于那些偶然发现这个问题的人......

我刚刚发布了一个 服务器端自动完成实现 在谷歌代码上。该项目包括一个可以集成到现有应用程序中的 java 库和一个独立的 HTTP AJAX 自动完成服务器。

我希望人们能够将高效的自动完成功能融入到他们的应用程序中。踢轮胎！

Answer 5

我创建了一个名为 Simple AutoComplete 的 JQuery 插件，它允许您在同一页面上根据需要添加许多自动完成功能，并添加带有额外参数的过滤器，并执行回调函数以引入其他参数，例如项目的 id。

请参阅 http://www.idealmind.com.br/projetos/simple-autocomplete-jquery-plugin/

Answer 6

常用表达。