可以在很小内存中容纳几万甚至几百万个正则表达式的算法

[rockeet febird]

并且只一需要遍扫描，就可以知道匹配了哪个正则表达式，不需要类似 google.re2 中先预扫描得到候选，然后在候选集中匹配。

这样的算法应该有应用价值吧，我现在已经有了思路。

[junyi sun]

我想到了GFW……

2013/5/14 rockeet febird <roc...@gmail.com>

并且只一需要遍扫描，就可以知道匹配了哪个正则表达式，不需要类似 google.re2 中先预扫描得到候选，然后在候选集中匹配。

这样的算法应该有应用价值吧，我现在已经有了思路。

--
 
---
您收到此邮件是因为您订阅了 Google 网上论坛的“TopLanguage”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 pongba+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
 
 

[杨欣]

把这些正则表达式编译成一个或者多个状态机，然后再确定。

--

_______杨欣_______

[Shuai Wang]

多个正则表达式编译成“一个”状态机有办法么。。。？

[rockeet febird]

是要编译成一个 dfa, 但这不是靠说的, 算法很复杂, 目前只实现了简单的语法, 更复杂的语法现在还没有需求，以后有空再实现。不过还有一个问题DFA做不到,就是括号的捕获，现在是匹配以外的需求用其他的正则表达式库来做

[Kula]

这种技术做出来害人的可能性更大吧..我想了半天，只有gfw对这个算法有需求

2013/5/14 rockeet febird <roc...@gmail.com>

是要编译成一个 dfa, 但这不是靠说的, 算法很复杂, 目前只实现了简单的语法, 更复杂的语法现在还没有需求，以后有空再实现。不过还有一个问题DFA做不到,就是括号的捕获，现在是匹配以外的需求用其他的正则表达式库来做

[Super.Jiju(Alvin)]

这个我实现过；

针对url，title，query这样的短文本处理的；

以url的正则表达式来讲，百万个正则表达式，耗内存大概200M左右；

匹配任意一条url的性能大概是每秒5w；

基本思想是：

对一个url数据流，先快速确定它可能的匹配的正则表达式集合，然后再通过正则匹配校对处理；

如果正则表达式集合规范的话，冲突小，那么都不用第二步正则校对了；

有兴趣可以私下联系我；

[Alvinz]

很多场合都需要大量的模板的；各种分类，判断；黑白名单处理等等；

[HaoPeiQiang]

实际上flex不就是这个么？

2013/5/15 Kula <kula...@gmail.com>

--

http://magazine-maker.com

[rockeet febird]

你这个性能每秒50k条，平均每个 url 60字节算，也就 3M

百万个正则只耗费200M内存，平均每个正则200字节，不同之处大多在 url 的 host 部分？

应该跟 google.re2 中的 prefilter 类似吧，先用多模匹配算法找到可能的候选集，然后在候选集中逐个匹配

在 2013年5月15日星期三UTC+8上午8时41分49秒，Alvinz写道：

[rockeet febird]

flex 好像不能应对同一个目标串匹配多个正则的情况吧？

在 2013年5月15日星期三UTC+8上午9时07分16秒，Tinyfool写道：

[HaoPeiQiang]

我觉得看你怎么理解多个正则了，比如我要匹配1000个关键字，写1000个正则，也可以直接flex

2013/5/15 rockeet febird <roc...@gmail.com>

--

http://magazine-maker.com

[rockeet febird]

regex1:  http://.*\.google\.com/.*
regex2:  .*法轮功.*

regex3:  .*奥巴马.*肯尼亚

regex4:  .*[0-9]{4}-[0-9]{2}-[0-9]{2} [0-9]{2}:[0-9]{2}: [0-9]{2}  # 匹配年月日

.....

这个 flex 可以实现吗？

在 2013年5月15日星期三UTC+8上午11时00分01秒，Tinyfool写道：

[HaoPeiQiang]

举例子的时候，不要用敏感词，我正则还不够熟悉，研究下再说

2013/5/15 rockeet febird <roc...@gmail.com>

--

http://magazine-maker.com

[Earthson Lu]

这个和词法分析有什么不同么？所以我觉得Flex自然实现上没有问题。

2013/5/15 rockeet febird <roc...@gmail.com>

