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

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

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

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