Method and apparatus for identifying a data sequence related to a given data sequence

• US 6,643,653 B1
• Filed: 06/01/2001
• Issued: 11/04/2003
• Est. Priority Date: 06/01/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Chu, Winson
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US09/873,150
• Time in Patent Office: 886 Days
• Field of Search: 707/2, 707/3, 707/4, 707/102, 707/104.1, 707/10, 707/103.R, 707/203
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories

Abstract

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.

Claims

1. A method of mapping a key sequence of data to a target sequence of data, if the target sequence is stored in a computer readable memory, the method comprising:

retrieving, from a root node of the computer readable memory corresponding to the value of a first datum in said key sequence, an identifier of a first block;

for one or more blocks starting with said first block, wherein each of said blocks is one of a virtual block comprising one or more nodes and a leaf configured to store a sequence of data;

determining whether said block is a virtual block or a leaf;

if said block is a virtual block;

locating a node in said virtual block corresponding to the value of a next datum in said key sequence;

retrieving a home block identifier from said node; and

if said home block identifier identifies said virtual block, accessing a next block identified by a next block identifier of said node; and

if said block is a leaf;

determining whether said leaf contains said target sequence of data;

if said leaf contains said target sequence of data, retrieving said target sequence;

if said leaf does not contain said target sequence, accessing a next block identified by a next block identifier of said leaf if said leaf contains a next block identifier.

2. The method of claim 1, wherein said determining whether said leaf contains said target sequence of data comprises:

determining whether virtual block nodes corresponding to each datum of said key sequence have been accessed;

wherein if virtual block nodes corresponding to each datum of said key sequence have been accessed, then said leaf contains said target sequence of data.

3. The method of claim 1, wherein said determining whether said block is a virtual block or a leaf comprises:

determining whether an identifier by which said block is accessed identifies a block greater than or less than a threshold location in the computer readable memory.

4. The method of claim 3, wherein said identifier by which said block is accessed is one of:

said identifier of said first block if said block is said first block; and

said next block identifier is said block is a block other than said first block.

5. The method of claim 1, wherein said retrieving an identifier of a first block comprises:

accessing a root block of the computer readable memory; and

using said value of the first datum as an offset to identify said root node of said root block.

6. The method of claim 1, wherein nodes of two or more of said virtual blocks are interleaved in the computer readable memory.

7. The method of claim 1, wherein virtual blocks and said leaves are stored contiguously in the computer readable memory.

8. The method of claim 1, wherein said key sequence of data comprises a series of Unicode characters.

9. The method of claim 1, wherein said target sequence of data comprises a normalized Unicode character corresponding to said series of Unicode characters.

10. A computer-implemented method of facilitating retrieval of a target data sequence related to a key data sequence, comprising:

(a) receiving a key data sequence comprising a sequence of data;

(b) for a first datum in said key data sequence, locating a corresponding cell in a root block;

(c) retrieving from said cell an identifier of a virtual block comprising one or more nodes;

(d) locating a node in said virtual block corresponding to a next datum in said key data sequence;

(e) retrieving from said node an identifier of a next block, wherein said next block is one of another virtual block and a leaf;

(f) repeating (d)-(f) until said next block is a leaf; and

(g) if said node from which said identifier of said leaf was retrieved corresponds to the last datum in said key data sequence, retrieving said target data sequence from said leaf.

11. The computer-implemented method of claim 10, further comprising if said node from which said identifier of said leaf was retrieved does not correspond to said last datum in said key data sequence:

(h) retrieving from said leaf an identifier of a next virtual block; and

(i) repeating (d)-(g).

12. The method of claim 10, wherein said locating a corresponding cell comprises using the value of said first datum as an offset in said root block.

13. The method of claim 10, wherein said locating a node comprises using the value of said next datum as an offset into said virtual block.

14. The method of claim 10, wherein said locating a node comprises comparing a home block identifier within said node to said identifier of said virtual block.

