Method of sorting text and string searching

Details Method of sorting text and string searching Method of sorting text and string searching

2007-10-09

2010-06-08

Corrielus, Jean M (Department: 2162)

Data processing: database and file management or data structures

Database schema or data structure

Generating database or data structure

C707S736000, C707S741000, C707S742000, C707S752000, C707S753000, C707S705000

Reexamination Certificate

active

07734671

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.

REFERENCES:
patent: 6535642 (2003-03-01), De Bonet
patent: 6751624 (2004-06-01), Christal et al.
Structuring labeled trees for optimal succinctness, and beyond, IEEE, 2005, Ferragina et al.
An experimental study of an opportunistic index, pp. 269-278, ACM, 2001, Ferragina et al.
An analysis of the Burrows—Wheeler transform, ACM, 2001, pp. 407-430, Giovanni Manzini.
U.S. Appl. No. 10/916,370, filed Aug. 25, 2005, Levin et al.
P. Ferragina et al.; “An Experimental Study of an Opportunistic Index”; Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science; pp. 390-398, 2000.
R. Grossi et al.; “When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications”; Proc. SODA '04, pp. 636-645, 2004.
V. Makinen et al.; “Advs. of Backward Searching—Efficient Secondary Memory and Dist. Impl. of Comp. Suffix Arrays”; Int'l Symp. on Algorithms & Computation; pp. 681-692,2004.
R. Baeza-Yates et al.; “Fast Text Searching for Regular Expressions or Automaton Searching on Tries”; Journal of the ACM, vol. 43, No. 6, Nov. 1996, pp. 915-936.
M. Burrows et al.; “A Block-sorting Lossless Data Compression Algorithm”; Digital Equipment Corporation SRC Research Report, May 10, 1994.
G. Navarro et al.; “Compressed Full-Text Indexes”, ACM Computer Surveys, 2006.
Ho-Leung Chan et al.; “Compressed Indexes for Dynamic Text Collections”, ACM Transactions on Algorithms, vol. 3, No. 2; Article 21; May 2007.

Affiliated with

Also associated with

Rating

Method of sorting text and string searching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of sorting text and string searching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of sorting text and string searching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4174672