正則表達式匹配算法研究.pdf

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

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