V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
7color94
V2EX  ›  算法

Trie 树实现简单的前缀搜索关键词提示

  •  
  •   7color94 · 2017-01-16 09:19:33 +08:00 · 3123 次点击
    这是一个创建于 2866 天前的主题,其中的信息可能已经有所发展或是发生改变。

    最近整理 KMP , Trie , Trie 图三个算法。后来就直接用 Trie 树实现 web 端的搜索关键词提示小功能。

    实现原理:利用 1w2 英文单词建立 Trie 树。前端实时检测用户键盘输入,通过 ajax 请求计算得到:当前输入字符串作为前缀时所有的英文单词。并显示在输入框下方。

    进一步改进:通过记录用户输入的日志,利用 top-k 算法计算出热度最高的高频词,提示的时候只提示高频词,而不是现在这样提示所有包含前缀的关键词。

    项目地址: https://github.com/7color94/search-suggest

    5 条回复    2017-02-17 02:48:39 +08:00
    BuilderQiu
        1
    BuilderQiu  
       2017-01-16 09:24:13 +08:00
    我在想这种集群环境下要怎么弄,每台机器都弄一份?
    pandachow
        2
    pandachow  
       2017-01-16 10:51:29 +08:00
    问下同一个子树下面的排序是怎么做的?比方说输入了 te, 下面的 tee 和 tea 是怎么排列的,谁排在前面?字母顺序吗?
    7color94
        3
    7color94  
    OP
       2017-01-16 12:23:27 +08:00
    @BuilderQiu ajax 到中心服务器请求数据?
    7color94
        4
    7color94  
    OP
       2017-01-16 12:24:32 +08:00
    @pandachow 目前我是按照建立 Trie 树的顺序排列的。谁先出现谁排在前面。如果是真正应用场景的话,根据“热度”排列吧。
    jedihy
        5
    jedihy  
       2017-02-17 02:48:39 +08:00
    @BuilderQiu 假设第一个节点有 a-z 个子节点,可以把 a-z 的子树存到 26 台主机。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1452 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 433ms · UTC 23:56 · PVG 07:56 · LAX 15:56 · JFK 18:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.