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

今天面试被问了个算法,不会,请教下

  •  
  •   ruandao · 2020-05-08 02:51:23 +08:00 · 2269 次点击
    这是一个创建于 1659 天前的主题,其中的信息可能已经有所发展或是发生改变。

    大致题目是,譬如书名是 数据结构预算法

    然后搜索的时候,输入 "数 算"

    要怎么设计,去匹配搜索

    8 条回复    2020-05-08 09:00:10 +08:00
    hehheh
        1
    hehheh  
       2020-05-08 03:00:49 +08:00
    trie 吧
    binux
        2
    binux  
       2020-05-08 03:17:47 +08:00
    搜索什么?

    从一堆书里面搜到这本?
    从字符串中搜索"数 算"的位置?
    判断字符串是否符合包含"数 算"子串?
    lihongming
        3
    lihongming  
       2020-05-08 03:24:50 +08:00 via iPhone
    @hehheh 字很多、数据集很大的话,会不会很慢?

    个人觉得用桶可能更直接一些,每个字一个桶,把这两个桶取出来求交集
    shikimoon
        4
    shikimoon  
       2020-05-08 03:45:01 +08:00
    这种属于搜索查询中的模糊匹配场景,可以用分词+倒排索引,然后做字符串匹配。简单的用编辑距离也行
    hehheh
        5
    hehheh  
       2020-05-08 04:15:38 +08:00
    @lihongming 对,这样应该会比 trie 快很多。
    ruandao
        6
    ruandao  
    OP
       2020-05-08 05:36:11 +08:00
    @binux 一堆书名中搜索匹配的书名
    sadfQED2
        7
    sadfQED2  
       2020-05-08 08:12:59 +08:00 via Android
    倒排索引可以解决,分词的时候根据他的要求分词,比如他这个要单个字搜那就单个字分词。你可以看看 es 的搜索原理
    HuHui
        8
    HuHui  
       2020-05-08 09:00:10 +08:00 via Android
    基本就冲着 es 去了吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5771 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 01:53 · PVG 09:53 · LAX 17:53 · JFK 20:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.