number of access : ?
number of downloads : ?
ID 115416
Title Alternative
Efficient String Dictionary Compression Using String Dictionaries
Author
Kanda, Shunsuke
Content Type
Journal Article
Description
文字列集合を保管するためのデータ構造である文字列辞書に関して,近年,多くの用途でコンパクト性が求められるという実例が報告されている.また,その背景に応じて,Trie や Front-Coding などの辞書を実現するための優れた技法に,Re-Pair などの強力な文書圧縮技法を組み合わせた圧縮文字列辞書が提案されている.本稿では,既存の圧縮文字列辞書の改良を目的とし,文字列辞書の圧縮に文字列辞書を用いるという方策に基づいた辞書構造を提案する.実データを用いた実験より,提案による文字列辞書はRe-Pair により圧縮した辞書と比べ,メモリ効率や検索・復元速度のトレードオフに関して同等の性能を示しつつ,短い時間で構築できることを示した.
Description Alternative
A string dictionary is a data structure to store a set of strings. Recently, instances have emerged in practice where the size of string dictionaries has become a critical problem in many applications. Consequently, compressed string dictionaries have been proposed by leveraging efficient implementation techniques, such as Trie and Front-Coding, and powerful text compression techniques, such as Re-Pair. In this paper, we propose new dictionary structures based on a strategy using string dictionaries for the compression in order to improve existing compressed ones. We show that our string dictionaries can be constructed in a shorter time compared to the Re-Pair versions with competitive space usage and operation speed, through experiments on real-world datasets.
Journal Title
DBSJ Japanese Journal
ISSN
21890366
21890374
Publisher
日本データベース学会
Volume
16-J
Start Page
7
Published Date
2018-03
EDB ID
URL ( Publisher's Version )
FullText File
language
jpn
TextVersion
Publisher
departments
Science and Technology