文献

J-GLOBAL ID：201802251276630429   整理番号：18A1365327

文字列辞書を用いた効率的な文字列辞書圧縮の検討と評価

Efficient String Dictionary Compression Using String Dictionaries

著者 (3件)： 神田峻介 (徳島大 大学院先端技術科学教育部) ,  森田和宏 (徳島大 大学院社会産業理工学研究部) ,  泓田正雄 (徳島大 大学院社会産業理工学研究部)
資料名： 日本データベース学会和文論文誌(Web)  (DBSJ Japanese Journal (Web))
巻： 16-J  ページ： ROMBUNNO.7 (WEB ONLY)  発行年： 2018年03月 
JST資料番号： U0795A  ISSN： 2189-0374  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 文字列集合を保管するためのデータ構造である文字列辞書に関して,近年,多くの用途でコンパクト性が求められるという実例が報告されている。また,その背景に応じて,TrieやFront-Codingなどの辞書を実現するための優れた技法に,Re-Pairなどの強力な文書圧縮技法を組み合わせた圧縮文字列辞書が提案されている。本稿では,既存の圧縮文字列辞書の改良を目的とし,文字列辞書の圧縮に文字列辞書を用いるという方策に基づいた辞書構造を提案する。実データを用いた実験より,提案による文字列辞書はRe-Pairにより圧縮した辞書と比べ,メモリ効率や検索・復元速度のトレードオフに関して同等の性能を示しつつ,短い時間で構築できることを示した。(著者抄録)

シソーラス用語： 文字列 ,  *辞書 ,  *データ圧縮 ,  *データ構造 ,  木構造 ,  検索効率 ,  符号化 ,  実験
準シソーラス用語： トライ木 ,  評価実験

分類 (2件)： その他の計算機利用技術  (JE14000C) ,  システムプログラミング一般  (JD03010Y)

引用文献 (18件)：

• Miguel A Martínez-Prieto, Nieves Brisaboa, Rodrigo Cánovas, Francisco Claude, and Gonzalo Navarro. Practical compressed string dictionaries. Information Systems, 56:73-108, 2016.
• Roberto Grossi and Giuseppe Ottaviano. Fast compressed tries through path decompositions. ACM Journal of Experimental Algorithmics, 19(1):Article 1.8, 2014.
• Julian Arz and Johannes Fischer. LZ-compressed string dictionaries. In DCC, pages 322-331, 2014.
• Shunsuke Kanda, Kazuhiro Morita, and Masao Fuketa. Compressed double-array tries for string dictionaries supporting fast lookup. Knowledge and Information Systems, 51(3):1023-1042, 2017.
• 久田 晋. Prefix/patricia trieの入れ子による辞書圧縮. In 言語処理学会, 2011.

タイトルに関連する用語 (3件)： 文字列 ,  辞書 ,  評価