Python论坛  - 讨论区

标题:RE: [python-chinese] 请教一个多模式字符串匹配的问题

2005年08月05日 星期五 09:20

Robert Chen - 陈儒 Robert.Chen at zyxel.cn
Fri Aug 5 09:20:07 HKT 2005

如果是一般的多模式匹配,有一些很成熟的算法,像你所说的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

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2005年08月05日 星期五 10:31

Wang Kebo mep_ at 163.com
Fri Aug 5 10:31:11 HKT 2005

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

__
Best Regards,
 
Kebo Wang

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2005年08月05日 星期五 10:54

saddle saddle at gmail.com
Fri Aug 5 10:54:51 HKT 2005

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

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


[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2005年08月05日 星期五 12:15

saddle saddle at gmail.com
Fri Aug 5 12:15:32 HKT 2005

看了一下那两篇文章, 感觉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



[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2005年08月05日 星期五 12:19

agile java agile.java at gmail.com
Fri Aug 5 12:19:46 HKT 2005

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

[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

2005年08月05日 星期五 15:08

saddle saddle at gmail.com
Fri Aug 5 15:08:13 HKT 2005

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

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



[导入自Mailman归档:http://www.zeuux.org/pipermail/zeuux-python]

如下红色区域有误,请重新填写。

    你的回复:

    请 登录 后回复。还没有在Zeuux哲思注册吗?现在 注册 !

    Zeuux © 2019

    京ICP备05028076号