代码补全的搜索算法用什么合适

[oldcai]

抽象出来应该就是顺序输入一个变量或者函数什么的中间的几个字母，就搜索出最符合的一个补全作为提示。

用b-tree还是trie还是ngram呢，能告诉一下原因就太感谢了。

[signal]

马甲自顶

[jjplay]

马甲自顶

[luikore]

已知前缀,用 trie
已知后缀,把词都反序了和前缀一样
已知中缀,用 trie+后缀树
已知前后缀, 先做前缀匹配, 再筛选

参考 textmate 源码: https://github.com/textmate/textmate/blob/master/Frameworks/editor/src/completion.cc

[luikore]

数据结构的话, trie 有很多变种的.

HAT-trie 比darray-trie/burst-trie/judy-array 要快一些, 我有 HAT-trie 的一个 fork, 添加了前缀搜索和步进 walk 功能

https://github.com/luikore/hat-trie

[oldcai]

@luikore 好像是不知到底是前缀还是后缀还是中缀，比如
abcdefg
现在abc要提示
ceg也要提示
afg也要提示
这个样子捏？
唯一确定的是字母顺序是一定的，但是出现与否是不确定的

[luikore]

@oldcai

前/后缀搜索是中缀的特殊情况, 把 abcdefg 的后缀子串全部插入一个树里

abcdefg
bcdefg
cdefg
defg
efg
fg
g

通过前缀搜索就能匹配任何子串, 这棵树就叫后缀树.

跳字搜索其实不难, 例如搜 ceg, 先获取 c 对应的子树(上面的情况就只有 cdefg 一项了...), 然后遍历这个子树找匹配 c*e*g 的就可以. 不是超巨大候选列表的情况不会慢.