软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2008年
3期
674-686
,共13页
多模式匹配%中英文混合%哈希%Trie
多模式匹配%中英文混閤%哈希%Trie
다모식필배%중영문혼합%합희%Trie
分析了中英文混合环境下多模式匹配的特点,以及已有多模式匹配算法应用于中英文混合环境时的不足,给出并证明了中英文混合环境下多模式匹配算法的性能定理,提出了一种适合于中英文混合环境的基于线索完全哈希Trie结构的多模式匹配算法.该算法扩展了标准Trie结构,以中英文字符内码为键值构造完全哈希Trie匹配机,并利用模式串之间的关系对Trie匹配机进行线索化.理论分析与实验结果表明,所提出的算法在匹配中无需复杂的哈希运算,不需要回溯匹配指针,在中英文混合环境下能够进行正确、高效的匹配,而且不存在空间膨胀问题,具有较低的空间与时间复杂度,有较大理论与应用价值.
分析瞭中英文混閤環境下多模式匹配的特點,以及已有多模式匹配算法應用于中英文混閤環境時的不足,給齣併證明瞭中英文混閤環境下多模式匹配算法的性能定理,提齣瞭一種適閤于中英文混閤環境的基于線索完全哈希Trie結構的多模式匹配算法.該算法擴展瞭標準Trie結構,以中英文字符內碼為鍵值構造完全哈希Trie匹配機,併利用模式串之間的關繫對Trie匹配機進行線索化.理論分析與實驗結果錶明,所提齣的算法在匹配中無需複雜的哈希運算,不需要迴溯匹配指針,在中英文混閤環境下能夠進行正確、高效的匹配,而且不存在空間膨脹問題,具有較低的空間與時間複雜度,有較大理論與應用價值.
분석료중영문혼합배경하다모식필배적특점,이급이유다모식필배산법응용우중영문혼합배경시적불족,급출병증명료중영문혼합배경하다모식필배산법적성능정리,제출료일충괄합우중영문혼합배경적기우선색완전합희Trie결구적다모식필배산법.해산법확전료표준Trie결구,이중영문자부내마위건치구조완전합희Trie필배궤,병이용모식천지간적관계대Trie필배궤진행선색화.이론분석여실험결과표명,소제출적산법재필배중무수복잡적합희운산,불수요회소필배지침,재중영문혼합배경하능구진행정학、고효적필배,이차불존재공간팽창문제,구유교저적공간여시간복잡도,유교대이론여응용개치.
