Method and system for compression indexing and efficient proximity search of text data

• US 20050198070A1
• Filed: 03/08/2004
• Published: 09/08/2005
• Est. Priority Date: 03/08/2004
• Status: Active Grant

• Current Assignee: Marpex Incorporated
• Original Assignee: Marpex Incorporated
• Inventors: Lowry, Douglas B.
• Granted Patent: US 7,433,893 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• 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

A system and method of compression indexing and efficient proximity search of text data permits high speed search featuring ranking the relevance of search results according to closeness of desired terms within each portion of text found. The system includes (a) preparing target text, (b) creating a “compression index ebook”, (c) browsing in a compression index ebook, and (d) searching in a compression index ebook. To create the compression index, the method includes the steps of selecting target text, identifying tokens, such as words and punctuation strings, wherein each of the tokens has a frequency. The frequencies of each token are counted. Tokens are ranked from highest frequency to lowest frequency. The frequencies are compressed. The next step is assigning positions to each token frequency and compressing the positions to form a compression index ebook, which is stored in random access memory to eliminate disk seeks during browsing and searching.

Claims

1. A method of compression indexing, comprising the steps of:

selecting at least one data file;

identifying tokens, each of the tokens having a frequency;

counting the frequency of each token;

calculating parameters;

ranking the tokens from highest frequency to lowest frequency;

compressing the frequencies;

assigning a position to each instance of each token;

compressing the positions; and

,

aggregating tokens, frequencies, parameters, and positions to form a compression index ebook.

2. The method of claim 1, wherein the token is a word.

3. The method of claim 1, wherein the token is a string of punctuation characters.

4. The method of claim 1, wherein the token is a markup tag with no blanks.

5. The method of claim 1, further comprising the step of:

searching the compression index ebook.

6. The method of claim 5, wherein searching occurs in random access memory.

7. The method of claim 6, wherein the step of searching the compression index ebook is performed without disk seeks.

8. The method of claim 1, wherein the step of compressing the positions to form a compression index ebook, the position of the first instance of each token is absolute, and the position of each subsequent instance of the same token is relative to the preceding position.

9. The method of claim 1, wherein the compression index ebook comprises:

an exhaustive index of every token, the compression index ebook adapted to derive closeness-of-fit measures, the compression index ebook also adapted to reproduce any portion of original text for display.

10. The method of claim 1, further comprising the steps of:

reconstituting a portion of the data file; and

displaying the portion of the data file on a screen.

11. The method of claim 10, wherein compressed positions of the data file point to a compressed text random access memory file, the step of reconstituting the data file further comprising the steps of:

a. loading the compressed text RAM file;

b. selecting a domain to display, the domain being a portion of the data file, the domain having a starting point and an ending point;

c. decompressing successive integers;

d. determining positions of the tokens in the token list;

e. extracting the tokens from the token list; and

f. writing the tokens to the screen.

12. The method of claim 11, further comprising the step of:

repeating steps c-f until the ending point of the domain is reached.

13. The method of claim 11, wherein the selected domain is part of a domains list, the domains list having a plurality of domains, the domains list having the starting point and the ending point of each domain.

14. The method of claim 5, further comprising the step of:

ranking search results by relevance, wherein relevance is determined by the closeness of fit of search terms, headings, and frequencies of search terms.

15. The method of claim 1, further comprising the step of:

browsing the compression index ebook, wherein an associated user is able to sequentially read content of the compression index ebook starting at any point.

16. A method for using a compression index ebook, comprising the steps of:

a. creating the compression index ebook having the steps of;

(i) providing target text, the target text being at least one data file, the target text having tokens, the tokens having frequencies;

(ii) accumulating parameters;

(iii) building a list of all tokens represented in the target text, together with their respective frequencies;

(iv) sorting the list in order of declining token frequencies;

(v) accumulating positions data of each instance of each token; and

(vi) combining steps i-v into the compression index ebook;

b. browsing and searching the compression index ebook.

17. The method of claim 16, wherein browsing and searching occurs on a personal computer.

18. The method of claim 16, wherein browsing and searching is server based over an Internet.

