Text storage and retrieval system and method

• US 5,704,060 A
• Filed: 05/22/1995
• Issued: 12/30/1997
• Est. Priority Date: 05/22/1995
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Michael G. Del Monte
• Inventors: Del Monte, Michael G.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Loomis, John C.
• Application Number:
  US08/445,661
• Time in Patent Office: 953 Days
• Field of Search: 395/148, 395/600, 364/419.13, 364/419.19, 341/51, 341/55, 341/65, 341/76, 341/87, 341/89
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

An improved method and system for storing and retrieving information written as text. The method and system store most words of the text solely in an inverted structure, and the remainder of the text'"'"'s information in an auxiliary structure. The structures can be quickly searched for keyword information, provide highly efficient storage, and can be reconstituted into the original text.

Claims

1. A computer-based system for storing text, comprising:

a lexical parser which divides said text into search terms and all other information;

a word vector table which stores said search terms solely as an inverted structure, wherein each said search term is stored uniquely and each said search term is coupled with a list of its positions within said text; and

a first auxiliary data structure which stores only said other information;

wherein said word vector table and said first auxiliary data structure contain sufficient information substantially to reproduce said text.

2. The system of claim 1, wherein said positions are counted from the beginning of the text, each search term in said text is counted as one position, and each instance of other information between said search terms is counted as one or more positions.

3. The system of claim 1, wherein said text contains words, and said search terms are the approximate lemmas of said words.

4. The system of claim 1, wherein said text contains words, and said search terms are compressed representations of said words.

5. The system of claim 1, wherein said lists of positions are compressed before storage in said word vector table.

6. The system of claim 5, wherein said lists are compressed at least in part by sequential differencing.

7. The system of claim 1, wherein said search terms are stored in said word vector table by reference to a second auxiliary data structure, said second auxiliary data structure storing said search terms.

8. The system of claim 7, wherein said text contains words, and said search terms are the approximate lemmas of said words.

9. The system of claim 7, wherein said text contains words, and said search terms are compressed representations of said words.

10. The system of claim 7, wherein said lists of positions are compressed before storage in said word vector table.

11. The system of claim 10, wherein said lists of positions are compressed at least in part by sequential differencing.

12. The system of claim 1, wherein said text comprises one or more paragraphs having paragraph formats, said formats including at least the margins of said paragraphs, and wherein said paragraph formats are stored in said first auxiliary data structure as a table of said formats and a list of references to said table.

13. A computer-based method for storing text, comprising the steps of:

dividing said text into search terms and all other information;

storing said search terms solely as an inverted structure, wherein each said search term is stored uniquely and each said search term is coupled with a list of its positions within said text; and

storing only said other information in a first auxiliary data structure.

14. The method of claim 13, wherein said text contains words, and said search terms are the approximate lemmas of said words.

15. The method of claim 13, additionally comprising the step of compressing said inverted structure after said first storing step.

16. A computer-based method for compressing a particular string of symbols, comprising the steps of:

providing a large number of strings similar to said particular string;

assigning a value to nearly all substrings contained within said large number of strings, said value being equal to the frequency of occurrence of said substring in said large number of strings, multiplied by the length of said substring;

storing the highest valued substrings in a list;

assigning to each substring in said list a unique fixed-length code; and

replacing each substring contained both within said particular string and said list with the code corresponding to said substring.

18. A computer-based method for storing text, comprising the steps of:

dividing said text into search terms and all other information;

compressing said search terms using the method of claim 16;

storing said search terms solely as an inverted structure, wherein each said search term is stored uniquely and each said search term is coupled with a list of its positions within said text; and

storing said other information in a first auxiliary data structure.

19. A computer-based method for storing text, comprising the steps of:

dividing said text into search terms and all other information;

storing said other information in a first auxiliary data structure;

compressing said search terms using the method of claim 16;

storing said search terms in a second auxiliary data structure; and

storing said search terms in an inverted structure, wherein each said search term is stored uniquely by reference to said second auxiliary data structure, and each said search term is coupled with a list of its positions within said text.

20. A computer-based method for storing text, comprising the steps of:

dividing said text into search terms and all other information;

storing said search terms solely as an inverted structure, wherein each said search term is stored uniquely and each said search term is coupled with a list of its positions within said text;

compressing at least part of said other information using the method of claim 16; and

storing said other information in a first auxiliary data structure.

17. A computer-based method for compressing a particular string of symbols, comprising the steps of:

providing a large number of strings similar to said particular string;

providing a temporary list of substrings contained within said large number of strings;

assigning a value to all substrings in said temporary list, said value being equal to the frequency of occurrence of said substring in said large number of strings, multiplied by the length of said substring;

subtracting from each string in said large number of strings each substring contained in said temporary list;

assigning a value to all remaining substrings in said large number of strings, said value being equal to the frequency of occurrence of said substring in said large number of strings, multiplied by the length of said substring;

replacing all substrings in said temporary list having a value lower than any said remaining substring with the highest valued said remaining substrings;

iterating said assigning, subtracting, assigning, and replacing steps until said temporary list is substantially unchanged from the previous iteration;

assigning to each substring in said temporary list a unique fixed-length code; and

replacing each substring contained both within said particular string and said list with the code corresponding to said substring.