×

Method and apparatus for traversing a compressed deterministic finite automata (DFA) graph

  • US 7,949,683 B2
  • Filed: 11/27/2007
  • Issued: 05/24/2011
  • Est. Priority Date: 11/27/2007
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for traversing a compressed deterministic finite automata-based graph comprising:

  • in a processor;

    traversing nodes in the compressed graph, the nodes being interconnected through valid arcs, by traveling node to node through a valid arc, where a current valid arc of a current node leads to a next node with a walker process to search for an expression in an input stream, the compressed graph having no redundant arcs, and each valid arc of the compressed graph representing a character match in the expression; and

    using a hash value generated from an input character to index in the current node and to read the current valid arc associated with the input character;

    using a hash function associated with the current valid arc to generate a hash value from a next input character; and

    indexing in the next node using the hash value generated from the next input character to read a next valid arc to manage the walker process.

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