Efficient storage and search of word lists and other text

• US 7,580,925 B2
• Filed: 04/19/2006
• Issued: 08/25/2009
• Est. Priority Date: 04/19/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Tegic Communications, Inc. (Microsoft Corporation)
• Inventors: Kay, David Jon, Unruh, Erland
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): CHEN, TE Y
• Application Number:
  US11/379,354
• Publication Number:
  US 20070250469A1
• Time in Patent Office: 1,224 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer readable storage medium tangibly embodying machine-readable digital data arranged to facilitate expedited searching. The data includes a plurality of words residing in a table having rows and columns, each word residing in a different row and each letter of the word occupying a different column in that row. Each continuous run of same letters in a column forms an interval. The words are positioned relative to each other to maximize lengths of the intervals, and/or optimize efficiency of compression of the columns by run length encoding.

Claims

1. A computer-implemented method for searching a collection of machine-readable digital data, the method comprising:

a computer receiving a given search word;

the computer evaluating the search word against some or all words in a table, said table having rows and columns, each word residing in a different row and each letter of the word occupying a different column in that row, where the words are stored so as to preserve order of the letters within the words, and where each contiguous run of same letters in a column forms an interval, and such that lengths of the intervals are maximized to facilitate data searching, the evaluating operation comprising;

for each target word in the table to which the search word is being evaluated, comparing, one letter at a time, letters of the search word to corresponding letters of the target word as represented by the columns in the table;

if letters of the search word and the target word satisfy a predetermined matching condition, providing an output representing a successful match, otherwise, skipping ahead in the table to a row where a next interval begins in the column where the comparing operation encountered a letter of the search word failing to match a letter of the target word, and reinitiating the comparing operation;

upon completing the evaluating operation without finding a successful match the computer providing an output representing a failed match.

2. The method of claim 1, where:

the predetermined matching condition includes one of the following;

all letters of the search word matching all letters of the target word, a specified number of letters matching as between the search word and the target word.

3. The method of claim 1, where:

the comparing operation comprises the operations of;

establishing a pointer for each letter of the search word, each pointer identifying a corresponding column in a first row of the table;

comparing letters of the search word to letters at the corresponding pointers;

the skipping operation comprises advancing each pointer to a row in the table where a next interval begins in a column where the comparing operation encountered the letter of the search word failing to match the letter of the target word.

4. The method of claim 3,

the operations further comprising computing how many intervals are present in each column, and determining a low-to-high order of the columns as to intervals present therein;

where the operation of comparing letters of the search word to a letter at the corresponding pointer progresses from pointer to pointer in accordance with the low-to-high order.

5. The method of claim 3,

where the table resides in a compressed form including a data stream comprising, for each column, run length coding of the intervals in that column;

the table further including metadata, said metadata including jump codes, each jump code having a given position in the data stream and identifying a second position in the data stream constituting a relative jump from the given position spanning a predetermined number of table rows;

where the skipping operation comprises;

for each pointer, utilizing the jump codes to advance the pointer a known number of table rows ahead, and thereafter moving any additionally required number of additional intervals to reach a position corresponding to a word in the table where said next interval begins.

6. The method of claim 1, where:

the table further includes metadata identifying rows below which no occurrences of words of various letter lengths occur in the table;

the operations comprise concluding the comparing operation at a row below which there are no remaining occurrences of words with same length in letters as the search word.

7. An article of manufacture, comprising:

a computer readable storage medium tangibly embodying one or more of the following;

(1) a first program of machine-readable instructions executable by a digital processing apparatus to perform operations of searching a collection of machine-readable digital data, (2) a second program of machine-readable instructions executable by the digital data processing apparatus to perform installation of the first program;

where said operations comprise;

receiving a given search word;

evaluating the search word against some or all words in a table, said table having rows and columns, each word residing in a different row and each letter of the word occupying a different column in that row, where the words are stored so as to preserve order of the letters within the words, and where each contiguous run of same letters in a column forms an interval, and such that lengths of the intervals are maximized to facilitate data searching, the evaluating operation comprising;

for each target word in the table to which the search word is being evaluated, comparing, one letter at a time, letters of the search word to corresponding letters of the target word as represented by the columns in the table;

if letters of the search word and the target word satisfy a predetermined matching condition, providing an output representing a successful match, otherwise, skipping ahead in the table to a row where a next interval begins in the column where the comparing operation encountered a letter of the search word failing to match a letter of the target word, and reinitiating the comparing operation;

upon completing the evaluating operation without finding a successful match, providing an output representing a failed match.

where the operations are executable.

8. An apparatus, comprising:

circuitry of multiple interconnected electrically conductive elements configured to perform operations of searching a collection of machine-readable digital data;

where said operations comprise;

receiving a given search word;

evaluating the search word against some or all words in a table, said table having rows and columns, each word residing in a different row and each letter of the word occupying a different column in that row, where the words are stored so as to preserve order of the letters within the words, and where each contiguous run of same letters in a column forms an interval, and such that lengths of the intervals are maximized to facilitate data searching, the evaluating operation comprising;

for each target word in the table to which the search word is being evaluated, comparing, one letter at a time, letters of the search word to corresponding letters of the target word as represented by the columns in the table;

if letters of the search word and the target word satisfy a predetermined matching condition, providing an output representing a successful match, otherwise, skipping ahead in the table to a row where a next interval begins in the column where the comparing operation encountered a letter of the search word failing to match a letter of the target word, and reinitiating the comparing operation;

upon completing the evaluating operation without finding a successful match, providing an output representing a failed match.

9. A data processing apparatus, comprising:

a collection of machine-readable digital data including a plurality of words residing in a table having rows and columns, each word residing in a different row and each letter of the word occupying a different column in that row, where the words are stored so as to preserve order of the letters within the words, and where each contiguous run of same letters in a column forms an interval, and such that lengths of the intervals are maximized to facilitate data searching;

a manager programmed to search the table by performing operations comprising;

receiving a given search word;

evaluating the search word against some or all words in the table, comprising operations of;

for each target word in the table to which the search word is being evaluated, comparing, one letter at a time, letters of the search word to corresponding letters of the target word as represented by the columns in the table;

if letters of the search word and the target word satisfy a predetermined matching condition, providing an output representing a successful match, otherwise, skipping ahead in the table to a row where a next interval begins in the column where the comparing operation encountered a letter of the search word failing to match a letter of the target word, and reinitiating the comparing operation;

upon completing the evaluating operation without finding a successful match, providing an output representing a failed match.

10. A data processing apparatus, comprising:

first computing hardware means for storing a plurality of words residing in a table having rows and columns, each word residing in a different row and each letter of the word occupying a different column in that row, where the words are stored so as to preserve order of the letters within the words, and such that lengths of the intervals are maximized to facilitate data searching, and where each contiguous run of same letters in a column forms an interval;

second computing hardware means for searching the first means by performing operations comprising;

receiving a given search word;

evaluating the search word against some or all words in the table, comprising operations of;

for each target word in the table to which the search word is being evaluated, comparing, one letter at a time, letters of the search word to corresponding letters of the target word as represented by the columns in the table;

if letters of the search word and the target word satisfy a predetermined matching condition, providing an output representing a successful match, otherwise, skipping ahead in the table to a row where a next interval begins in the column where the comparing operation encountered a letter of the search word failing to match a letter of the target word, and reinitiating the comparing operation;

upon completing the evaluating operation without finding a successful match, providing an output representing a failed match.