基于自動機的正則表達(dá)式匹配算法.pdf

1、隨著計算機科學(xué)的不斷發(fā)展，信息數(shù)據(jù)量呈爆炸性增長，給數(shù)據(jù)處理工作帶來了一定的挑戰(zhàn)，用戶的查詢也變的越來越復(fù)雜。由于需要處理的數(shù)據(jù)規(guī)模越來越大，進(jìn)行的搜索也越來越困難，正則表達(dá)式作為一種可定義復(fù)雜查詢的強有力工具為處理文本搜索問題提供了一種靈活而又高效的方法。如今，正則表達(dá)式的應(yīng)用已經(jīng)涉及到很多領(lǐng)域，為查詢處理提供了方便。如何快速高效地響應(yīng)正則表達(dá)式查詢也變得至關(guān)重要。
　　目前，已提出了很多解決正則表達(dá)式匹配的方法。這些方法基本上

2、都是對正則表達(dá)式進(jìn)行在線搜索，即預(yù)先沒有對要查詢的文本做任何處理，根據(jù)其匹配的原理大致可分為三種:基于NFA的正則表達(dá)式匹配;基于DFA的正則表達(dá)式匹配;基于過濾方法的正則表達(dá)式匹配。其中，基于過濾方法的正則表達(dá)式匹配方法目前使用的比較多，查詢性能較高，但是現(xiàn)有的過濾方法只是針對某些結(jié)構(gòu)的正則表達(dá)式效果較明顯，而正則表達(dá)式本身的結(jié)構(gòu)非常復(fù)雜，如何選擇一種更優(yōu)的過濾方法來滿足正則表達(dá)式的查詢需求整體提高正則表達(dá)式的查詢性能是一項很具挑戰(zhàn)性

3、的工作。
　　本文根據(jù)正則表達(dá)式的特點，針對數(shù)據(jù)文件是否預(yù)先被處理這兩種情況，提出了相應(yīng)的正則表達(dá)式在線與離線查詢處理技術(shù)。在未索引數(shù)據(jù)文件的情況下，從正則表達(dá)式中提取出可以很好地代表該表達(dá)式的最佳因子集合，然后根據(jù)最佳因子的個數(shù)來選擇使用單字符串查詢的BM算法或多字符串查詢的CW算法在數(shù)據(jù)文件中找到包含最佳因子的候選字符串，最后在DFA上對候選字符串進(jìn)行驗證。在索引數(shù)據(jù)文件的情況下，本文提出了三種索引結(jié)構(gòu)，基于基本后綴樹的索引、