在用多個正則表達式匹配創建DFA的過程中,有壹個DFA的Union運算。在這個過程中,如果狀態膨脹失控,就需要以某種方式對正則表達式集合進行分組,以便抑制這種狀態膨脹。分組後,將生成多個DFA。但是,為了應用程序接口的方便和統壹,如果將這些DFA揉成壹個DFA對象,每個DFA都需要不同的初始狀態(根)。
提高DFA聯盟的績效
具有相同尾部的多個DFA
如果使用adfa_build創建了幾個不同的ADFA(非循環DFA,非循環DFA ),那麽在稍後的時間點合並這些adfa仍然是DFA的聯合操作。在這種情況下,NFA到DFA過程中的狀態擴展總是線性的,即使如此,NFA到DFA過程中仍然需要大量的內存。
雖然我之前也想過DFA包含多個初態(根)的可能性,但壹直沒有深入思考過。這次經過仔細思考,我發現(所有的)DFA最小化算法理論上都沒有必要局限於單個DFA,不管有多少根,算法都可以正常工作!唯壹需要註意的是,最小化前後的根在某些應用中需要相互對應。
在最小化之前,多個DFA可以完全獨立。唯壹的要求是所有DFA的狀態ID屬於同壹個ID空間,這非常簡單。在工程上可以用同壹個DFA對象來表示。對於分離的DFA對象,只需要實現壹個DFA包裝器來重新映射多個分離的DFA的狀態id。
這樣,執行多根DFA最小化的所有準備工作就完成了。最小化完成後,這些DFA會* *共享壹些相同的尾部,但壹般情況下,頭部不會* * *;但在極端情況下,比如DFA1是DFA2的子集,那麽從DFA2的根可以到達DFA1的根,整個DFA1就完全享受到了。
執行DFA聯合
將所有的尾部最小化,然後通過將NFA變換為DFA來進行最小化,從而大大減少了NFA變換為DFA的時間和內存消耗。
匹配多個正則表達式的動態DFA
具體請參考多正則表達式匹配中的動態DFA算法。
主要有兩點:
多個子DFA使用regex_build中的最小化算法來獲得具有多個根和壹個尾的DFA。
動態DFA是多個DFA的並集,因為並集的完整DFA無法構造(狀態指數爆炸),而並集的部分DFA是從DFA並集的NFA動態構造的。
在使用正則表達式集合的並集的動態DFA來搜索特定的匹配正則表表達式ID之後,從ID的根中提取括號。
實現
在實現這個概念的過程中,我對我的adfa_minimize進行了重構和優化。