[go: up one dir, main page]

Bannai et al., 2013 - Google Patents

Converting SLP to LZ78 in almost Linear Time

Bannai et al., 2013

View PDF
Document ID
12752498012460666541
Author
Bannai H
Gawrychowski P
Inenaga S
Takeda M
Publication year
Publication venue
Annual Symposium on Combinatorial Pattern Matching

External Links

Snippet

Given a straight line program of size n, we are interested in constructing the LZ78 factorization of the corresponding text. We show how to perform such conversion in time, where m is the number of LZ78 codewords. This improves on the previously known solution …
Continue reading at pdfs.semanticscholar.org (PDF) (other versions)

Classifications

    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • H03M7/42—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code using table look-up for the coding or decoding process, e.g. using read-only memory
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • H03M7/4031—Fixed length to variable length coding
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • G06F17/30625—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30964—Querying
    • G06F17/30979—Query processing
    • G06F17/30985—Query processing by using string matching techniques
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/21—Text processing
    • G06F17/22—Manipulating or registering by use of codes, e.g. in sequence of text characters

Similar Documents

Publication Publication Date Title
Bille et al. Random access to grammar-compressed strings and trees
Bille et al. Random access to grammar-compressed strings
Sadakane et al. Squeezing succinct data structures into entropy bounds
Gawrychowski Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic
US5585793A (en) Order preserving data translation
Shun et al. Practical parallel lempel-ziv factorization
Bannai et al. Converting SLP to LZ78 in almost Linear Time
Prezza Optimal rank and select queries on dictionary-compressed text
JPS59231683A (en) Data compression system
Apostolico et al. Some theory and practice of greedy off-line textual substitution
Bannai et al. Efficient LZ78 factorization of grammar compressed text
Policriti et al. From LZ77 to the run-length encoded burrows-wheeler transform, and back
Gawrychowski Tying up the loose ends in fully LZW-compressed pattern matching
Sirén Compressed Full-Text Indexes for Highly Repetitive Collections.
BULUŞ et al. A new word-based compression model allowing compressed pattern matching
Prezza Compressed computation for text indexing
Chen et al. E cient Lossless Compression of Trees and Graphs
Maruyama et al. Context-sensitive grammar transform: Compression and pattern matching
Bille et al. Finger search in grammar-compressed strings
Oswald et al. Knowledge engineering perspective of text compression
Tamakoshi et al. From run length encoding to LZ78 and back again
Hirschberg et al. Parsing algorithms for dictionary compression on the PRAM
Tischler Faster average case low memory semi-external construction of the Burrows–Wheeler transform
Giancarlo et al. Optimal partitions of strings: A new class of Burrows-Wheeler compression algorithms
Sakamoto Grammar compression: Grammatical inference by compression and its application to real data