什么是提供自动完成功能的有效搜索算法？ [英] What is an efficient search algorithm to provide auto-completion?

问题描述

我有10000个关键字的列表。什么是有效的自动搜索列表算法？

I've got a list of 10000 keywords. What is an efficient search algorithm to provide auto-completion with that list?

推荐答案

使用 Trie 是一种选择，但空间效率低。通过使用称为基数树或Patricia树的修改版本，可以提高它们的空间效率。

Using a Trie is an option but they are space-inefficient. They can be made more space effecient by using a modified version known as a Radix Tree, or Patricia Tree.

三元搜索树可能是一个更好的选择。这是有关该主题的文章： 高效的自动关于使用三元搜索树进行拼写校正（与自动完成类似的问题）的另一篇优秀文章是， 使用三元DAG进行拼写更正。

A ternary search tree would probably be a better option. Here is an article on the subject: "Efficient auto-complete with a ternary search tree." Another excellent article on the use of Ternary Search Tree's for spelling-correction (a similar problem to auto-complete) is, "Using Ternary DAGs for spelling correction."

这篇关于什么是提供自动完成功能的有效搜索算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！