×

Memory optimized pattern searching

  • US 7,565,380 B1
  • Filed: 03/24/2006
  • Issued: 07/21/2009
  • Est. Priority Date: 03/24/2005
  • Status: Expired due to Fees
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.

View all claims
  • 8 Assignments
Timeline View
Assignment View
    ×
    ×