Asymptotic Optimality of the Block Sorting Data Compression Algorithm (Special Section on Information Theory and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper the performance of the Block Sorting algorithm proposed by Burrows and Wheeler is evaluated theoretically. It is proved that the Block Sorting algorithm is asymptotically optimal for stationary ergodic finite order Markov sources. Our proof is based on the facts that sysbols with the same Markov state (or context) in an original data sequence are grouped together in the output sequence obtained by Burrows-Wheeler transform, and the codeword length of each group can be bounded by a function described with the fequencies of sysbols included in the group.
- 社団法人電子情報通信学会の論文
- 1998-10-25
著者
-
有村 光晴
湘南工科大学工学部コンピュータ応用学科
-
Yamamoto Hirosuke
School Of Engineering The University Of Tokyo
-
ARIMURA Mitsuharu
School of Engineering, the University of Tokyo
-
Arimura Mitsuharu
School Of Engineering The University Of Tokyo
関連論文
- On the redundancy rate of FF and VF source codes for general sources (ワイドバンドシステム)
- On the redundancy rate of FF and VF source codes for general sources (情報セキュリティ)
- On the redundancy rate of FF and VF source codes for general sources (情報処理)
- プログラミング,何をどう教えているか 文理融合学科におけるプログラミングの導入教育
- 文理融合学科におけるプログラミングの導入教育(プログラミング,何をどう教えているか)
- IT2010-21 一般情報源に対する無歪みFF符号の最小達成可能冗長度レート(フレッシュマンセッション,一般)
- 一般情報源に対するFF符号およびVF符号の冗長度レートについて(一般:情報通信基礎サブソサイエティ合同研究会)
- 一般情報源に対するFF符号およびVF符号の冗長度レートについて(一般:情報通信基礎サブソサイエティ合同研究会)
- 一般情報源に対するFF符号およびVF符号の冗長度レートについて(一般:情報通信基礎サブソサイエティ合同研究会)
- 十分統計量と強ユニバーサル情報源符号化
- 情報スペクトルの幅と固定長符号化の最悪冗長度 (情報理論・情報通信基礎サブソサイエティ合同研究会)
- On the Average Coding Rate of the Tunstall Code for Stationary and Memoryless Sources
- 情報スペクトルの幅と固定長符号化の最悪冗長度(情報通信基礎サブソサイエティ合同研究会)
- 情報スペクトルの幅と固定長符号化の最悪冗長度(情報通信基礎サブソサイエティ合同研究会)
- 情報スペクトルの幅と固定長符号化の最悪冗長度(情報通信基礎サブソサイエティ合同研究会)
- ユニバーサルデータ圧縮と十分統計量
- 定常エルゴード情報源に対するMTF法の性能解析
- A Bitplane Tree Weighting Method for Lossless Compression of Gray Scale Images
- Lossless Data Compression via Substring Enumerationにおけるある改良
- Asymptotic Optimality of the Block Sorting Data Compression Algorithm (Special Section on Information Theory and Its Applications)
- FF符号における冗長度と符号化レートの関係について(情報源符号化)
- Lossless Data Compression via Substring Enumerationのマルコフ情報源に対する最悪冗長度
- Lossless Data Compression via Substring Enumerationのマルコフ情報源に対する最悪冗長度
- 冗長度と符号化レートの両方で最適なFF符号
- 可算無限アルファベットの情報源に対してVF符号が存在する条件(記録素子用符号化,一般)
- Lossless Data Compression via Substring Enumerationのマルコフ情報源に対する最悪冗長度