--

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Perfection is achieved 

not when there is nothing more to add

 but when there is nothing left to take away

[rockeet febird]

你可以试一下

在 2013年5月15日星期三UTC+8下午12时59分17秒，Earthson写道：

[None_Nobody]

个人觉得这种内存需求大小不是关键，速度才是。

一般来说，不会有极多的正规则出现，否则怎么还叫正规则呢？

像google 那样，用两次也不错。

至于速度么，你可以拼一下FPGA 或者 ASIC  的实现，如果能拼的过，可以进设备了，推荐你去问下华为。



On Wednesday, May 15, 2013 1:44:24 PM UTC+8, rockeet febird wrote:

你可以试一下 but when there is nothing left to take away

[None_Nobody]

在拼华为之前，先拼个 GPU 版本的哈。

 https://github.com/bkase/CUDA-grep.git

[est]

今天我也遇到这个问题了。

比如聚划算每天都有n多促销商品

用户如果厌烦了天天去刷，那么可以采取“关键词订阅”功能，这样就不用人工去看有没有自己感兴趣的，而是机器自动判断。

这个功能现在聚划算也有，但是非常不准。很多关键词捕获不到。

所以每天一个促销商品上架，就需要去跟成兆上亿的关键词去匹配，然后发送消息给响应用户。

这个算法怎么做最有效呢？

大家讨论下思路吧？

感觉应该是逆向的全文索引？呵呵。

2013/5/15 None_Nobody <lyx...@gmail.com>

在拼华为之前，先拼个 GPU 版本的哈。

 https://github.com/bkase/CUDA-grep.git

[jyf]

On Tue, Sep 03, 2013 at 10:21:52AM +0800, est wrote:
> 今天我也遇到这个问题了。
>
> 比如聚划算每天都有n多促销商品
>
> 用户如果厌烦了天天去刷，那么可以采取“关键词订阅”功能，这样就不用人工去看有没有自己感兴趣的，而是机器自动判断。
>
> 这个功能现在聚划算也有，但是非常不准。很多关键词捕获不到。
>
> 所以每天一个促销商品上架，就需要去跟成兆上亿的关键词去匹配，然后发送消息给响应用户。
>
> 这个算法怎么做最有效呢？
>
> 大家讨论下思路吧？
>
> 感觉应该是逆向的全文索引？呵呵。

这种应用 一般不是在商品(文章)入库的时候分词 然后为每个词触发一次订阅检查的事件么？

[est]

> 这种应用 一般不是在商品(文章)入库的时候分词 然后为每个词触发一次订阅检查的事件么？

百万关键词用个for循环去全文搜索？跪了。。。

2013/9/3 jyf <jyf...@gmail.com>

[Chao Zhang]

triedict + 分词

Best Regards,
Zhang Chao

2013/9/3 est <electr...@gmail.com>

--
 
---
您收到此邮件是因为您订阅了 Google 网上论坛“TopLanguage”中的主题。
要退订此主题，请访问 https://groups.google.com/d/topic/pongba/ryu5NRVpv6U/unsubscribe。
要退订此论坛及其所有主题，请发送电子邮件到 pongba+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。

[est]

好吧。分词大家都是知道的。我觉得这个问题关键可以优化的地方在于如何去把海量关键词编译一下。

比如 “手机”，“手机电池” 这两个关键词理论上应该可以在同一个scan里面完成。

本菜CS非常肤浅，所以就搞不懂了。求大牛指点

2013/9/3 Chao Zhang <super...@gmail.com>

[Chao Zhang]

trie 就可以了
分词是保证trie匹配后的边界正确，剔除错误匹配的词

[jyf]

On Tue, Sep 03, 2013 at 11:32:56AM +0800, est wrote:
> > 这种应用 一般不是在商品(文章)入库的时候分词 然后为每个词触发一次订阅检查的事件么？
>
> 百万关键词用个for循环去全文搜索？跪了。。。

大哥 你这个有两个集合 N 和 M
N是新收录的商品的关键词集合
M是订阅的关键词集合

这里的for是指对N的 你想成M了吧？

对于M 难道不是trie么

[est]

> N是新收录的商品的关键词集合

