文献

J-GLOBAL ID：201702267422623378   整理番号：17A0690358

高階圧縮における連続パターンのコンパクトな表現法

著者 (2件)： 古谷勇 (北大 工) ,  喜田拓也 (北大 大学院情報科学研究科)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2017  号： AL-162  ページ： Vol.2017-AL-162,No.1,1-8 (WEB ONLY)  発行年： 2017年03月06日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 高階圧縮とは,入力データを表すラムダ式を構築し,それを符号化することで行う圧縮法である。本論文では,同じパターンが連続する部分に対して,コンパクトなラムダ式を生成する手法を提案する。提案手法では,パターンの連続回数を表す自然数(連長)を超冪の線形式に分解し,その式に対応するラムダ式を直接出力する。自然数nに対して,出力されるラムダ式のサイズがO(log n)であることを証明した。また,実験の結果,連長をラムダ式のバイナリ表現で置き換える既存手法に比べ,ラムダ式のサイズを平均して約21%低減することを確認した。(著者抄録)

シソーラス用語： *データ圧縮 ,  λ計算 ,  連続性 ,  データ型 ,  データ ,  *モデリング ,  コンパクト性 ,  データ表現 ,  *符号化 ,  反復配列 ,  一次方程式
準シソーラス用語： 入力データ ,  *モデル化 ,  繰返し配列 ,  線形方程式

分類 (1件)： 符号理論  (ND02030R)

引用文献 (6件)：

• Barendregt, H.: The Lambda Calculus, Its Syntax and Semantics: Revised edition, North-Holland (1985).
• Huffman, D.: A Method for the Construction of Minimum-Redundancy Codes, Proc. the Institute of Radio Engineers, Vol. 40, No. 9, pp. 1098-1101 (1952).
• Kieffer, J. C. and Yang, E.-H.: Grammar-Based Codes: a New Class of Universal Lossless Source Codes, IEEE Trans. on Inform. Theory, Vol. 46, No. 3, pp. 737-754 (2000).
• Kobayashi, N., Matsuda, K., Shinohara, A. and Yaguchi, K.: Functional Programs As Compressed Data, Higher Order Symbol. Comput., Vol. 25, No. 1, pp. 39-84 (2012).
• Sayood, K.(ed.): Lossless Compression Handbook, Academic Press (2002).

タイトルに関連する用語 (1件)： 表現