文献

J-GLOBAL ID：201602212284361665   整理番号：16A0023248

制約付きRe-Pairに基づいた適応型ブロック伸長法によるデータ圧縮アルゴリズム

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

抄録/ポイント： Re-Pairアルゴリズムは,入力テキスト長に対して線形時間で動作し,優れた圧縮率を達成することのできる文法圧縮アルゴリズムである。ただし,その動作はオフライン的であるため,テキスト全体を一度にメモリ上に読み込む必要がある。この問題に対し,従来,入力テキストを固定長のブロックに分割し,ブロック毎にRe-Pairを適用する手法が取られている。その手法で良好な圧縮率を達成するには,あらかじめ適切なブロック長を与える必要がある。我々はこれまでに,Re-Pairによって生成される文法にある種の条件を設けることで,Re-Pairアルゴリズムと同等のテキスト置換を与えられた辞書を用いてオンライン的に実行することのできるアルゴリズムを得ている。本稿では,そのオンライン置換アルゴリズムを基に,ブロック長を適応的に伸長させながら圧縮する手法を提案する。(著者抄録)

シソーラス用語： *データ圧縮 ,  *計算機アルゴリズム ,  文法 ,  変換 ,  生成文法
準シソーラス用語： *データ圧縮アルゴリズム ,  適応型ブロック伸長法 ,  文法圧縮 ,  文法変換

分類 (1件)： システムプログラミング一般  (JD03010Y)

タイトルに関連する用語 (4件)： 制約 ,  Re ,  データ圧縮 ,  アルゴリズム