作者lg31cm (我住5F)
看板RegExp
标题Re: [问题] 正规表示法处理的很慢
时间Sat Jul 11 03:39:21 2009
※ 引述《ta0306556 (POIL)》之铭言：
: 有一堆资料，我手上有的资讯为 本文和词性
: 那有时候我需要用到词性去做比对，有时候要用到本文做比对
: 但是我都是要结取出本文，而正规表示法又不能够比对字串阵列
: 所以我必须把正规表示法做成下列的样子：
: @严长寿~Nb@，~.*(<value>@.*~.*@.*~.*@.*~.*)@出生~.*
: 我以@作为词的分隔，每个词有两个栏位，分别为：「本文~词性」
: 那我要去做比对的时候，把我要的资讯放上去
: 要忽略的地方改为".*"，因此会有很多个".*"
: 但是这样会让程式几乎跑不动，太慢了
: 请问有没有其他的方法可以改善...
典型的.*滥用，假如你的 regex engine 是 NFA(大部分
regex都是采用NFA)，可以说一定慢到你受不了，因为.*
会一直往後吃字元直到字串结尾或是end of line，接着
因为你的.*後面又有其他字元，regex engine只好不断
backtracking直到找到match的字元为止，假如你要处理的
资料很短还没关系，资料一长一定会让match时间成指数级成长
你的.*还不只一个，engine光是backtracking就够忙的了，当然
慢到让你觉得电脑当了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.124.98.159
1F：推 ta0306556:恩，感谢指教，可是我的问题我想不到更好的方法了～ 07/11 21:51
2F：→ ta0306556:请问有没有什麽其他的方法让我可以解我的问题呢？ 07/11 21:52
3F：推 ta0306556:因为我的每个.*後面不是@就是~我可以设定遇到这两个符号 07/11 23:08
4F：→ ta0306556:就中断的方法吗？ 07/11 23:09
5F：推 MichaelHsin: [^@]* 07/12 00:14
6F：推 ta0306556:对吼，以前用过，我居然忘了...感谢提醒！ 07/12 01:17