Code string processing system and method using intervals

• US 5,778,371 A
• Filed: 09/12/1995
• Issued: 07/07/1998
• Est. Priority Date: 09/13/1994
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Fujihara, Mutsumi
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/526,872
• Time in Patent Office: 1,029 Days
• Field of Search: 395/600, 395/602, 395/622, 707/203, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A data retrieval system which updates data quickly. A divider determines the first substring and second substring based on the code string from which a key string is retrieved. For each substring, a generator generates the dictionary data showing the correspondence between a trailing string, which is a trailing part of data in the substring, and the start position of the trailing string within the code string. A retriever a trailing string whose leading string is a key string or a part of the key string, based on the dictionary data. A remover removes duplicate trailing strings. When a changer changes the code string, an updater updates dictionary data associated with the substring based on the contents of the change. A first maintaining device maintains the boundary interval at a maximum key length or longer, and a second maintaining device maintains the boundary interval at a specified length or less.

Claims

1. A data processing system comprising:

a binary tree generating means for generating a binary tree representing a range of each interval based on the intervals in a code string including at least one interval,

said binary tree having nodes each of which corresponds to an interval,

the end side of each node being connected to a preceding node corresponding to an interval preceding the interval of the node or to a following node corresponding to an interval following the interval of the node,

each node being assigned a partial interval length which is a sum of the interval length of the node itself and the interval length of at least one node in the end side of the node; and

an interval retrieving means for identifying an interval where a specified position indicating a position within said code string is included,

wherein said interval retrieving means sequentially moves a current node, pointed to by a specified pointer, from said root to said end side, calculates the range of the current node based on the partial interval length of at least one of the current node and said preceding node and said following node directly connected to the end side of the current node, compares the calculated interval with said specified position, moves the current node to the preceding node when the specified position precedes the calculated interval;

moves the current node to the following node when the specified position follows the calculated interval, and identifies that the specified position is included in the current node when the specified position is included in the calculated interval.

2. A data processing system as claimed in claim 1, further comprising an identifying means for identifying an interval corresponding to a specified node which is any given node in said binary tree, wherein the identifying means

moves the current node, pointed to by a pointer, from said specified node toward the parent node, which is a higher-level node, of said current node, one node level at a time, until said root is reached,

adds up the interval length of the node and the partial interval length of the preceding node or the following node of the node each time the current node is moved, depending upon whether a child node which is said current node before movement is said preceding node or said following node,

and identifies an interval corresponding to said specified node by calculating one or both of a left interval length, which is the sum of interval lengths of the nodes preceding said specified node in L-C-R order or a right interval length, which is the total interval length of the nodes following said specified node in L-C-R order.

3. A data processing system as claimed in claim 1, further comprising identifying means for identifying an interval corresponding to a specified node which is any given node in said binary tree, wherein the identifying means moves said specified node to said root by means of splaying.

4. A data processing system as claimed in claim 1, or 2, further comprising a binary tree updating means for updating said binary tree, when said interval is changed, according to the contents of the change.

5. A data processing system as claimed in claim 4, wherein said binary tree updating means comprising:

an interval length changing means for changing said interval length;

a deleting means for deleting said node corresponding to a deleted interval from said binary tree when said interval is deleted; and

an adding means for adding a node corresponding to an added interval when an interval is added.

6. A data processing system as claimed in claim 5, wherein said interval length changing means changes said partial interval length of each node sequentially from said node of said interval, whose length is to be changed, to said root by a changed length.

7. A data processing system as claimed in claim 5, wherein said interval length changing means moves said node of said interval, whose length is to be changed, to said root by means of splaying, and increases or decreases said partial interval length of the node, which is the root, by a changed length.

8. A data processing system as claimed in claim 5, wherein said adding means adds said node corresponding to said interval, which is to be added, to said binary tree,

adjusts the connection sequence of said nodes, and

adjusts said partial interval length of each node.

9. A data processing system as claimed in claim 8, wherein said adding means uses the sum of said interval length of said added node and the partial interval length of said lower-level node of the node as said partial interval length of said added node and, for the nodes on the path from the parent node to which the added node is connected directly as a lower-level node to said root, adds the interval length of the added node to the partial interval length of each of the nodes.

10. A data processing system as claimed in claim 5, wherein said adding means

moves the nodes immediately preceding and following the position, at which a node is to be added, to said root by means of splaying one at a time,

adds said node corresponding to an interval, which is to be added, at the position immediately following said immediately-preceding node or at the position immediately before said immediately-following node, and

adds the interval length of the added node to the partial interval length of said immediately-preceding or immediately-following node or said added node, as necessary.

11. A data processing system as claimed in claim 5, wherein said adding means

adds said node corresponding to said interval, which is to be added, to said binary tree with the interval length of the node being 0,

moves the added node to the root of said binary tree by means of splaying, and

increases the partial interval length of the node, moved to the root, by the interval length of the added interval.

12. A data processing system as claimed in claim 5, wherein said deleting means deletes from said binary tree said node of said interval to be deleted,

adjusts the connection among the nodes, and

adjusts said partial interval length of each node.

13. A data processing system as claimed in claim 5, wherein said deleting means

moves said node corresponding to said interval, which is to be deleted, to the root by means of splaying,

moves the node immediately preceding or following the node, which is to be deleted, to the root by means of splaying,

