支持正則表達式的文本匹配優(yōu)化算法.pdf

1、正則表達式本身具備描述復雜查詢的能力，能夠通過特定的語法描述一類文本的共同特征。正則表達式因其強大的表達能力和簡潔的語法，使得其計算機語言以及相關(guān)領(lǐng)域中的應用十分廣泛。因此，支持高效的正則表達式的文本匹配技術(shù)也就顯得尤為重要。
　　目前，支持正則表達式的文本匹配的搜索引擎種類很多。但是，基本上所有的正則表達式匹配算法，都采用了自動機理論。也就是說，正則表達式通常先轉(zhuǎn)換成確定（或非確定）有限狀態(tài)自動機，然后利用自動機在文本中進行搜索

2、匹配。由于需要在線地處理正則表達式并構(gòu)建自動機，因此，基本上支持正則表達式的文本匹配算法都是在線的。按照匹配類型不同，支持正則表達式的文本匹配可以分為正則表達式的全局匹配與正則表達式的局部匹配。全局匹配是判斷字符串是否屬于正則表達式表達語言。而局部匹配在判斷字符串中的任何子串是否屬于正則表達式所表達的語言的同時，并同時需要返回子串的位置信息。
　　根據(jù)匹配類型的不同，本文設(shè)計了正則表達式的局部匹配和全局匹配的算法。這兩個算法都支持

3、離線的處理，并設(shè)計了相應的索引結(jié)構(gòu)。對于正則表達式的全局匹配，定義了前-后綴的概念，提出了基于前-后綴的過濾策略，并同時選擇了適用于這種過濾策略的索引結(jié)構(gòu)trie樹對字符串集合構(gòu)建了索引。進而，提出了對正則表達表達式進行化簡方法。首先對查詢的字符串進行化簡，通過計算得到其過濾因子:前-后綴集合。然后對待檢索的字符串集合進行過濾，得到候選字符串集合。最后采用傳統(tǒng)的有限自動機進行驗證候選集合。而對于正則表達式的局部匹配，設(shè)計了基于BWT的索