呃，这里似乎应该是全文（原始商品描述），关键词是怎么得来的呢？

2013/9/3 jyf <jyf...@gmail.com>

[jyf]

On Tue, Sep 03, 2013 at 11:46:41AM +0800, est wrote:
> > N是新收录的商品的关键词集合
>
> 呃，这里似乎应该是全文（原始商品描述），关键词是怎么得来的呢？

用分词 另外想起来了 以前在上家公司做应付上级的黑词检测时候 发现两个东西

1, 靠 '|' 来拼接的关键词的正则搜索在几千个待搜索词的情况下比自己用cython实现的trie搜索快

2, 去社区提问时 有人回答可以直接构建自动机来实现一次搜索多个关键词 我功底浅 加上当时工期紧 没有去实现

[Yongwei Wu]

2013/9/3 jyf <jyf...@gmail.com>:

> On Tue, Sep 03, 2013 at 11:46:41AM +0800, est wrote:
>> > N是新收录的商品的关键词集合
>>
>> 呃，这里似乎应该是全文（原始商品描述），关键词是怎么得来的呢？
>
> 用分词 另外想起来了 以前在上家公司做应付上级的黑词检测时候 发现两个东西
>
> 1, 靠 '|' 来拼接的关键词的正则搜索在几千个待搜索词的情况下比自己用cython实现的trie搜索快

Python？Python又不是以性能出名的，怎么跟正则表达式比？

有专门适合搜索多个词的算法的。我以前用过一个为多词优化的Boyer-Moore-Horspool-Sunday算法。不过，这个算法最早是为单个关键字设计的，表达式多到标题的级别恐怕不太适合。我随便用Google搜一下multi
pattern match，第一页就有很合适的资料。

--
Wu Yongwei
URL: http://wyw.dcweb.cn/

[chico CHEN]

这个东西工程上好解决。如果你只是让用户订阅就简单处理。这个一共M个关键词。第一遍处理你现有的所有商品，以后增量的处理你新加的商品。这个做到最后就是几个集合之间的diff，需要去重。PM一般会定义topK,所以这个日后的复杂度很低。。。

但是如果你可以让用户自己新增关键词订阅。这个就比较困难了.

--

---
您收到此邮件是因为您订阅了 Google 网上论坛的“TopLanguage”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 pongba+un...@googlegroups.com。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。

--
Thanks & Best Regards
chico chen
Institute of Software
MSN:cctt1...@163.com

[jyf]

1, 是cython, 另外我说的是几千个的情况 超过几千个以后反而cython的实现快了, 当然很有可能就是我实现的问题

2, 是有多个的 我记得还找到个国人实现的 多词同时搜索类kmp的算法 ，我没什么功底，不知道怎么实现，唯一能想到的就是对待搜索的也构建个trie 然后一边搜 一边剪枝

[rockeet febird]

如果仅仅是多模匹配，我的自动机库中有AC(aho-corasick)自动机，底层的自动机实现可配置，基于双数组的实现匹配最快。几万个字符串时，单线程匹配速度轻轻松松一百兆。支持上千万个模式串也轻轻松松无压力

[jyf]

On Wed, Sep 04, 2013 at 07:02:37AM -0700, rockeet febird wrote:
> 如果仅仅是多模匹配，我的自动机库中有AC(aho-corasick)自动机，底层的自动机实现可配置，基于双数组的实现匹配最快。几万个字符串时，单线程匹配速度轻轻松松一百兆。支持上千万个模式串也轻轻松松无压力

对这个有兴趣 能否借代码来学习下？

[est]

问了下做bioinfo的同学，他们也涉及到类似大规模pattern匹配的问题，有个BLAST算法。还推荐了一本书

《Algorithms on strings, trees and sequences》

2013/9/5 jyf <jyf...@gmail.com>

On Wed, Sep 04, 2013 at 07:02:37AM -0700, rockeet febird wrote:
> 如果仅仅是多模匹配，我的自动机库中有AC(aho-corasick)自动机，底层的自动机实现可配置，基于双数组的实现匹配最快。几万个字符串时，单线程匹配速度轻轻松松一百兆。支持上千万个模式串也轻轻松松无压力

对这个有兴趣 能否借代码来学习下？