Memory optimized pattern searching
First Claim
Patent Images
1. A method performed by a processor for constructing a finite state machine (FSM) of searchable strings, the method comprising:
- receiving a set of searchable strings, each of which comprises a number of characters;
forming a hierarchical trie structure using the set of searchable strings, wherein the forming comprises storing the characters of the set of searchable strings within a plurality of child nodes descending from a root node of the trie structure; and
constructing a FSM using the hierarchical trie structure, wherein the constructing comprises forming a plurality of state entries of the FSM, each comprising a substring whose length is bound by a maximum size limitation placed on a memory device for storing the FSM, wherein the constructing comprises;
traversing the hierarchical trie structure node by node;
maintaining a substring in the FSM by retaining the character stored at a current node if (a) the current node has more than one child node immediately descending therefrom, (b) the current node has less than one child node immediately descending therefrom, or (c) the current node comprises a last character of a searchable string; and
forming a new substring in the FSM by concatenating the character stored at the current node and a parent node immediately preceding the current node to form a compressed node embodying the characters of the current node and the parent node if a length of the new substring is less than or equal to the maximum size limitation placed on the memory device, wherein a said each state entry of the FSM corresponding to the compressed node includes only one failure transition.
8 Assignments
0 Petitions
Accused Products
Abstract
A method of modifying a finite state machine (FSM) wherein the FSM is accessed by a plurality of entries, with each entry comprised of a substring and a next-state pointer, and the FSM is modified so that each entry comprises a length, which is less than or equal to a maximum size boundary placed on a memory device configured for storing the FSM.
-
Citations
9 Claims
-
1. A method performed by a processor for constructing a finite state machine (FSM) of searchable strings, the method comprising:
-
receiving a set of searchable strings, each of which comprises a number of characters; forming a hierarchical trie structure using the set of searchable strings, wherein the forming comprises storing the characters of the set of searchable strings within a plurality of child nodes descending from a root node of the trie structure; and constructing a FSM using the hierarchical trie structure, wherein the constructing comprises forming a plurality of state entries of the FSM, each comprising a substring whose length is bound by a maximum size limitation placed on a memory device for storing the FSM, wherein the constructing comprises; traversing the hierarchical trie structure node by node; maintaining a substring in the FSM by retaining the character stored at a current node if (a) the current node has more than one child node immediately descending therefrom, (b) the current node has less than one child node immediately descending therefrom, or (c) the current node comprises a last character of a searchable string; and forming a new substring in the FSM by concatenating the character stored at the current node and a parent node immediately preceding the current node to form a compressed node embodying the characters of the current node and the parent node if a length of the new substring is less than or equal to the maximum size limitation placed on the memory device, wherein a said each state entry of the FSM corresponding to the compressed node includes only one failure transition. - View Dependent Claims (2, 3)
-
-
4. A method performed by a processor for forming a finite state machine (FSM) of searchable strings that each comprises a number of characters, the method comprising:
-
forming a hierarchical trie structure embodying the searchable strings, wherein the characters of the searchable strings are stored within a plurality of branches of sequential nodes extending from a root node of the trie structure; traversing the hierarchical trie structure to sequentially select the nodes therein; for each selected node, selectively concatenating the character stored at the selected node and the character stored at a child node immediately descending from the selected node to form a compressed node embodying the characters at the selected node and the child node if (a) the selected node is not a branch node that has more than one child node immediately descending therefrom and (b) the selected node is not an output node that comprises a last character of one of the searchable strings; and constructing the FSM, by the processor, using the hierarchical trie structure including the compressed nodes, wherein the FSM includes a plurality of state entries each corresponding to an associated node of the trie, and wherein the state entry for each compressed node includes only one failure transition. - View Dependent Claims (5, 6)
-
-
7. A system including a search engine for searching an input string for a plurality of searchable strings that each comprises a number of characters, the search engine comprising:
-
means for forming a hierarchical trie structure embodying the searchable strings, wherein the characters of the searchable strings are stored within a plurality of branches of sequential nodes extending from a root node of the trie structure; means for traversing the trie structure to sequentially select the nodes therein; means for selectively concatenating the character stored at each selected node and the character stored at a child node immediately descending from the selected node to form a compressed node embodying both characters if (a) the selected node is not a branch node that has more than one child node immediately descending therefrom and (b) the selected node is not an output node that comprises a last character of one of the searchable strings; and means for constructing a Finite State Machine (FSM) using the hierarchical trie structure including the compressed nodes, wherein the FSM includes a plurality of state entries each corresponding to an associated node of the trie, and wherein the state entry for each compressed node includes only one failure transition. - View Dependent Claims (8, 9)
-
Specification