支持正則表達(dá)式的文本匹配優(yōu)化算法.pdf

1、正則表達(dá)式本身具備描述復(fù)雜查詢(xún)的能力，能夠通過(guò)特定的語(yǔ)法描述一類(lèi)文本的共同特征。正則表達(dá)式因其強(qiáng)大的表達(dá)能力和簡(jiǎn)潔的語(yǔ)法，使得其計(jì)算機(jī)語(yǔ)言以及相關(guān)領(lǐng)域中的應(yīng)用十分廣泛。因此，支持高效的正則表達(dá)式的文本匹配技術(shù)也就顯得尤為重要。
　　目前，支持正則表達(dá)式的文本匹配的搜索引擎種類(lèi)很多。但是，基本上所有的正則表達(dá)式匹配算法，都采用了自動(dòng)機(jī)理論。也就是說(shuō)，正則表達(dá)式通常先轉(zhuǎn)換成確定（或非確定）有限狀態(tài)自動(dòng)機(jī)，然后利用自動(dòng)機(jī)在文本中進(jìn)行搜索

2、匹配。由于需要在線地處理正則表達(dá)式并構(gòu)建自動(dòng)機(jī)，因此，基本上支持正則表達(dá)式的文本匹配算法都是在線的。按照匹配類(lèi)型不同，支持正則表達(dá)式的文本匹配可以分為正則表達(dá)式的全局匹配與正則表達(dá)式的局部匹配。全局匹配是判斷字符串是否屬于正則表達(dá)式表達(dá)語(yǔ)言。而局部匹配在判斷字符串中的任何子串是否屬于正則表達(dá)式所表達(dá)的語(yǔ)言的同時(shí)，并同時(shí)需要返回子串的位置信息。
　　根據(jù)匹配類(lèi)型的不同，本文設(shè)計(jì)了正則表達(dá)式的局部匹配和全局匹配的算法。這兩個(gè)算法都支持

3、離線的處理，并設(shè)計(jì)了相應(yīng)的索引結(jié)構(gòu)。對(duì)于正則表達(dá)式的全局匹配，定義了前-后綴的概念，提出了基于前-后綴的過(guò)濾策略，并同時(shí)選擇了適用于這種過(guò)濾策略的索引結(jié)構(gòu)trie樹(shù)對(duì)字符串集合構(gòu)建了索引。進(jìn)而，提出了對(duì)正則表達(dá)表達(dá)式進(jìn)行化簡(jiǎn)方法。首先對(duì)查詢(xún)的字符串進(jìn)行化簡(jiǎn)，通過(guò)計(jì)算得到其過(guò)濾因子:前-后綴集合。然后對(duì)待檢索的字符串集合進(jìn)行過(guò)濾，得到候選字符串集合。最后采用傳統(tǒng)的有限自動(dòng)機(jī)進(jìn)行驗(yàn)證候選集合。而對(duì)于正則表達(dá)式的局部匹配，設(shè)計(jì)了基于BWT的索