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

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

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

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