US 7,734,671 B1Granted

Method of sorting text and string searching

AssigneeThe United States of America as represented by the Director, National Security Agency

InventorMichael P. Ferguson

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method of sorting text for memory efficient searching is disclosed. A FM-index is created on received text, and a number of rows are marked. The locations of the marked rows are stored in data buckets as well as the last column of the FM-index, which is stored as a wavelet tree. Data blocks containing the data buckets are created; containing the number of times each character appears in the data block before each data bucket. A header block is created comprising an array of the number of times each character appears in the last column of the FM-index before each data blocks, the location of the end of the data blocks and the location of the end of the data, and appended to the data block. The header and data blocks are stored. The search process loads data buckets into memory as needed to find the required text.

Claims7

Dependent claims

A method of indexing data on a computer, comprising the steps of:

a) receiving data in a computer system, the received data stored in a user-definable storage medium;
b) applying Burrows Wheeler transform to create a Ferragina-Manzini index, having rows and columns;
c) marking a user-definable number of rows of the Ferragina-Manzini index;
d) storing a last column of the Ferragina-Manzini index as a wavelet tree in a user-definable number of data buckets;
e) storing the locations of the user-definable number of marked rows in each user-definable number of data buckets;
f) creating at least one data blocks, the at least one data blocks comprising the user-definable number of data buckets;
g) for each data block, calculating the number of times each character appears in the data block before each user-definable number of data buckets and appending the result to the data block;
h) creating a header block, the header block comprising an array containing the number of times each character appears in the last column of the Ferragina-Manzini index before each at least one data blocks, the location of the end of each at least one data blocks and the location of the end of the data;
i) appending the header block to the at least one data blocks;
j) storing the header block and each at least one data blocks in a user-definable medium;
and
k) if additional data is received in a computer system, returning to step (a), otherwise stopping.

9 more elements

A method of indexing and searching data on a computer, comprising the steps of:

a) receiving data in a computer system, the received data stored in a user-definable storage medium;
b) applying Burrows Wheeler transform to create a Ferragina-Manzini index, having rows and columns;
c) marking a user-definable number of rows of the Ferragina-Manzini index;
d) storing a last column of the Ferragina-Manzini index as a wavelet tree in a user-definable number of data buckets;
e) storing the locations of the user-definable number of marked rows in each user-definable number of data buckets;
creating at least one data blocks, the at least one data blocks comprising the user-definable number of data buckets;
g) for each data block, calculating the number of times each character appears in the data block before each user-definable number of data buckets and appending the result to the data block;
h) creating a header block, the header block comprising an array containing the number of times each character appears in the last column of the Ferragina-Manzini index before each at least one data blocks, the location of the end of each at least one data blocks and the location of the end of the data;
i) appending the header block to the at least one data blocks to create a new index;
j) storing the header block and each at least one data blocks in a user-definable medium;
k) receiving multiple text strings to be searched in the new index;
l) if a user-definable portion of at least one required data bucket is not loaded into memory, loading the user-definable portion of the at least one required data bucket into memory;
m) searching for a first multiple text strings;
and
n) searching for remaining multiple text strings using the user-definable data buckets.

12 more elements

Dependencies are inferred from the claim text.