15. The method of claim 14, wherein said locating a node further comprises terminating the method if said home block identifier does not match said identifier of said virtual block.

16. The method of claim 10, wherein said retrieving from said node an identifier of one of a next virtual block and a leaf comprises:

retrieving said identifier; and

comparing said identifier to a threshold;

wherein said threshold identifies a memory location separating virtual blocks from leaves.

17. The method of claim 10, wherein said key data sequence is a first series of Unicode characters and said target data sequence is a second series of Unicode characters.

18. The method of claim 17, wherein said first series comprises multiple Unicode characters and said second series comprises a single Unicode character.

19. The method of claim 10, wherein said (f) comprises determining whether said identifier of a next block identifies a block above or below a threshold storage location.

20. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of facilitating retrieval of a target data sequence related to a key data sequence, the method comprising:

(a) receiving a key data sequence comprising a sequence of data;

(b) for a first datum in said key data sequence, locating a corresponding cell in a root block;

(c) retrieving from said cell an identifier of a virtual block comprising one or more nodes;

(d) locating a node in said virtual block corresponding to a next datum in said key data sequence;

(e) retrieving from said node an identifier of a next block, wherein said next block is one of another virtual block and a leaf;

(f) repeating (d)-(f) until said next block is a leaf; and

(g) if said node from which said identifier of said leaf was retrieved corresponds to the last datum in said key data sequence, retrieving said target data sequence from said leaf.

21. A computer readable storage medium containing a data structure configured to facilitate the retrieval of a target data sequence related to a key data sequence, the data structure comprising:

a root comprising one cell for each possible value of a first datum in the key data sequence, including a first cell corresponding to said first datum;

one or more virtual blocks, wherein each said virtual block comprises one or more nodes and each said node is configured to identify one of;

another of said one or more virtual blocks; and

a leaf; and

one or more leaves containing data sequences, including a first leaf containing the target data sequence;

wherein nodes of one of said virtual blocks are interleaved, in the data structure, with nodes of another of said virtual blocks.

22. The computer readable storage medium of claim 21, wherein each node of a virtual block comprises:

a first reference identifying said virtual block; and

a second reference identifying either said other virtual block or said leaf.

23. The computer readable storage medium of claim 21, wherein said first leaf comprises:

a first reference identifying one of said first leaf and a first virtual block;

a size of the target data sequence; and

the target data sequence.

24. The computer readable storage medium of claim 21, wherein the key data sequence comprises a plurality of Unicode characters and the target data sequence comprises a composite Unicode character.

25. The computer readable storage medium of claim 24, wherein said first datum comprises a first byte of a first character of said plurality of Unicode characters.

26. An apparatus for determining whether a first target data sequence corresponding to a first key data sequence is available, comprising:

a root block comprising one entry for each possible value of a first datum of said first key data sequence;

a set of virtual blocks, wherein each of said virtual blocks comprises one or more nodes, and each node comprises;

a first reference configured to identify said virtual block comprising said node; and

a second reference configured to identify either another virtual block or a leaf; and

a set of leaves, wherein each of said leaves is configured to store a target data sequence corresponding to a first key data sequence; and

a processor configured to traverse, from a first entry in said root block corresponding to said first datum, nodes within a subset of said virtual blocks corresponding to subsequent data in said first key data sequence, via said second references, to determine whether one of said leaves contains said first target data sequence.

27. The apparatus of claim 26, wherein each of said leaves comprises:

a size of said target data sequence; and

said target sequence.

28. The apparatus of claim 27, wherein each of said leaves further comprises:

a first reference configured to identify either said leaf comprising said first reference or one of said virtual blocks.

29. The apparatus of claim 26, wherein said root block, said set of virtual blocks and said set of leaves are stored contiguously in a memory.

30. The apparatus of claim 29, wherein one or more nodes of a first virtual block are interleaved with one or more nodes of a second virtual block.