Michael P Ferguson

US Patent:

7734671, Jun 8, 2010

Filed:

Oct 9, 2007

Appl. No.:

11/973585

Inventors:

Michael P. Ferguson - Washington DC, US

Assignee:

The United States of America as represented by the Director, National Security Agency - Washington DC

International Classification:

G06F 17/30

US Classification:

707999102, 707736, 707741, 707742, 707752, 707753, 707705

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.