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

一个普通的搜索服务该怎么做?

  •  
  •   vjnjc · 2019-11-28 17:36:48 +08:00 · 1980 次点击
    这是一个创建于 1813 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天面试被问到一道题目,回来想了半天也没思路,求拍醒

    问题: 假设你平时用 IDE 进行编码,IDE 会在启动的时候做一些索引。然后你整个项目搜索“String”会迅速定位到多个包含 String 关键字的代码。 请问由你来做这个功能,怎么才能让搜索执行效率高?

    第 1 条附言  ·  2019-11-28 18:19:03 +08:00
    搜索部分应该是像 4 楼所说的,分索引和没索引两种类型。

    有没有做中文搜索匹配的能告诉我一下火星文该怎么匹配啊?
    12 条回复    2019-11-28 20:01:28 +08:00
    lhx2008
        1
    lhx2008  
       2019-11-28 17:41:08 +08:00 via Android
    索引之后肯定是 O(logn) 以下了,所以是问怎么建立索引?
    vjnjc
        2
    vjnjc  
    OP
       2019-11-28 17:44:14 +08:00
    @lhx2008 嗯应该是问怎么建索引。
    我一个粗糙的考虑是用 dictionary,比如“String” -> [“file1”, "file2", "file3"...], “Str” -> [“file1”, "file2", "file3"...], “S” -> [“file1”, "file2", "file3"...],这样的话查起来方便,但是空间效率利用太低了吧。。。
    vjnjc
        3
    vjnjc  
    OP
       2019-11-28 17:46:45 +08:00
    @lhx2008 还有一个 followup,火星文该怎么匹配?比如搜索我,能找到“涐”。这个就更加没有头绪了。。。
    optional
        4
    optional  
       2019-11-28 17:47:34 +08:00   ❤️ 1
    无索引搜索可能问的是 BM 算法, 有索引问的应该是分词之后倒排索引。
    lhx2008
        5
    lhx2008  
       2019-11-28 17:47:53 +08:00 via Android
    @vjnjc 你这个示例,用一个前缀树做 key 的结构就行啊,而且 s 这种单词有没有搜索的价值。至于怎么解析代码就很复杂了。
    jenschen
        6
    jenschen  
       2019-11-28 17:48:54 +08:00 via iPhone
    b+树吧
    lhx2008
        7
    lhx2008  
       2019-11-28 17:49:12 +08:00 via Android
    同意楼上,可能考的是只是字符串搜索
    vjnjc
        8
    vjnjc  
    OP
       2019-11-28 18:00:01 +08:00
    @optional 多谢指点迷津
    vjnjc
        9
    vjnjc  
    OP
       2019-11-28 18:01:33 +08:00
    @lhx2008 多谢。
    这应该是个开放性题目,看我知识广度,感觉回答出 4#说的 2 种之一就好了,然而我都没看到过 0 0,说实话前缀树在做算法的时候自己还用过,忘得一干二净了
    Vegetable
        10
    Vegetable  
       2019-11-28 18:02:12 +08:00
    这场景怪怪的,ide 真的会做这个事情吗?
    66450146
        11
    66450146  
       2019-11-28 18:50:53 +08:00
    这个最合适的还是参考 Language Server Protocol ( https://microsoft.github.io/language-server-protocol/overview)

    从这里倒推具体 language server 的实现,其实就是一个 tokeniser,生成 AST ( https://en.wikipedia.org/wiki/Abstract_syntax_tree) 分析就行了,大部分都是这么做的

    字符串匹配不是不行,但是效果要差很多,对于关键字很多的语言更麻烦
    vjnjc
        12
    vjnjc  
    OP
       2019-11-28 20:01:28 +08:00
    @66450146 多谢神乃木,又有新线索了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1612 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 39ms · UTC 17:04 · PVG 01:04 · LAX 09:04 · JFK 12:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.