这是一个创建于 3822 天前的主题，其中的信息可能已经有所发展或是发生改变。
搜索的时候，来了一个query，为了判断这个query是否满足某种格式以促发某种搜索（如天气：北京），我们采用正则表达式进行匹配。现在假设有1000个类似的正则表达式，问要怎么做才能尽可能小的影响搜索速度？
 |
1
liprais 2014-05-31 05:09:01 +08:00 via iPad
对这一千个正则分类吧，先试区分度大的，然后动态调整
|
 |
2
shoumu OP |
 |
5
xgod 2014-06-02 04:15:39 +08:00
如果正则不算复杂，可以专门写一个处理正则模式的状态机来处理（认真理解正则表达式的话，实际上N条正则是可以合并成一条正则的，是一种状态分支树结构，测试每条路径是否是通路。有索引、寻路效果，读的书不多不知道如何准确表达，嘿），将所有模式合并成一个模式。复杂的话，工作量基本接近于写一个正则引擎了。
|
|
6
shoumu OP @xgod
首先，构建这个状态机就不是轻松的事情，其次，无法知道1000条正则能够合并到什么程度，然后，当正则再增多的时候，感觉很麻烦 |
 |
7
cevincheung 2014-06-02 12:12:26 +08:00
目测是微信平台。
例如： [搜天气音乐] 是搜[音乐]市的天气呢？还是搜一首名叫[天气]的音乐呢？ |
|
8
shoumu OP |
|
9
cevincheung 2014-06-02 12:36:51 +08:00
@shoumu
感觉完全可以把提交的字符串 进行分词，然后按照词语对应的分类权重来决定。 其实就是一个搜索引擎嘛。 比如： 提交 [周杰伦稻香] 那么，周杰伦理应属于人物/明星。那么稻香属于植物(个人觉得)/歌曲。那么人物、歌曲、植物。综合搜索。那就是要搜音乐嘛 |
|
10
shoumu OP @cevincheung
你可能没有明白我的意思，我的意思是这样的，在搜索引擎普通的搜索外，还针对具体的一些内容（如天气、新闻等）提供了特别的搜索（参考百度阿拉丁、360onebox），但是这些特别的搜索不是任意一个query都能够触发的。现在的一种方式是希望能够通过正则表达式的匹配进行触发，如果有1000个这样的阿拉丁（或onebox）的正则表达式的话，怎么样才能够快速地获取query能够匹配的正则表达式，然后匹配，判断是否触发 |
|
11
xgod 2014-06-02 17:43:32 +08:00
@shoumu 这个要看你正则存在多少共性了，如果不分支中间的共性，你一次匹配一个串，需要执行1000个正则，就算预编译了，性能肯定有瓶颈。
如果你能够通过1000个正则的前10位字符前缀就可以确定为其中100个正则，那就能让一个字符匹配只执行100个正则操作。 |
|
12
xgod 2014-06-02 18:08:17 +08:00
想了下，有没有一种算法可以实现正则的合并成一种索引树、通路的叶子节点对应正则表达式。将每个正则拆开，生成分支树（类似字典树，但范围值可相互包含，如：交集、并集），然后其它正则生成分支树，不断在在初始分支树上找节点，合并重合的部分设置标记，异同的生成新分支。初想一下类似这样吧，我想不容易实现，估计是不小的工作量。如果能搞定，估计有其它的应用场景了。
|
 |
14
czheo 2014-06-02 22:17:00 +08:00
别正则了，换做bayes classifier吧
|
Select Language