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

Question

我希望能够实现一个简单的类（使用Java语言），允许我注册和注销字符串，并基于当前字符串集合自动完成给定的字符串。因此，接口应该是：

• void add(String)
• void remove(String)
• String complete(String)

在算法和数据结构方面，最好的方法是什么？

- Kaarel

---

如果complete（）存在歧义，该怎么办？ - maccullt

complete()在某种意义上是明确的，它只会完成到歧义开始的地方（即它不会返回一个已注册的字符串，而是一些已注册字符串的公共前缀）。然而可能会有另一种方法，它会返回一个已注册字符串列表。 - Kaarel

Answer 1

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

- pgras

---

太棒了，我从未听说过PATRICIA trie。这绝对是我要进一步研究的一个领域。 - Aidos

谢谢你的回答。我最终使用了这个基数树的Java实现：http://code.google.com/p/radixtree/ - Kaarel

Answer 2

您需要的数据结构被称为三叉搜索树。在www.javaworld.com/javaworld/jw-02-2001/jw-0216-ternary.html上有一个很好的JavaWorld示例。

- Aidos

Answer 3

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

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

我希望能让人们将高效的自动完成功能融入到他们的应用程序中。快来试试吧！

- Shilad Sen

Answer 4

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

请访问http://www.idealmind.com.br/projetos/simple-autocomplete-jquery-plugin/查看。

- Wellington RIbeiro

Answer 5

你需要使用一种可以按照排序顺序维护的列表。你还需要编写自己的搜索算法，以便找到与搜索模式匹配的列表中第一个元素的索引。然后从该索引开始迭代，直到第一个不匹配的元素，这样你就得到了可能完成的列表。

我建议看一下 commons-collections 中的 TreeList。它具有快速插入和删除中间列表项的功能，这是你想要维护排序顺序所必需的。很可能可以很容易地从支持该列表的树上编写搜索函数。

- John Case

Answer 6

正则表达式。

- Jon Homan