正則表達(dá)式匹配算法研究.pdf

1、正則表達(dá)式匹配是從文本中找出與給定正則表達(dá)式匹配的所有字符序列的起始和結(jié)束位置，該操作在文本編輯、生物信息學(xué)、模式識別等領(lǐng)域有著重要的應(yīng)用。通過分析發(fā)現(xiàn)現(xiàn)存方法需要對文本建立后綴樹索引，而本文后綴樹索引空間大，建樹過程復(fù)雜且查找正則表達(dá)式的前綴、后綴位置信息時需要遍歷整個后綴樹效率較低。為了提高匹配效率，本文從以下幾個方面對正則表達(dá)式匹配問題進(jìn)行了深入研究：
　　首先，提出了基于數(shù)組索引的訪問策略，該策略先查詢正則表達(dá)式中一定出現(xiàn)

2、的字符序列的位置，然后根據(jù)這些位置進(jìn)行對正則表達(dá)式左右匹配，最后找出能夠與此正則表達(dá)式匹配的所有位置，從而避免遍歷整個后綴樹，并提出了基于上述策略的正則表達(dá)式匹配算法-Matc h算法。
　　其次，針對在正則表達(dá)式的匹配階段存在的冗余計(jì)算問題，提出了新的匹配方法，即依照出現(xiàn)次數(shù)最少的字符序列位置進(jìn)行左右匹配；根據(jù)左右匹配的不同限制以及以前方法的過濾思想提出了兩種過濾策略，即左右匹配的過濾策略和基于消極因子的過濾策略，進(jìn)一步減少了候