Wu&Manber;的算法还好了，算是简单的算法了，但是其效率在实际中是非常高的。还有一些算法设计比较复杂的算法，理论上有很多优化的地方，但实际中的效果并不必Wu&Manber;的好，这个应该是和计算机系统结构，像内存，Cache等有关系了，算法只是一部分。

不知道你在网上找到的Python的agrep的实现是怎样的，如果用Python实现这个算法，执行效率肯定会大打折扣，我想用Python包装一下C的模块应该才是可行的。

这个算法也可以应用到中文的多模式匹配中，肯定没问题的，我以前做过一个项目，就是基于这个算法，在2000个模式的背景下，一秒钟可以处理近100M bytes。当然，你需要根据你的具体情况对这个算法进行一些改进，但这种算法对中文肯定也是非常有效的。


-----Original Message-----
From: python-chinese-bounces at lists.python.cn [mailto:python-chinese-bounces at lists.python.cn] On Behalf Of saddle
Sent: Friday, August 05, 2005 12:16 PM
To: python-chinese at lists.python.cn
Subject: Re: [python-chinese]请教一个多模式字符串匹配的问题

看了一下那两篇文章， 感觉agrep确实性能不错（虽然没看明白）
而且网上也能找到python的agrep实现
不过里面的一些假设和设定情况， 中文和英文有不同的情况， 好像直接应用在中
文的多模式匹配有些问题了。

http://www.bio.cam.ac.uk/~mw263/pyagrep.html
http://www.personal.psu.edu/staff/i/u/iua1/python/apse/
两个都是用swig实现的c模块， 看来是用python本身实现的速度要慢的多。

2000个模式每秒接近100M bytes中文匹配是我看到的很优秀的结果了， 不过，这
个主要考虑在内存中的匹配速度吧， 我如果能实现10M左右的速度， 就跟的上硬
盘提供的速度了。
On Fri, 5 Aug 2005 15:46:00 +0800
Robert Chen - 陈儒 <Robert.Chen at zyxel.cn> 撰写于:

Robert.Chen> Wu&Manber;的算法还好了，算是简单的算法了，但是其效率在实际中是非常高的。还有一些算法设计比较复杂的算法，理论上有很多优化的地方，但实际中的效果并不必Wu&Manber;的好，这个应该是和计算机系统结构，像内存，Cache等有关系了，算法只是一部分。
Robert.Chen> 
Robert.Chen> 不知道你在网上找到的Python的agrep的实现是怎样的，如果用Python实现这个算法，执行效率肯定会大打折扣，我想用Python包装一下C的模块应该才是可行的。
Robert.Chen> 
Robert.Chen> 这个算法也可以应用到中文的多模式匹配中，肯定没问题的，我以前做过一个项目，就是基于这个算法，在2000个模式的背景下，一秒钟可以处理近100M bytes。当然，你需要根据你的具体情况对这个算法进行一些改进，但这种算法对中文肯定也是非常有效的。
Robert.Chen> 
Robert.Chen>