如果是一般的多模式匹配，有一些很成熟的算法，像你所说的p1, p2都是a开头的，利用自动机做多模式匹配可以利用这一点来加速匹配。

但是自动机算法比较古老了，现在国际上公认的一般情况下效率最好的多模式匹配算法是Sun Wu和Manber在94年提出的一个多模式匹配算法。当然这个算法是针对英文提出的，在模式非常多的情况下，比如上千个的时候，效率的提升尤其显著。如果你要做的是中文的多模式匹配，那么应该根据中文模式的特点修改一下算法。因为中文词和英文词在长度上一般来说相差是比较大的。

这篇paper的名字是：A Fast Algorithm For Multi-Pattern Searching
下面提供下载，不过我没测试过，你试试吧
http://www.cnpaf.net/Forum/read.php?fid=5&tid;=1833&toread;=1


-----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:01 AM
To: python-chinese at lists.python.cn
Subject: [python-chinese] 请教一个多模式字符串匹配的问题

例如从字符串 str1 = 'abcxxxasdf'里面匹配多个模式
p1 = 'aaa', p2='abc', p3= 'xxx'。
用正则表达式应该可以只读取一次str1就可以了，
不过，不知道有更好的优化方法，例如p1,p2都是a开头的，可以例用上用来加速匹
配么
哪位作过类似的东西， 能谈谈看法么。
_______________________________________________
python-chinese list
python-chinese at lists.python.cn
http://python.cn/mailman/listinfo/python-chinese

我的某算法需要解线性规划，寻找GLPK的Python Binding，
目前找到了pulp，可惜pulp即不支持windows，也不支持GLPK的新版本。
Google上也没有发现其他更好的。另外，我对GNU MathProg不熟悉，使用的是API方式
求解。
有谁可以提供一些建议？

__
Best Regards,
 
Kebo Wang

多谢， 已经注册下载了， 看看他的做法

On Fri, 5 Aug 2005 09:20:07 +0800
Robert Chen - 陈儒 <Robert.Chen at zyxel.cn> 撰写于:

Robert.Chen> 如果是一般的多模式匹配，有一些很成熟的算法，像你所说的p1, p2都是a开头的，利用自动机做多模式匹配可以利用这一点来加速匹配。
Robert.Chen> 
Robert.Chen> 但是自动机算法比较古老了，现在国际上公认的一般情况下效率最好的多模式匹配算法是Sun Wu和Manber在94年提出的一个多模式匹配算法。当然这个算法是针对英文提出的，在模式非常多的情况下，比如上千个的时候，效率的提升尤其显著。如果你要做的是中文的多模式匹配，那么应该根据中文模式的特点修改一下算法。因为中文词和英文词在长度上一般来说相差是比较大的。
Robert.Chen> 
Robert.Chen> 这篇paper的名字是：A Fast Algorithm For Multi-Pattern Searching
Robert.Chen> 下面提供下载，不过我没测试过，你试试吧
Robert.Chen> http://www.cnpaf.net/Forum/read.php?fid=5&tid;=1833&toread;=1

看了一下那两篇文章， 感觉agrep确实性能不错（虽然没看明白）
而且网上也能找到python的agrep实现
不过里面的一些假设和设定情况， 中文和英文有不同的情况， 好像直接应用在中
文的多模式匹配有些问题了。
On Fri, 5 Aug 2005 09:20:07 +0800
Robert Chen - 陈儒 <Robert.Chen at zyxel.cn> 撰写于:

Robert.Chen> 如果是一般的多模式匹配，有一些很成熟的算法，像你所说的p1, p2都是a开头的，利用自动机做多模式匹配可以利用这一点来加速匹配。
Robert.Chen> 
Robert.Chen> 但是自动机算法比较古老了，现在国际上公认的一般情况下效率最好的多模式匹配算法是Sun Wu和Manber在94年提出的一个多模式匹配算法。当然这个算法是针对英文提出的，在模式非常多的情况下，比如上千个的时候，效率的提升尤其显著。如果你要做的是中文的多模式匹配，那么应该根据中文模式的特点修改一下算法。因为中文词和英文词在长度上一般来说相差是比较大的。
Robert.Chen> 
Robert.Chen> 这篇paper的名字是：A Fast Algorithm For Multi-Pattern Searching
Robert.Chen> 下面提供下载，不过我没测试过，你试试吧
Robert.Chen> http://www.cnpaf.net/Forum/read.php?fid=5&tid;=1833&toread;=1
Robert.Chen> 
Robert.Chen> 
Robert.Chen> -----Original Message-----
Robert.Chen> From: python-chinese-bounces at lists.python.cn [mailto:python-chinese-bounces at lists.python.cn] On Behalf Of saddle
Robert.Chen> Sent: Friday, August 05, 2005 12:01 AM
Robert.Chen> To: python-chinese at lists.python.cn
Robert.Chen> Subject: [python-chinese] 请教一个多模式字符串匹配的问题
Robert.Chen> 
Robert.Chen> 例如从字符串 str1 = 'abcxxxasdf'里面匹配多个模式
Robert.Chen> p1 = 'aaa', p2='abc', p3= 'xxx'。
Robert.Chen> 用正则表达式应该可以只读取一次str1就可以了，
Robert.Chen> 不过，不知道有更好的优化方法，例如p1,p2都是a开头的，可以例用上用来加速匹
Robert.Chen> 配么
Robert.Chen> 哪位作过类似的东西， 能谈谈看法么。
Robert.Chen> _______________________________________________
Robert.Chen> python-chinese list
Robert.Chen> python-chinese at lists.python.cn
Robert.Chen> http://python.cn/mailman/listinfo/python-chinese
Robert.Chen> _______________________________________________
Robert.Chen> python-chinese list
Robert.Chen> python-chinese at lists.python.cn
Robert.Chen> http://python.cn/mailman/listinfo/python-chinese

正则匹配很吗？我一直在用啊

是说速度么， 正则表达式一般情况下的应用还可以吧， 不过对于过分追求速度的
情况， 可能是慢一些， 在一些python的书里面都有提到re的速度比string的find
要慢很多。
On Fri, 5 Aug 2005 12:19:46 +0800
agile java <agile.java at gmail.com> 撰写于:

agile.java> 正则匹配很吗？我一直在用啊