Patent Document ID: 8866644
Application ID: 13451877

Base Claim:
1. A method for detecting a known arbitrary length bit string from a stream of input bits, using a system including a first trie matching circuit storing a first trie data structure, the first stored trie data structure storing a representation of hashes of chunks of n arbitrary length bit strings, including L hierarchical levels, 0 through (L−1), each of the hierarchical L=i levels having 2 L nodes, each of the 2 L nodes of a level having a data bit map representing hashes of chunks of the arbitrary length bit strings, and a next node bit map representing a partition, of chunks of arbitrary length bit strings corresponding to the node, across two nodes at the next hierarchical level of the trie, corresponding to the node; a first string matching circuit storing, for each of the chunks of arbitrary length bit strings, the chunk of the arbitrary length bit string, or a pointer thereto, in a memory location addressed by a concatenation of values from bit locations of the next node bit maps to which the chunk of arbitrary length bit string was hashed; a second trie matching circuit storing a second trie data structure, the second stored trie data structure storing representations of multi-chunk portions of n arbitrary length bit strings, including L hierarchical levels, 0 through (L−1), each of the hierarchical levels L=i having 2 i nodes, each of the 2 i nodes of a level having a data bit map representing hashes of representations of multi-chunk portions of the n arbitrary length bit strings, and a next node bit map representing a partition, of representations of multi-chunk portions of the n arbitrary length bit strings corresponding to the node, across two nodes at the next hierarchical level of the trie, corresponding to the node; a second string matching circuit storing, for each of representations of multi-chunk portions of the n arbitrary length bit strings, the representations of multi-chunk portions of the n arbitrary length bit strings, or a pointer thereto, in a memory location addressed by a concatenation of values from bit locations of the next node bit maps to which the representations of multi-chunk portions of the n arbitrary length bit strings was hashed, the method comprising: a) accepting chunks of the stream of input bits; b) applying the chunks, sequentially, to the first trie matching circuit to determine, for each chunk, whether or not a first match exists; c) if the first trie matching circuit determines that a first match exists, then 1) providing, using a unique identifier of the detected chunk, a string corresponding to the unique identifier, to the first single string matching circuit to determine whether or not a string match exists, 2) if it is determined that a string match exists, then determining, with the second trie matching circuit, whether a second match exists, 3) if the second trie matching circuit determines that a second match exists, then A) providing, using another unique identifier of the detected identifier and any previously detected identifiers, a string corresponding to the other unique identifier, to the second single string matching circuit to determine whether or not a second string match exists, B) if it is determined that a second string match exists, then repeating acts (a) and (b), wherein the second trie matching circuit operates on identifiers corresponding to two sequential chunks.

---

Claim 8:
8. The method of claim 1 wherein the n arbitrary length bit strings are nucleotide sequences.