计算机应用研究
計算機應用研究
계산궤응용연구
APPLICATION RESEARCH OF COMPUTERS
2012年
3期
950-954
,共5页
正则表达式%确定有限自动机%布鲁姆过滤器%比特向量%确定字符串%匹配概率%匹配速率
正則錶達式%確定有限自動機%佈魯姆過濾器%比特嚮量%確定字符串%匹配概率%匹配速率
정칙표체식%학정유한자동궤%포로모과려기%비특향량%학정자부천%필배개솔%필배속솔
针对确定有限自动机(DFA)的正则表达式匹配技术存在状态膨胀和一次状态转移只能处理单个字符的问题,提出了一种基于布鲁姆过滤器的正则表达式匹配算法.该算法将正则表达式中的每个确定字符串组成DFA的一个状态,添加比特向量完成匹配过程,并且在一次状态转移中根据确定字符串的匹配结果达到处理多个字符的目的.实验分析表明该算法有效降低了DFA状态的膨胀,提高了匹配速率.
針對確定有限自動機(DFA)的正則錶達式匹配技術存在狀態膨脹和一次狀態轉移隻能處理單箇字符的問題,提齣瞭一種基于佈魯姆過濾器的正則錶達式匹配算法.該算法將正則錶達式中的每箇確定字符串組成DFA的一箇狀態,添加比特嚮量完成匹配過程,併且在一次狀態轉移中根據確定字符串的匹配結果達到處理多箇字符的目的.實驗分析錶明該算法有效降低瞭DFA狀態的膨脹,提高瞭匹配速率.
침대학정유한자동궤(DFA)적정칙표체식필배기술존재상태팽창화일차상태전이지능처리단개자부적문제,제출료일충기우포로모과려기적정칙표체식필배산법.해산법장정칙표체식중적매개학정자부천조성DFA적일개상태,첨가비특향량완성필배과정,병차재일차상태전이중근거학정자부천적필배결과체도처리다개자부적목적.실험분석표명해산법유효강저료DFA상태적팽창,제고료필배속솔.
