基于反向因子的正則表達(dá)式匹配及其優(yōu)化方法.pdf

1、正則表達(dá)式是一種能夠提供復(fù)雜查詢能力的技術(shù)，其通過特定的語法結(jié)構(gòu)來描述出一類文本的共同特征。其強(qiáng)大的表達(dá)能力和簡潔的語法，使得其在各個(gè)領(lǐng)域都被廣泛的應(yīng)用。例如，文本編輯，基因序列匹配，還有shell命令。
　　本文主要研究的是如何有效的在長文本上進(jìn)行正則表達(dá)式查詢。一種比較簡單的方法來實(shí)現(xiàn)正則表達(dá)式查詢就是構(gòu)造正則表達(dá)式的自動(dòng)機(jī)，對(duì)于字符串中的每一個(gè)位置，通過自動(dòng)機(jī)來判斷從該位置開始的子串是否可以被該自動(dòng)機(jī)所接受。但是必須注意到驗(yàn)

2、證過程的計(jì)算代價(jià)是非常大的。這種簡單方法的主要限制在于需要重復(fù)做這種驗(yàn)證過程很多次。有許多方法提出了改進(jìn)的地方來加速匹配過程，大致都是先確定出字符串上的一些候選區(qū)間，然后一個(gè)接一個(gè)的驗(yàn)證這些區(qū)間。這些方法從正則表達(dá)式中提取出一些子串來確定候選區(qū)間出現(xiàn)的位置。每一個(gè)候選區(qū)間都將用一個(gè)或者多個(gè)自動(dòng)機(jī)來驗(yàn)證。即使這些方法可以減少許多驗(yàn)證過程，但是當(dāng)正向因子產(chǎn)生了很多候選區(qū)間的時(shí)候這些方法的效率將變得非常低，尤其當(dāng)文本非常長的時(shí)候更加明顯。

3、r>　　本文提出了一種有效的技術(shù)來提高正則表達(dá)式匹配的性能，通過利用反向因子來過濾掉大多數(shù)的候選區(qū)間，所謂反向因子是指一定不會(huì)出現(xiàn)在答案當(dāng)中的一些子串。反向因子不僅可以用于過濾掉候選區(qū)間，還可以提前結(jié)束自動(dòng)機(jī)的驗(yàn)證。此外，該技術(shù)的一個(gè)主要優(yōu)點(diǎn)是它可以集成到現(xiàn)有的一些技術(shù)當(dāng)中，從而能大幅度的提高現(xiàn)有技術(shù)的性能。本文提出了一種通過利用反向因子來過濾掉候選區(qū)間的算法，然后利用位并行技術(shù)來處理反向因子來進(jìn)一步提高了算法的性能。用位向量表示子串在