| 摘要 |
A method and apparatus for identifying a target data sequence related to a given data sequence, if a related target data sequence exists. Either sequence may be of variable length. Target data sequences are stored in a virtual tree comprising a root, one or more virtual blocks and one or more leaves. Each leaf contains a target data sequence. A cell in the root corresponding to (e.g., having an index matching the value of) the first datum (e.g., a byte, word, character) identifies a virtual block, of variable size, which contains a node corresponding to (e.g., at a position matching the value of) the next datum of the sequence. Each node contains a home block identifier identifying its home virtual block and a next block identifier identifying either another virtual block or a leaf. Virtual blocks may have no empty nodes, and nodes of multiple virtual blocks may be interleaved.
|
