%0 Journal Article
%T Efficient multi-pattern matching algorithm based on dual-state coding<br>一种基于双重状态编码的多模式匹配算法
%A DU Wen-chao
%A CHEN Shu-qiao
%A <br>杜文超
%A 陈庶樵
%J 计算机应用研究
%D 2012
%I 
%X Multi-pattern matching algorithm based on finite automata is one of the core technologies on network content filtering and managing. However, with the pattern set becomes larger, it needs too much storage cost. To decrease its space complexity, meanwhile keeping low time complexity, this paper proposed a method based on keywords predisposing and state coding. Keywords predisposing could filter out massive irrelevant matching, it obviously decreased the complexity. And state coding eliminated much failure transitions, could efficiently decrease the storage cost. Theoretical analysis and simulation results show, compared to traditional algorithm based on TCAM, this algorithm can provide a high throughput with a moderate memory requirement.
%K pattern matching
%K nondeterministic finite automata(NFA)
%K ternary content addressable memory(TCAM)
%K state coding<br>模式匹配
%K 非确定性有限自动机（NFA）
%K 三态内容寻址存储器(TCAM)
%K 状态编码
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=A9D9BE08CDC44144BE8B5685705D3AED&aid=F886A295C1E57CC55D67402D8D596537&yid=99E9153A83D4CB11&vid=771469D9D58C34FF&iid=94C357A881DFC066&sid=9D3954EE0D6BC193&eid=58826BCD25BE3ED6&journal_id=1001-3695&journal_name=计算机应用研究&referenced_num=0&reference_num=14