Title :
LZ-Compressed String Dictionaries
Author :
Arz, Julian ; Fischer, J.
Author_Institution :
KIT, Karlsruhe, Germany
Abstract :
We show how to compress string dictionaries using Lempel-Ziv (LZ78) data compression. Our approach is validated experimentally on dictionaries of up to 1.5 GB of uncompressed text. We achieve compression ratios often outperforming the existing alternatives, especially on dictionaries containing many repeated substrings. Our query times remain competitive.
Keywords :
data compression; data structures; LZ-compressed string dictionary; LZ78 data compression; Lempel-Ziv data compression; compression ratio; data structure; query times; uncompressed text; Data compression; Data structures; Dictionaries; Encoding; Indexing; lempel-ziv; string compression; succinct data structures;
Conference_Titel :
Data Compression Conference (DCC), 2014
Conference_Location :
Snowbird, UT
DOI :
10.1109/DCC.2014.36
