| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-07-24 11:20 T-codeの再帰的構造に基づく新しい辞書式データ圧縮アルゴリズム ○濱野健二・山本博資（東大）  IT2009-20 |
|
| 抄録 | （和） | T-codeの再帰的構造に基づく新しい辞書式データ圧縮アルゴリズムを提案する．Calgaryコーパスの全てのファイルについて，本圧縮アルゴリズムは，LZ78系のLZWアルゴリズムを実装したcompressコマンドを上回る圧縮性能を持つ． 暗号用乱数の統計的評価に広く使用されているNIST SP 800-22には，当初，LZ78増分分解法で決まるLZ-complexityに基づくLempel-Ziv圧縮検定が含まれていたが，P値が離散的に分布するためにNIST SP 800-22から除外された．現在，系列の圧縮性を直接的に評価する乱数検定がNIST SP 800-22に含まれていない．この問題を解決するために，2008年，T-complexityに基づく乱数検定法を提案した．系列のT-complexityは，系列をT-codeの符号語として表すために系列を分解するアルゴリズム（T-decomposition）で決まる．T-codeの再帰的構造に基づくデータ圧縮アルゴリズムの実現は，T-codeに基づく乱数検定法がNIST SP 800-22のLempel-Ziv圧縮検定を代替可能であることを支持する． |
| （英） | We present a new data compression algorithm based on a dictionary method using the recursive construction of T-codes. For all files in Calgary corpus, this data compression algorithm achieves better compression ratio than the ``compress" command, which is an implementation of the LZW algorithm classified as the LZ78 family. The NIST SP 800-22, which is the most widely used statistical test suit for random numbers in the field of cryptography, originally included the Lempel-Ziv compression test based on the LZ-complexity derived from the LZ78 incremental parsing rule, but then removed it because its P-value distributes discretely. Now the NIST SP 800-22 has no randomness test to directly measure the compressibility of sequences. To solve this problem, we proposed a randomness test based on T-codes in 2008. The T-complexity used in this test is derived from the string parsing algorithm called T-decomposition, by which the string can be represented as a T-code codeword. Realization of a data compression algorithm based on the recursive construction of T-codes supports that the randomness test based on T-codes can replace the Lempel-Ziv compression test included in the NIST SP 800-22. |
|
| キーワード | （和） | T-code / T-complexity / データ圧縮 / Lempel-Ziv / LZ-complexity / NIST SP 800-22 / / |
| （英） | T-code / T-complexity / data compression / Lempel-Ziv / LZ-complexity / NIST SP 800-22 / / | |
| 文献情報 | 信学技報, vol. 109, no. 143, IT2009-20, pp. 85-90, 2009年7月. | |
| 資料番号 | IT2009-20 | |
| 発行日 | 2009-07-16 (IT) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IT2009-20 |
|
| 研究会情報 | |
| 研究会 | IT |
| 開催期間 | 2009-07-23 - 2009-07-24 |
| 開催地（和） | 関西学院大学（梅田キャンパス） |
| 開催地（英） | Kwansei Gakuin Univ. (Umeda campus) |
| テーマ（和） | フレッシュマンセッション，一般 |
| テーマ（英） | Freshman session, general |
| 講演論文情報の詳細 | |
| 申込み研究会 | IT |
| 会議コード | 2009-07-IT |
| 本文の言語 | 日本語 |
| タイトル（和） | T-codeの再帰的構造に基づく新しい辞書式データ圧縮アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A New Data Compression Algorithm Based on a Dictionary Method Using Recursive Construction of T-codes |
| サブタイトル（英） | |
| キーワード(1)（和/英） | T-code / T-code |
| キーワード(2)（和/英） | T-complexity / T-complexity |
| キーワード(3)（和/英） | データ圧縮 / data compression |
| キーワード(4)（和/英） | Lempel-Ziv / Lempel-Ziv |
| キーワード(5)（和/英） | LZ-complexity / LZ-complexity |
| キーワード(6)（和/英） | NIST SP 800-22 / NIST SP 800-22 |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 濱野 健二 / Kenji Hamano / ハマノ ケンジ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： Tokyo Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山本 博資 / Hirosuke Yamamoto / |
| 第2著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： Tokyo Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-07-24 11:20:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IT |
| 資料番号 | IT2009-20 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.143 |
| ページ範囲 | pp.85-90 |
| ページ数 | 6 |
| 発行日 | 2009-07-16 (IT) |
[研究会発表申込システムのトップページに戻る]