Invention Grant
US07482955B2 String matching system and method using bloom filters to achieve sub-linear computation time
有权
字符串匹配系统和方法使用bloom filter实现子线性计算的时间
- Patent Title: String matching system and method using bloom filters to achieve sub-linear computation time
- Patent Title (中): 字符串匹配系统和方法使用bloom filter实现子线性计算的时间
-
Application No.: US11756453Application Date: 2007-05-31
-
Publication No.: US07482955B2Publication Date: 2009-01-27
- Inventor: Po-Ching Lin , Ying-Dar Lin , Yi-Jun Zheng , Yuan-Cheng Lai
- Applicant: Po-Ching Lin , Ying-Dar Lin , Yi-Jun Zheng , Yuan-Cheng Lai
- Agency: Lapus Greiner Lai Corsini, LLC
- Agent Theodore Lapus; Edwin Greiner
- Priority: TW95142250A 20061115
- Main IPC: H03M7/00
- IPC: H03M7/00

Abstract:
A string matching system includes a text string, a plurality of patterns, an m-byte search window and a plurality of Bloom filters, wherein the m-byte search window stands for an m-byte sub-string in the text string under inspection. Every Bloom filter comprises sub-strings of a plurality of patterns. These Bloom filters are queried for membership of the rightmost block in the search window to determine the shift length. The acceleration efficiency of matching many bytes can be achieved simultaneously by shifting the search window for many bytes. Meanwhile, the patterns are stored into an embedded memory through a memory-efficient mechanism —the Bloom filter.
Public/Granted literature
- US20080111718A1 String Matching System and Method Using Bloom Filters to Achieve Sub-Linear Computation Time Public/Granted day:2008-05-15
Information query