文献

J-GLOBAL ID：200902276447200586   整理番号：09A0848711

T-codeの再帰的構造に基づく新しい辞書式データ圧縮アルゴリズム

A New Data Compression Algorithm Based on a Dictionary Method Using Recursive Construction of T-codes

著者 (2件)： 濱野健二 (東大 大学院新領域創成科学研究科) ,  山本博資 (東大 大学院新領域創成科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 109  号： 143(IT2009 6-31)  ページ： 85-90  発行年： 2009年07月16日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： T-codeの再帰的構造に基づく新しい辞書式データ圧縮アルゴリズムを提案する。Calgaryコーパスの全てのファイルについて,本圧縮アルゴリズムは,LZ78系のLZWアルゴリズムを実装したcompressコマンドを上回る圧縮性能を持つ。暗号用乱数の統計的評価に広く使用されているNIST SP800-22には,当初,LZ78増分分解法で決まるLZ-complexityに基づくLempel-Ziv圧縮検定が含まれていたが,P値が離散的に分布するためにNIST SP800-22から除外された。現在,系列の圧縮性を直接的に評価する乱数検定がNIST SP800-22に含まれていない。この問題を解決するために,2008年,T-complexityに基づく乱数検定法を提案した。系列のT-complexityは,系列をT-codeの符号語として表すために系列を分解するアルゴリズム(T-decomposition)で決まる。T-codeの再帰的構造に基づくデータ圧縮アルゴリズムの実現は,T-codeに基づく乱数検定法がNIST SP800-22のLempel-Ziv圧縮検定を代替可能であることを支持する。(著者抄録)

シソーラス用語： *データ圧縮 ,  *符号 ,  構造 ,  再帰性 ,  コーパス ,  アルゴリズム ,  乱数 ,  検定 ,  *計算量 ,  *情報理論
準シソーラス用語： Lempel-Ziv圧縮 ,  *T-code ,  *T-complexity ,  再帰的構造 ,  符号語 ,  乱数検定

分類 (3件)： システムプログラミング一般  (JD03010Y) ,  符号理論  (ND02030R) ,  システム・制御理論一般  (IA02010H)

引用文献 (16件)：

• Calgary Corpus. ftp.cpcs.ucalgary.ca/pub/projects/text.compression.corpus
• COVER, T. M. Elements of Information Theory. 2006
• GUNTHER, U. Data Compression and Serial Communication with Generalized T-codes. Journal of Universal Computer Science. 1996, 2, 11, 769-795
• GUNTHER, U. Robust Source Coding with Generalized T-Codes. PhD thesis, The University of Auckland. 1998
• 濱野. T-Code を用いた乱数検定手法の構成法について. ISEC. 2008, 107, 499, 43-50

タイトルに関連する用語 (3件)： 辞書 ,  データ圧縮 ,  アルゴリズム