| 講演名 | 2022-07-21 データを生成するコンピューター上のプログラムを符号語とするデータ圧縮法 有村 光晴(湘南工科大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 文字列のコフモゴロフ複雑度は，チューリング機械上のプログラムを用いて文字列を表現する際のプログラムの最小の長さと定義されている．一方，ラムダ計算もチューリング機械と同様の計算能力を持つことが明らかになっている．本稿では，文字列に対して，それを生成するコンピューター上のプログラムを符号語とするデータ圧縮を提案する．プログラミング言語としては，ラムダ計算を基礎にして実装された関数型プログラミング言語Haskellを用いる．計算モデルとしては，文脈自由文法および，それと同等の計算機モデルであるプッシュダウン・オートマトンを用いる．作成したプログラムとこれらの関係について述べる．また，この符号化の有限状態情報源に対するユニバーサル性を示すほか，符号化および復号化が線形時間で可能であることを示す． |
| 抄録(英) | The Kolmogorov complexity of a string is defined as the shortest length of the program on a Turing machine used to represent the string. On the other hand, it is proved that lambda calculus has the same computational power as the Turing machine. This paper proposes a data compression method using computer programs as the codeword. We use the Haskell programming language, which is a functional programming language implemented on the basis of the lambda calculus. As a computational model, we use a context-free grammar and its corresponding computer model, push-down automaton. A relationship between this program and these models is described. In addition to showing the universality of this coding for finite-state information sources, we also show that coding and decoding are possible in linear time. |
| キーワード(和) | データ圧縮 / コルモゴロフ複雑度 / 関数型プログラミング / Haskell / 文脈自由文法 / プッシュダウン・オートマトン |
| キーワード(英) | Data Compression / Kolmogorov Complexity / Functional Programming / Haskell / Context-Free Grammar / Pushdown Automaton |
| 資料番号 | IT2022-19 |
| 発行日 | 2022-07-14 (IT) |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 2022/7/21(から2日開催) |
| 開催地（和） | 岡山理科大学 |
| 開催地（英） | Okayama University of Science |
| テーマ（和） | フレッシュマンセッション，一般 |
| テーマ（英） | Freshman session, General |
| 委員長氏名（和） | 小嶋 徹也(東京高専) |
| 委員長氏名（英） | Tetsuya Kojima(Tokyo Kosen) |
| 副委員長氏名（和） | 野上 保之(岡山大学) |
| 副委員長氏名（英） | Yasuyuki Nogami(Okayama Univ.) |
| 幹事氏名（和） | 松田 哲直(埼玉大) / 眞田 亜紀子(長岡技科大) |
| 幹事氏名（英） | Tetsunao Matsuta(Saitamai Univ.) / Akiko Manada(Nagaoka Univ. of Tech.) |
| 幹事補佐氏名（和） | 野崎 隆之(山口大) |
| 幹事補佐氏名（英） | Takayuki Nozaki(Yamaguchi Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Theory |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | データを生成するコンピューター上のプログラムを符号語とするデータ圧縮法 |
| サブタイトル（和） | |
| タイトル（英） | A Data Compression Method Where The Codeword Is a Computer Program Generating The Data |
| サブタイトル（和） | |
| キーワード(1)（和/英） | データ圧縮 / Data Compression |
| キーワード(2)（和/英） | コルモゴロフ複雑度 / Kolmogorov Complexity |
| キーワード(3)（和/英） | 関数型プログラミング / Functional Programming |
| キーワード(4)（和/英） | Haskell / Haskell |
| キーワード(5)（和/英） | 文脈自由文法 / Context-Free Grammar |
| キーワード(6)（和/英） | プッシュダウン・オートマトン / Pushdown Automaton |
| 第 1 著者 氏名（和/英） | 有村 光晴 / Mitsuharu Arimura |
| 第 1 著者 所属（和/英） | 湘南工科大学(略称：湘南工科大) Shonan Institute of Technology(略称：Shonan Inst. Tech.) |
| 発表年月日 | 2022-07-21 |
| 資料番号 | IT2022-19 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | IT-128 |
| ページ範囲 | pp.18-23(IT), |
| ページ数 | 6 |
| 発行日 | 2022-07-14 (IT) |