EFFICIENT STORAGE AND SEARCH OF WORD LISTS AND OTHER TEXT

• US 20090037371A1
• Filed: 10/01/2008
• Published: 02/05/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: UNRUH, Erland, Kay, David Jon
• Granted Patent: US 8,204,921 B2
• Time in Patent Office: Days
• 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 method for storing machine-readable digital data to facilitate expedited searching, comprising operations of:

establishing a table having rows and columns;

in the table, storing machine-readable digital data comprising a plurality of words, each word residing in a different row and each letter of the word occupying a different column in that row, and where each contiguous run of same letters in a column forms an interval;

the storing operation including an act of establishing relative positioning of words in the table according to one of the following;

maximizing lengths of the intervals, optimizing efficiency of compression of the columns by run length encoding.

2. The method of claim 1, the operations further comprising:

compressing the table by forming, for each column, a data stream comprising run length coding of the intervals in that column.

3. The method of claim 2, the operations further comprising:

supplementing the table with metadata including jump codes, each jump code having a first position in the data stream and prescribing a specified number of table rows and a second position in the data stream, where data in the data stream between the first and second positions represents a span of the specified number of table rows.

4. The method of claim 1, the operations further comprising:

supplementing the table with metadata identifying rows below which no occurrences of words of various letter lengths occur in the table.

5. The method of claim 1, where the act of establishing relative positioning of words in the table comprises:

starting from the table being substantially empty, adding words from a source list to the table by performing operations comprising;

determining similarity between each word in the source list and a last word in the table, and adding a most similar word of the source list to the table after the last word;

repeating the determining operation for each word in the source list.

6. The method of claim 1, where the letters comprise alphabetic characters, numbers, symbols, and punctuation marks.

7. A computer readable data product manufactured by the following process:

establishing a table having rows and columns;

in the table, storing machine-readable digital data comprising a plurality of words, each word residing in a different row and each letter of the word occupying a different column in that row, and where each contiguous run of same letters in a column forms an interval;

the storing operation including an act of establishing relative positioning of words in the table according to one of the following;

maximizing lengths of the intervals, optimizing efficiency of compression of the columns by run length encoding.

8. An article of manufacture, comprising:

a computer readable storage medium tangibly embodying machine-readable digital data arranged to facilitate expedited searching;

the machine-readable digital data comprising;

a plurality of words, each word residing in a different row and each letter of the word occupying a different column in that row, and where each contiguous run of same letters in a column forms an interval;

where words in the table are relatively positioned according to one of the following;

maximizing lengths of the intervals, optimizing efficiency of compression of the columns by run length encoding.