V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
oldcai
V2EX  ›  问与答

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

  •  
  •   oldcai · 2013-07-05 14:38:06 +08:00 · 3405 次点击
    这是一个创建于 4150 天前的主题,其中的信息可能已经有所发展或是发生改变。
    抽象出来应该就是顺序输入一个变量或者函数什么的中间的几个字母,就搜索出最符合的一个补全作为提示。

    用b-tree还是trie还是ngram呢,能告诉一下原因就太感谢了。
    6 条回复    1970-01-01 08:00:00 +08:00
    signal
        1
    signal  
       2013-07-05 15:52:47 +08:00
    马甲自顶
    jjplay
        2
    jjplay  
       2013-07-05 15:57:09 +08:00
    马甲自顶
    luikore
        3
    luikore  
       2013-07-05 16:07:37 +08:00   ❤️ 1
    已知前缀,用 trie
    已知后缀,把词都反序了和前缀一样
    已知中缀,用 trie+后缀树
    已知前后缀, 先做前缀匹配, 再筛选

    参考 textmate 源码: https://github.com/textmate/textmate/blob/master/Frameworks/editor/src/completion.cc
    luikore
        4
    luikore  
       2013-07-05 16:22:57 +08:00   ❤️ 1
    数据结构的话, trie 有很多变种的.

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

    https://github.com/luikore/hat-trie
    oldcai
        5
    oldcai  
    OP
       2013-07-05 20:13:27 +08:00
    @luikore 好像是不知到底是前缀还是后缀还是中缀,比如
    abcdefg
    现在abc要提示
    ceg也要提示
    afg也要提示
    这个样子捏?
    唯一确定的是字母顺序是一定的,但是出现与否是不确定的
    luikore
        6
    luikore  
       2013-07-05 20:45:47 +08:00   ❤️ 1
    @oldcai

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

    abcdefg
    bcdefg
    cdefg
    defg
    efg
    fg
    g

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

    跳字搜索其实不难, 例如搜 ceg, 先获取 c 对应的子树(上面的情况就只有 cdefg 一项了...), 然后遍历这个子树找匹配 c*e*g 的就可以. 不是超巨大候选列表的情况不会慢.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1718 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 18ms · UTC 16:52 · PVG 00:52 · LAX 08:52 · JFK 11:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.