作者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