Compressed matching in dictionaries

DOI10.3390/A4010061MaRDI QIDQ1736479zbMATH OpenOpenAlexFDO

Authors Shmuel T. Klein, Dana Shapira

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a4010061

zbMATH Keywords

compressed matchingdictionariesFibonacci codesHuffman codesIR systemspattern matching

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Review text

Summary: The problem of compressed pattern matching, which has recently been treated in many papers dealing with free text, is extended to structured files, specifically to dictionaries, which appear in any full-text retrieval system. The prefix-omission method is combined with Huffman coding and a new variant based on Fibonacci codes is presented. Experimental results suggest that the new methods are often preferable to earlier ones, in particular for small files which are typical for dictionaries, since these are usually kept in small chunks.

Recommendations

• Faster compressed dictionary matching
• Let sleeping files lie: Pattern matching in Z-compressed files.
• scientific article; zbMATH DE number 2140438
• Pattern matching in Huffman encoded texts
• Compressed automata for dictionary matching

Cites work

• \((s,c)\)-dense coding: an optimized compression code for natural language text databases.
• Compressed matching in dictionaries
• scientific article; zbMATH DE number 2185629 (Why is no real title available?)
• scientific article; zbMATH DE number 2185642 (Why is no real title available?)
• scientific article; zbMATH DE number 1263249 (Why is no real title available?)
• scientific article; zbMATH DE number 1445301 (Why is no real title available?)
• Improving table compression with combinatorial optimization
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Pattern matching in Huffman encoded texts
• Robust universal complete codes for transmission and compression

Cited in

(18)

• Compressed matching in dictionaries
• Direct merging of delta encoded files
• Compressing dictionary matching index via sparsification technique
• Succinct 2D dictionary matching
• Pattern matching in Huffman encoded texts
• Bidirectional adaptive compression
• Unification and matching on compressed terms
• scientific article; zbMATH DE number 2088760 (Why is no real title available?)
• MODELING DELTA ENCODING OF COMPRESSED FILES
• Small-Space 2D Compressed Dictionary Matching
• Succinct Dictionary Matching with No Slowdown
• The structural border array
• scientific article; zbMATH DE number 1946603 (Why is no real title available?)
• A new compression method of double array for compact dictionaries
• scientific article; zbMATH DE number 1432383 (Why is no real title available?)
• Forward looking Huffman coding
• String matching over compressed text on handheld devices using tagged sub-optimal code (TSC)
• Compressed parameterized pattern matching

Describes a project that uses

Uses Software

• XMill

This page was built for publication: Compressed matching in dictionaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736479)