19. The method of claim 16, wherein the step of accumulating parameters comprises:

accumulating parameters and token frequencies on a single pass through the at least one data file, the data file having lightly marked up text, wherein the single pass through of the at least one data file of lightly marked up text comprises input for the compression index ebook.

20. The method of claim 19, wherein the step of building a list of all tokens represented in the target text, together with their respective frequencies further comprises the steps of:

sorting all tokens in order of declining frequency;

creating a temporary parameters file to facilitate passing parameters between successive states of the method to create the compression index ebook;

parsing the target text as a means for creating the token list, each of the tokens having a flag byte preceding the token and a null byte following the token; and

compressing and outputting the frequencies of tokens.

21. The method of claim 20, wherein the step of accumulating positions data further comprises the steps of:

reserving a block of random access memory to accumulate positions data;

reparsing the entire data file;

recording the position of all tokens in the random access memory block; and

compressing and outputting the positions data, wherein the position of the first instance of each token is absolute, and the position of each subsequent instance of the same token is relative to the preceding position.

22. The method of claim 21, wherein the step of combining steps (i)-(v) into one compression index ebook, further comprises the steps of:

outputting public parameters as plain text at a beginning of the compression index ebook;

outputting compressed private parameters; and

appending the tokens, frequencies and positions to complete the compression index ebook.

23. The method of claim 21, wherein numeric values assigned to successive tokens from the data file are compressed and successively appended to create a compressed text random access memory file, wherein the random access memory file is computationally equivalent to the target text such that the positions within this compressed text random access memory file are used as the position values of successive tokens.

24. The method of claim 16, wherein positions are compressed, compressed positions of the data file point to a compressed text random access memory file, the method further comprising the step of reconstituting the data file to browse and search the compression index ebook comprising the steps of:

a. loading the compressed text RAM file;

b. selecting a domain to display, the domain being a portion of the data file, the domain having a starting point and an ending point, wherein the selected domain is part of a domains list, the domains list having a plurality of domains, the domains list having the starting point and the ending point of each domain;

c. decompressing successive integers;

d. determining positions of the tokens in the token list;

e. extracting the tokens from the token list;

f. writing the tokens to the screen; and

g. repeating steps c-f until the ending point of the domain is reached.

25. The method of claim 16, wherein after searching the compression index ebook, search results are ranked by relevance.

26. The method of claim 25, wherein searching the compression index ebook comprises the step of:

scoring for closeness of fit of search terms by measuring the number of waste words that intervene between the first and last term found within a domain, and subtracting the count of waste words from the maximum allowable value.

27. The method of claim 26, wherein searching the compression index ebook comprises the step of:

scoring for headings.

28. The method of claim 27, wherein searching the compression index ebook comprises the step of:

scoring for frequencies of search terms.

29. The method of claim 27, further comprising the step of:

ranking search results from the domain with the highest score to lowest score, wherein scores equal the sum of closeness of fit, frequency of search terms in heading and frequency of terms in the domain, wherein search results are displayed as a list of hits arranged in order of closeness of fit and with frequency of occurrence in headings and body controlling the ranking when the number of waste words is the same for multiple domains.

30. A computer readable medium containing instructions for controlling a computer system to perform a method, the method comprising the steps of:

selecting at least one file;

identifying tokens, each of the tokens having a frequency;

counting the frequency of each token;

calculating parameters;

ranking the tokens from highest frequency to lowest frequency;

compressing the frequencies;

assigning a position to each instance of each token;

compressing the positions;

aggregating tokens, frequencies, parameters, and positions to form a compression index ebook; and

browsing and searching the compression index ebook.

31. An apparatus, comprising:

means for selecting at least one file;

means for identifying tokens, each of the tokens having a frequency;

means for counting the frequency of each token;

means for calculating parameters;

means for ranking the tokens from highest frequency to lowest frequency;

means for compressing the frequencies;

means for assigning a position to each instance of each token;

means for compressing the positions; and

means for aggregating tokens, frequencies, parameters, and positions to form a compression index ebook; and

browsing and searching the compression index ebook.