文献

J-GLOBAL ID：201502212717770311   整理番号：15A0367926

Dense符号化のための文法圧縮分割

Grammar Compression Parsing for Dense Coding

著者 (3件)： 正木拓也 (北大 大学院情報科学研究科) ,  笹川裕人 (北大 大学院情報科学研究科) ,  喜田拓也 (北大 大学院情報科学研究科)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2014  号： AL-149  ページ： VOL.2014-AL-149,NO.5 (WEB ONLY)  発行年： 2014年09月05日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 入力テキストを単語毎に符号化するEnd-Tagged Dense符号(ETDC)は,バイト単位の可変長符号を用いる,符号語の抽出が容易な検索向きのデータ圧縮法である。本稿では,単語毎に分かち書きされていないテキストに対してETDCで符号化する手法を提案した。提案手法は,テキストに対して文法圧縮の一つであるRe-Pairアルゴリズムを利用した分かち書きを行い,その後にETDCで符号化を行う。その際,Re-Pairアルゴリズムの再帰処理において,後段のETDCの符号化の効率を見積もる評価指標を導入し,その指標に基づいて再帰を打ち切る。それにより,日本語テキストやゲノムデータなどに対しても,検索や圧縮率の観点から効率よいデータ圧縮が実現できる。今回,実データに対して提案手法を適用することで,gzipやbzip2に匹敵する圧縮率を達成できることを実証した。(著者抄録)

シソーラス用語： *符号化 ,  *自然言語処理 ,  文法 ,  自然言語 ,  可変長符号 ,  データ圧縮 ,  データ検索 ,  構文分析 ,  復号化 ,  日本語 ,  データベース ,  ゲノム ,  圧縮率
準シソーラス用語： ゲノムデータベース ,  分かち書き ,  文法圧縮

分類 (2件)： 符号理論  (ND02030R) ,  自然語処理  (JE06000L)

引用文献 (10件)：

• Amir, A. and Benson, C.: Efficient two-dimensional compressed matching, Data Compression Conference, 1992. DCC'92., IEEE, pp. 279-288 (1992).
• Brisaboa, N., Iglesias, E., Navarro, G. and Paramá, J.: An Efficient Compression Code for Text Databases, Proc. 25th European Conference on Information Retrieval Research (ECIR), LNCS 2633, pp. 468-481 (2003).
• Kieffer, J. C. and Yang, E.-H.: Grammar-based codes: a new class of universal lossless source codes, Information Theory, IEEE Transactions on, Vol. 46, No. 3, pp. 737-754 (2000).
• Larsson, N. J. and Moffat, A.: Off-line dictionary-based compression, Proceedings of the IEEE, Vol. 88, No. 11, pp. 1722-1732 (2000).
• Moffat, A.: Word-based text compression, Software: Practice and Experience, Vol. 19, No. 2, pp. 185-198 (1989).

タイトルに関連する用語 (2件)： 符号化 ,  文法圧縮