V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
shoumu
V2EX  ›  程序员

一道有意思的问题

  •  
  •   shoumu ·
    shoumu · 2014-05-30 17:24:00 +08:00 · 3347 次点击
    这是一个创建于 3819 天前的主题,其中的信息可能已经有所发展或是发生改变。
    搜索的时候,来了一个query,为了判断这个query是否满足某种格式以促发某种搜索(如天气:北京),我们采用正则表达式进行匹配。现在假设有1000个类似的正则表达式,问要怎么做才能尽可能小的影响搜索速度?
    15 条回复    2014-06-02 22:50:00 +08:00
    liprais
        1
    liprais  
       2014-05-31 05:09:01 +08:00 via iPad
    对这一千个正则分类吧,先试区分度大的,然后动态调整
    shoumu
        2
    shoumu  
    OP
       2014-05-31 10:19:33 +08:00
    @liprais 你这个不好具体实现啊。

    现在有一个思路是这样的,对1000个正则简历倒排索引,然后每次query来的时候,都去查找,相当于另一个搜索
    liprais
        3
    liprais  
       2014-05-31 13:53:47 +08:00
    @shoumu 你这种是不是还执行配每个正则表达式才能得到结果?
    shoumu
        4
    shoumu  
    OP
       2014-05-31 14:04:24 +08:00
    @liprais 不用,是去搜索出最匹配的正则表达式,然后进行匹配
    xgod
        5
    xgod  
       2014-06-02 04:15:39 +08:00
    如果正则不算复杂,可以专门写一个处理正则模式的状态机来处理(认真理解正则表达式的话,实际上N条正则是可以合并成一条正则的,是一种状态分支树结构,测试每条路径是否是通路。有索引、寻路效果,读的书不多不知道如何准确表达,嘿),将所有模式合并成一个模式。复杂的话,工作量基本接近于写一个正则引擎了。
    shoumu
        6
    shoumu  
    OP
       2014-06-02 11:43:44 +08:00
    @xgod
    首先,构建这个状态机就不是轻松的事情,其次,无法知道1000条正则能够合并到什么程度,然后,当正则再增多的时候,感觉很麻烦
    cevincheung
        7
    cevincheung  
       2014-06-02 12:12:26 +08:00
    目测是微信平台。

    例如: [搜天气音乐] 是搜[音乐]市的天气呢?还是搜一首名叫[天气]的音乐呢?
    shoumu
        8
    shoumu  
    OP
       2014-06-02 12:28:15 +08:00
    @cevincheung
    不是微信平台
    都有可能,我想问的是怎么快速的判断可用来进行匹配的正则表达式,进而通过匹配看是否触发某种搜索
    cevincheung
        9
    cevincheung  
       2014-06-02 12:36:51 +08:00
    @shoumu
    感觉完全可以把提交的字符串 进行分词,然后按照词语对应的分类权重来决定。

    其实就是一个搜索引擎嘛。

    比如: 提交 [周杰伦稻香] 那么,周杰伦理应属于人物/明星。那么稻香属于植物(个人觉得)/歌曲。那么人物、歌曲、植物。综合搜索。那就是要搜音乐嘛
    shoumu
        10
    shoumu  
    OP
       2014-06-02 13:30:28 +08:00
    @cevincheung
    你可能没有明白我的意思,我的意思是这样的,在搜索引擎普通的搜索外,还针对具体的一些内容(如天气、新闻等)提供了特别的搜索(参考百度阿拉丁、360onebox),但是这些特别的搜索不是任意一个query都能够触发的。现在的一种方式是希望能够通过正则表达式的匹配进行触发,如果有1000个这样的阿拉丁(或onebox)的正则表达式的话,怎么样才能够快速地获取query能够匹配的正则表达式,然后匹配,判断是否触发
    xgod
        11
    xgod  
       2014-06-02 17:43:32 +08:00
    @shoumu 这个要看你正则存在多少共性了,如果不分支中间的共性,你一次匹配一个串,需要执行1000个正则,就算预编译了,性能肯定有瓶颈。
    如果你能够通过1000个正则的前10位字符前缀就可以确定为其中100个正则,那就能让一个字符匹配只执行100个正则操作。
    xgod
        12
    xgod  
       2014-06-02 18:08:17 +08:00
    想了下,有没有一种算法可以实现正则的合并成一种索引树、通路的叶子节点对应正则表达式。将每个正则拆开,生成分支树(类似字典树,但范围值可相互包含,如:交集、并集),然后其它正则生成分支树,不断在在初始分支树上找节点,合并重合的部分设置标记,异同的生成新分支。初想一下类似这样吧,我想不容易实现,估计是不小的工作量。如果能搞定,估计有其它的应用场景了。
    shoumu
        13
    shoumu  
    OP
       2014-06-02 18:52:10 +08:00
    @xgod 现有的想法是对正则表达式建立倒排索引,然后query来了之后,直接通过倒排表查找
    czheo
        14
    czheo  
       2014-06-02 22:17:00 +08:00
    别正则了,换做bayes classifier吧
    shoumu
        15
    shoumu  
    OP
       2014-06-02 22:50:00 +08:00
    @czheo 没明白,具体说说吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4012 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 04:14 · PVG 12:14 · LAX 20:14 · JFK 23:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.