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

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

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

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