decreases the partial interval length of said immediately-preceding or immediately-following node, which is the root, by the interval length of said node to be deleted, and

deletes said node to be deleted.

14. A data processing system as claimed in claim 4, further comprising a structure adjusting means for adjusting the structure of said binary tree by changing the connection sequence of said nodes.

15. A data processing system as claimed in claim 14, wherein rotation, double rotation (zig-zig) and double rotation (zig-zag) are used as a structure adjustment procedure for changing the structure while maintaining the sequence of said nodes of said binary tree.

16. A data processing system as claimed in claim 14, wherein said structure adjusting means adjusts said binary tree by means of splaying through which a target node, which is any of said nodes, is moved to said root.

17. A data processing system as claimed in claim 1, wherein said code string is text containing a plurality of lines,

said interval is a line included in the text, and

said binary tree generating means generates a first binary tree representing the sequence of lines with nodes corresponding to one or more lines in the text and a second binary tree representing the sequence of codes in each line with nodes each corresponding to one or more characters on the line.

18. A data processing system as claimed in claim 1, wherein said code string is text containing a plurality of lines of a fixed length, and

said binary tree generating means sets a blank character in a position where no character is present and generates said binary tree by representing each substring of the text as a single node with a character or a blank character occurring consecutively as a label and with the number of consecutive characters as the interval length.

19. A data processing method comprising:

a binary tree generating process for generating a binary tree representing a range of each interval based on the intervals in a code string including at least one interval,

said binary tree having nodes of which corresponds to an interval,

the end side of each node being connected to a preceding node corresponding to an interval preceding the interval of the node or to a following node corresponding to an interval following the interval of the node,

each node being assigned a partial interval length which is the sum of the interval length of the node itself and the interval length of at least one node on the end side of the node, and

an interval retrieving process for identifying an interval where a specified position indicating a position within said code string is included, wherein said interval retrieving process sequentially moves a current node, pointed to by a specified pointer, from said root to said end side, calculates the range of the current node based on the partial interval length of at least one of the current node and said preceding node and said following node directly connected to the end side of the current node, compares the calculated interval with said specified position, moves the current node to the preceding node when the specified position precedes the calculated interval, moves the current node to the following node when the specified position follows the calculated interval, and identifies that the specified position is included in the current node when the specified position is included in the calculated interval.

20. A data processing method as claimed in claim 19, further comprising an identifying process for identifying an interval corresponding to a specified node which is any given node in said binary tree, wherein the identifying process

moves the current node, pointed to by a pointer, from said specified node toward the parent node, which is a higher-level node, of said current node, one node level at a time, until said root is reached,

adds up the interval length of the node and the partial interval length of the preceding node or the following node of the node each time the current node is moved, depending upon whether a child node which is said current node before movement is said preceding node or said following node,

and identifies an interval corresponding to said specified node by calculating one or both of a left interval length, which is the sum of interval lengths of the nodes preceding said specified node in L-C-R order or a right interval length, which is the total interval length of the nodes following said specified node in L-C-R order.

21. A data processing method as claimed in claim 19, or 20, further comprising a binary tree updating process for updating said binary tree, when said interval is changed, according to the contents of the change.

22. A data processing method as claimed in claim 21, wherein said binary tree updating process comprises:

an interval length changing process for changing said interval length;

a deleting process for deleting said node corresponding to a deleted interval from said binary tree when said interval is deleted; and

an adding process for adding a node corresponding to an added interval when an interval is added.

23. A data processing method as claimed in claim 21, further comprising a structure adjusting process for adjusting the structure of said binary tree by changing the connection sequence of said nodes.

24. A data processing system comprising:

a binary tree generating means for generating a binary tree representing a range of each interval based on the intervals in a code string including at least one interval, said binary tree having nodes each of which corresponds to an interval, each node being assigned a partial interval length which is the sum of the interval lengths of all the nodes included in the subtree whose root is the node including the node itself, and

an interval retrieving means for identifying an interval where a specified position indicating a position within said code string is included, wherein said interval retrieving means sequentially moves a current node, pointed to by a specified pointer, from said root to said end side, calculates the range of the current node based on the partial interval length of at least one of the current node and said preceding node and said following node directly connected to the end side of the current node, compares the calculated interval with said specified position, moves the current node to the preceding node when the specified position precedes the calculated interval, moves the current node to the following node when the specified position follows the calculated interval, and identifies that the specified position is included in the current node when the specified position is included in the calculated interval.

25. A data processing method comprising:

a binary tree generating process for generating a binary tree representing a range of each interval based on the intervals in a code string including at least one interval, said binary tree having nodes each of which corresponds to an interval, each node being assigned a partial interval length which is the sum of the interval lengths of all the nodes included in the subtree whose root is the node including the node itself, and

an interval retrieving process for identifying an interval where a specified position indicating a position within said code string is included, wherein said interval retrieval process sequentially moves a current node, pointed to by a specified pointer, from said root to said end side, calculates the range of the current node based on the partial interval length of at least one of the current node and said preceding node and said following node directly connected to the end side of the current node, compares the calculated interval with said specified position, moves the current node to the preceding node when the specified position precedes the calculated interval, moves the current node to the following node when the specified position follows the calculated interval, and identifies that the specified position is included in the current node when the specified position is included in the calculated interval.