blocks|key|3569806|text|使用Trie是一种选择，但它们的空间效率很低。通过使用称为Radix+Tree或Patricia+Tree的修改版本，可以使它们具有更高的空间效率。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3569807|三元搜索树可能是更好的选择。这里有一篇关于这个主题的文章："Efficient+auto-complete+with+a+ternary+search+tree.“另一篇关于使用三元搜索树进行拼写更正(与自动补全类似的问题)的优秀文章是"Using+Ternary+DAGs+for+spelling+correction.”|3569808|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Trie|1|http://en.wikipedia.org/wiki/Radix_tree|2|http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/|3|http://www.strchr.com/ternary_dags^0|2|4|0|T|A|1|0|U|1F|2|3B|17|3|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]|$A|X|B|Y|1|Z]]|C|$]]|$1|D|3|E|5|6|7|10|8|@]|9|@$A|11|B|12|1|13]|$A|14|B|15|1|16]]|C|$]]|$1|F|3|-4|5|6|7|17|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]|N|$5|I|J|K|C|$L|O]]|P|$5|I|J|K|C|$L|Q]]|R|$5|I|J|K|C|$L|S]]]]

Using a <a href="http://en.wikipedia.org/wiki/Trie" rel="noreferrer">Trie</a> is an option but they are space-inefficient. They can be made more space effecient by using a modified version known as a <a href="http://en.wikipedia.org/wiki/Radix_tree" rel="noreferrer">Radix Tree</a>, or Patricia Tree.

A ternary search tree would probably be a better option. Here is an article on the subject: "<a href="http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/" rel="noreferrer">Efficient auto-complete with a ternary search tree.</a>" Another excellent article on the use of Ternary Search Tree's for spelling-correction (a similar problem to auto-complete) is, "<a href="http://www.strchr.com/ternary_dags" rel="noreferrer">Using Ternary DAGs for spelling correction.</a>"

blocks|key|3569730|text|我认为binary+search在处理10000个条目时工作得很好。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3569731|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Binary_search^0|3|D|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

I think <a href="http://en.wikipedia.org/wiki/Binary_search" rel="nofollow noreferrer">binary search</a> works just fine for 10000 entries.

blocks|key|5681914|text|一个trie:只要你输入一个字母，http://en.wikipedia.org/wiki/Trie就会给你O(N)的搜索时间(我假设你每次输入一个字母都想要新的建议)。如果你有很小的单词，这应该是相当有效的，并且每个新字母的搜索空间都会减少。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|5681915|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Trie^0|H|X|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

A trie: <a href="http://en.wikipedia.org/wiki/Trie" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Trie</a> gives you O(N) search time whenever you type a letter (I'm assuming you want new suggestions whenever a letter is typed). This should be fairly efficient if you have small words and the search space will be reduced with each new letter.

blocks|key|5681923|text|正如您已经提到的，您将单词存储在数据库中(请参阅Auto-suggest+Technologies+and+Options)，创建单词的索引并让数据库完成此工作。他们知道如何高效地做到这一点。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|5681924|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/2331919^0|O|11|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

As you’ve already mentioned that you store your words in a database (see <a href="https://stackoverflow.com/questions/2331919">Auto-suggest Technologies and Options</a>), create an index of that words and let the database do the work. They know how to do that efficiently.

blocks|key|3569860|text|对于纵横字词，提出了一种比较绕道的方法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3569861|它可以很容易地在这里改编:)|3569862|这个想法很简单，但相当有效:它包括索引单词，为每个字母位置建立一个索引。应该注意的是，在4/5个字母之后，可用的单词子集非常小，因此暴力可能是最好的……当然，这是必须衡量的。|3569863|至于这个想法，这里有一种Python方式：|3569864|class+AutoCompleter:
++def+__init__(self,+words):
++++self.words+=+words
++++self.map+=+defaultdict(set)
++++self._map()

++def+_map(self):
++++for+w+in+words:
++++++for+i+in+range(0,len(w)):
++++++++self.map[(i,w[i])].insert(w)

++def+words(self,+firstLetters):
++++#+Gives+all+the+sets+for+each+letter
++++sets+=+[self.map[(i,+firstLetters[i])]+for+i+in+range(0,+len(firstLetters))]

++++#+Order+them+so+that+the+smallest+set+is+first
++++sets.sort(lambda+x,y:+cmp(len(x),len(y)))

++++#+intersect+all+sets,+from+left+to+right+(smallest+to+biggest)
++++return+reduce(lambda+x,y:+intersection(x,y),+sets)|code-block|syntax|javascript|3569865|内存要求相当严格:每个位置的每个字母对应一个条目。但是，条目表示在此位置存在带有字母的单词，但并非所有情况都是如此。|3569866|速度似乎也很好，如果你想自动完成一个3个字母的单词(触发自动完成的经典阈值)：|3569867|3569868|我肯定需要在三叉树和trie方法上尝试一下，看看它是如何运行的。|3569869|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|W|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|X|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Y|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|Z|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|10|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|11|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|12|8|@]|9|@]|A|$]]|$1|R|3|S|5|6|7|13|8|@]|9|@]|A|$]]|$1|T|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|U|$]]

A rather roundabout method was proposed on SO for crosswords.

It could be adapted here fairly easy :)

The idea is simple, yet quite efficient: it consists on indexing the words, building one index per letter position. It should be noted that after 4/5 letters, the subset of words available is so small that a brute force is probably best... this would have to be measured of course.

As for the idea, here is a Python way:

<pre><code>class AutoCompleter:
 def __init__(self, words):
 self.words = words
 self.map = defaultdict(set)
 self._map()

 def _map(self):
 for w in words:
 for i in range(0,len(w)):
 self.map[(i,w[i])].insert(w)

 def words(self, firstLetters):
 # Gives all the sets for each letter
 sets = [self.map[(i, firstLetters[i])] for i in range(0, len(firstLetters))]

 # Order them so that the smallest set is first
 sets.sort(lambda x,y: cmp(len(x),len(y)))

 # intersect all sets, from left to right (smallest to biggest)
 return reduce(lambda x,y: intersection(x,y), sets)
</code></pre>

The memory requirement is quite stringent: one entry for each letter at each position. However, an entry means a word exist with a letter at this position, which is not the case for all.

The speed seems quite good too, if you wish to auto-complete a 3-letters word (classic threshold to trigger auto-completion):

<ul>
<li>3 look ups in a hash-map</li>
<li>2 intersections of sets (definitely the one spot), but ordered as to be as efficient as possible.</li>
</ul>

I would definitely need to try this out against the ternary tree and trie approach to see how it fares.

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

What is an efficient search algorithm to provide auto-completion?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我有一个包含10000个关键词的列表。什么是有效的搜索算法来提供该列表的自动完成？

问提供自动补全的有效搜索算法是什么？
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问提供自动补全的有效搜索算法是什么？EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问提供自动补全的有效搜索算法是什么？
EN