単語単位情報源に対するLZ78符号の圧縮性能(一般,フレッシュマン,招待講演 : フレッシュマンセッション)
スポンサーリンク
概要
- 論文の詳細を見る
代表的なユニバーサル符号であるZiv-Lempel(LZ)符号は,理論面だけでなく実用面からもより圧縮効果を高める修正アルゴリズムが数多く提案され,ユニバーサル性の証明や冗長度について議論されている.一方近年,実データに近い情報源を表現するモデルとして,言語アルファベット情報源や単語単位情報源が提案され,そのエントロピーレートが解析されている.また,LZ78符号は単語単位の定常エルゴード情報源に対して漸近最良であることがすでに示されている.単語単位の情報源に対するLZ78符号化として,(i)単語単位で増分分解を行う(ii)シンボル単位で増分分解を行うという2通りを考えることができる.これら2通りの方法でLZ78符号化を行う場合にどの程度の差が生じてくるのかという性能解析は興味深いテーマである.そこで,本稿では上記2通りのLZ78符号に基づく符号化法の平均冗長度について,その上界を求め,LZ78符号の有効性について考察を行う.その結果,(i)(ii)の2通りの方法ともその上界がO(1/log n)を達成することを示す.ここでnは入力系列長である.
- 社団法人電子情報通信学会の論文
- 2003-07-15
著者
関連論文
- 高次元ベクトル空間モデルによるテキスト分類問題について : 分類性能と距離構造の漸近解析(理論・技術)
- モバイル向け証明書検証システムの開発(ネットワークセキュリティ,シームレスコンピューティングとその応用技術)
- 複数のLDPC符号の交錯による有限状態マルコフ通信路に適した誤り訂正符号について(LDPC符号セッション(符号構成),LDPC符号,及び一般)
- 確率伝搬法を用いたCDMAマルチユーザ検出アルゴリズムに関する一考察
- ユニバーサル情報源・通信路結合符号化に関する一考察
- 外れ値データの発生を含む回帰モデルに対するベイズ予測アルゴリズム
- 複合情報源におけるε達成可能なオーバーフローしきい値に関する考察
- デジタル指紋技術のための結託耐性を持つ符号の連接符号化法
- 無ひずみ情報源符号化におけるオーバフロー確率について(情報理論)
- ユニバーサル通信路符号化法における通信路容量について(ブロードバンドモバイル時代における基礎技術)(情報通信サブソサイエティ合同研究会)
- 決定木モデルにおける予測アルゴリズムについて
- メモリ量を低減した近似ベイズ符号化アルゴリズム(情報理論)
- BW変換を用いたユニバーサル符号化アルゴリズムに関する研究
- 混合Polya分布に基づくサブカテゴリを考慮した文書分類手法 (情報理論)
- グラフを組み合わせたLDPC符号アンサンブルに対する最小スパンの解析(情報通信基礎サブソサイエティ合同研究会)
- ベイズ統計学に基づくOn-line学習モデルと学習可能性
- A-6-6 一般化LDPC符号に対するBF復号法の修正とその性能解析(A-6.情報理論,一般セッション)
- 元画像との差分ベクトルを特徴量とした学習による改変画像検出(ITS画像処理,映像メディア及び一般)
- JPEG2000のビットプレーンを用いたテクスチャ画像の検索(画像符号化,通信・ストリーム技術,及び一般)
- Group Shuffled BP復号法における効果的なグループ分割法
- 信頼度更新を用いたLDPC符号の Bit-Flipping 復号法の改良
- 単語の特徴を考慮したPLSIによる文書クラスタリング
- 単語の共起を考慮に入れたナイーブベイズモデルによる文書分類
- HMM通信路に対するEM復号の復号誤り確率の評価法
- バースト消失訂正に適したLDPC符号の修正方法について(情報通信基礎サブソサイエティ合同研究会)
- ソート・マッチング法に基づく軟判定復号アルゴリズムの修正
- 有限幾何に基づく Fingerprinting のための結託耐性符号
- 譲渡可能で二重使用不可能な電子チケットシステム
- 電子情報通信学会倫理綱領試案 : その解説と策定の経過
- トレリス符号を用いた有歪みデータ圧縮の一考察
- 一般化LDPC符号に対する部分符号の構造を利用した効率的な符号化法(フレッシュマンセッション,フレッシュマンセッション,一般)
- 単語と N-gram の各カテゴリにおける出現頻度の比の和を用いたテキスト自動分類手法
- 階層的クラスタを用いた適合性フィードバック手法による文書検索
- クラスタに基づく適合性フィードバックによる文書検索
- 単語ごとの修正重みに基づく適合性フィードバックによる文書検索
- ランプ型鍵配送方式について
- PLSIを用いた文書分類手法に関する一考察 (人工知能と知識処理)
- モバイル環境での証明書検証方式の評価(セキュリティ,データ工学論文)
- 多機能ICカード向けPKI機能
- 自然数表現の一般化について
- IT2010-13 混合Polya分布に基づくサブカテゴリを考慮した文書分類手法(フレッシュマンセッション,一般)
- 適合文書から抽出した重要語に基づく文書検索
- D-044 クラスタに基づいた適合性フィードバック手法(D分野:データベース)
- D-043 初期検索結果から抽出した単語を用いた擬似フィードック手法(D分野:データベース)
- E-010 ユーザにとって潜在的に重要な単語を用いた対話的文書検索(E.自然言語・文書・ゲーム)
- IT2010-11 アルファベットが未知の木情報源に対する効率的ベイズ符号化アルゴリズム(フレッシュマンセッション,一般)
- ベイズ統計学に基づく計算論的学習モデルと学習可能性
- モバイル向け証明書検証方式の評価
- モバイル向け証明書検証サーバの開発
- 質問学習と逐次実験計画の関係に関する一考察
- 直交計画を用いたブール関数の学習に関する一考察
- ブール関数の逐次実験計画を用いた学習に関する一考察
- ベイス決定理論による定式化のもとで直交計画を用いたブール関数の学習に関する一考察
- フーリエ変換を用いたブール関数の学習に関する一考察
- 質問からの学習問題の決定理論による定式化に関する一考察
- N-008 教学支援システムに関する学生アンケートの分析(N分野:教育・人文科学)
- N-021 自然言語表現に基づく学生アンケート分析システム(N.教育・人文科学)
- 高次元ベクトル空間モデルによるテキスト分類問題について : 分類性能と距離構造の漸近解析
- ソーシャルブックマークにおけるユーザのタグ付け傾向を加味したWebページ推薦手法 (人工知能と知識処理)
- 評価関数の重みパラメータを推定する対話型遺伝的アルゴリズム(「コミュニティ上での知識の共有・再利用」及び一般)
- PLSIを用いた文書分類手法に関する一考察(「コミュニティ上での知識の共有・再利用」及び一般)
- 語頭条件を満たさないWord-valued sourceに対するLZ78符号の符号化性能について
- 語頭条件を満たさない Word-valued source に対するLZ78符号の符号化性能について
- ソーシャルブックマークにおけるユーザのタグ付け傾向を加味したWebページ推薦手法(「コミュニティ上での知識の共有・再利用」及び一般)
- E-1 文間の単語共起類似度を用いた重要文抽出手法(要約・情報検索,E.自然言語・文書)
- 辞書番号を修正したLZW符号
- 参照回数を考慮したLZW法によるデータ圧縮(フレッシュマンセッション)(フレッシュマン,一般)
- 単語単位情報源に対するLZ78符号の圧縮性能(一般,フレッシュマン,招待講演 : フレッシュマンセッション)
- 評価関数の重みパラメータを推定する対話型遺伝的アルゴリズム (人工知能と知識処理)
- A-002 観光地の指定とスケジュールの多様性を考慮した観光スケジュール作成支援(モデル・アルゴリズム・プログラミング,一般論文)
- 大学の情報系授業における学生アンケートの分析
- 語頭条件を満たさない単語集合をもつWord-Valued Sourceの性質について
- E-13 クラスタ生成に基づく電子メール文書の重要度ランク付け手法(文書分類,E.自然言語・文書)
- ブロック単位で系列を出力する情報源に対するベイズ符号とZiv-Lempel符号のユニバーサル性について
- H-029 回転方向の自己相関関数を用いた商標図形分類法(H分野:画像認識・メディア理解)
- H-028 色情報に対する人間の感性を考慮した類似画像検索(H分野:画像認識・メディア理解)
- 相関に基づいた共クラスタリングによる協調フィルタリング
- 最頻文脈依存 N-gram を考慮した文法生成法に基づくデータ圧縮法
- Word-valued source から出現する系列の単語分割について
- 語頭条件を満たさない Word-Valued Source モデルに関する一考察
- 静止画像の無歪み圧縮に適した領域分割アルゴリズム
- JPEGにおけるハフマン符号化法の修正
- J-067 ブロック単位でマルチ走査を行う静止画像圧縮(J分野:グラフィクス・画像)
- 文脈混合を考慮したPPMアルゴリズム(フレッシュマン, 一般)
- 単一ビットプレーンごとのSPIHTアルゴリズムを用いた静止画像圧縮
- D-029 相互情報量に基づく特徴選択を用いた文書自動分類(D分野:データベース)
- データ圧縮に適した最頻 digram に基づく逐次型文法変換法
- J-066 情報の偏りを考慮した静止画像の可逆予測符号化法(J分野:グラフィクス・画像)
- 周波数変換後の信号の重要度を考慮した画像圧縮法(フレッシュマンセッション)(フレッシュマン,一般)
- 最頻N-gramを考慮した文法生成法に基づくデータ圧縮法(一般,フレッシュマン,招待講演 : フレッシュマンセッション)
- PLSIに基づく適合性フィードバック手法
- J-065 DCTにおけるAC係数の相関を考慮した画像符号化(J分野:グラフィクス・画像)
- ソーシャルブックマークにおけるユーザのタグ付け傾向を加味した Web ページ推薦手法
- 単語の潜在的意味を考慮した文書分類手法
- 評価関数の重みパラメータを推定する対話型遺伝的アルゴリズム(人工知能,データマイニング)
- F-040 混合決定木モデルによる連続変数の予測法に関する一考察(学習とゲーム,F分野:人工知能・ゲーム)
- A-009 アルファベットサイズが未知の情報源に対する効率的なベイズ符号化法の一考察(アルゴリズム・コンピュテーション(1),A分野:モデル・アルゴリズム・プログラミング)
- テキスト分類問題におけるカテゴリ情報を用いた適応的距離学習に関する一考察(第15回情報論的学習理論ワークショップ)
- ECOC法における分類器の予測精度を考慮した分類法に関する一考察(「コンテキストを意識した知識の利用」及び一般)
- 欠損値を含むデータのクラスタリングのためのRandom Forestを用いた類似度算出法(研究速報)