1. 首页
  2. 问答
  3. 自动完成算法的数据结构

自动完成算法的数据结构

2010-03-11 91 views
23

什么是自动完成算法的良好数据结构？哪些数据结构允许有效地查找包含特定子字符串的字符串？自动完成算法的数据结构

来源

2010-03-11 Tim

+0

http://en.wikipedia.org/wiki/Trie – frankc 2010-03-11 16:24:01

回答

15

如果你正在寻找做类似谷歌实现它是自动完成的方式的东西，你可能要检查出的三元搜索树：

http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/

但是，如果你想找到任何随机字符串在一个字符串中，尝试一个通用后缀树。

http://en.wikipedia.org/wiki/Generalised_suffix_tree

来源

2010-03-11 16:11:43

+0

如果您只想匹配前缀，那么这样做是否可行？例如一个三元搜索树可以帮助你匹配“abcd”中的“ab”，但不匹配“abcd”中的“bc”（可能会很厚，对三元搜索树不太了解，只会给链接留下一瞥）。 – 2010-03-11 16:15:21

+0

我这么认为，总的来说，它确实在x“开始”有点类似。但是，实际上，这似乎是我曾经使用过的所有自动完成功能的工作原理。 – 2010-03-11 16:21:34

+0

fww我使用字符串中任意位置的日常匹配的一些自动完成小部件;尽管如此 - 有用的链接，所以+1。 – 2010-03-11 16:24:10

4

退房suffix array和suffix tree。

来源

2010-03-11 16:21:41

+0

男人，我一直在寻找Ukkonen的算法多年，从来不知道！我有一个应用程序需要有效地匹配子字符串和错误。我甚至在过去这样的论坛上发过帖，但没有得到任何好的提示。你让我很快乐！ – swestrup 2010-03-11 16:35:46

+0

@swestrup：我很高兴我帮助你追踪这些信息:)你应该得到一份*算法设计手册*，http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/ref = sr_1_1？ie = UTF8＆s = books＆qid = 1268325877＆sr = 8-1它是数据结构，算法和参考书目/ URL参考的无价*汇编*） – 2010-03-11 16:53:51

1

如果你在做前缀（这是大多数autocompletes做的），那么三元搜索树也是我推荐的。如果您正在做普通中缀，那么请使用后缀树，如上所述。

来源

2010-03-11 16:24:38 swestrup

+0

Nah，它是一个愚蠢的想法。使用后缀树。好多了。 – swestrup 2010-03-11 16:33:53

+5

如果它是愚蠢的，请编辑您的答案 – 2010-03-11 18:43:27

1

作为后缀数组，树木和试验的替代方法，请查看Directed Acyclic Word Graphs（DAWG）和压缩变体（CDAWG）。它们可以以线性时间构建，占用线性空间，并允许子字符串搜索。

使用更复杂的搜索功能，您甚至可以支持一组有限的通配符。

来源

2010-05-27 16:28:29 Lucas

1

如果设置的自动完成建议是等级排序，一个SuggestTree是一个很好的数据结构。对于任何给定的前缀，它提供对以该前缀开头的建议的快速访问。

来源

2012-05-22 09:29:02

相关问题

 相关问题