講演抄録/キーワード |
講演名 |
2010-07-22 09:50
アルファベットが未知の木情報源に対する効率的ベイズ符号化アルゴリズム ○岩間大輝・寺本賢一・石田 崇・後藤正幸(早大) IT2010-11 |
抄録 |
(和) |
一般的なユニバーサル符号では, 情報源アルファベット中の全記号が正の出現確率を持つという仮定のもとで符号化法が構成されている. しかし実際の情報源系列では, すべての記号が出現するとは限らない.
そこで, 先行研究においてアルファベット中の出現記号数を未知とした符号アルゴリズムがいくつか提案されている. ベイズ最適性を保証するベイズ符号においても, アルファベットが未知の場合の符号化法が提案されているが, 計算量が膨大であり, また定常無記憶情報源を仮定しているという制約があった.
本研究では, 従来の研究で示されたアルゴリズムと等価な符号を効率的に計算するアルゴリズムを提案し, さらに, 次数未知の木情報源を対象にしたベイズ符号に拡張したアルゴリズムを定式化する. また, 平均計算量が漸近的に収束をすることに注目し, 計算量の理論的評価として漸近計算量を示す. 平均計算量が実際に収束することを確認し, 従来手法と提案手法の計算量の評価を行う. |
(英) |
In general universal coding, it is supposed that every symbol in alphabet appears. However, some symbols may not apper in data sequence inpractice.
Then source coding algorithms for sources with unknown alphabet have been propsed. On the other hand, it is difficult to use the Bayes cording algorithm for a source with unknown alphabet in practice, because the algorithm has huge computational complexity. In this paper, we propse an algorithm that has the identical compression performance and less complexity as the conventional method.
Additionally we formularize an extended algorithm for tree sources. Furthermore we show that the average computational complexity converges asymptotically.
Finally we show the simulation experiment for asymptotic performances of conventional and propsed methods. |
キーワード |
(和) |
ベイズ符号 / 情報源符号化 / 木情報源 / 計算量 / / / / |
(英) |
Bayes coding / source coding / tree source / computaional complexity / / / / |
文献情報 |
信学技報, vol. 110, no. 137, IT2010-11, pp. 1-6, 2010年7月. |
資料番号 |
IT2010-11 |
発行日 |
2010-07-15 (IT) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2010-11 |
研究会情報 |
研究会 |
IT |
開催期間 |
2010-07-22 - 2010-07-23 |
開催地(和) |
工学院大学 |
開催地(英) |
Kogakuin University |
テーマ(和) |
フレッシュマンセッション,一般 |
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
IT |
会議コード |
2010-07-IT |
本文の言語 |
日本語 |
タイトル(和) |
アルファベットが未知の木情報源に対する効率的ベイズ符号化アルゴリズム |
サブタイトル(和) |
|
タイトル(英) |
An Efficient Bayes Coding Algorithm for Context Tree Sources with Unknown Alphabet |
サブタイトル(英) |
|
キーワード(1)(和/英) |
ベイズ符号 / Bayes coding |
キーワード(2)(和/英) |
情報源符号化 / source coding |
キーワード(3)(和/英) |
木情報源 / tree source |
キーワード(4)(和/英) |
計算量 / computaional complexity |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
岩間 大輝 / Hiroki Iwama / イワマ ヒロキ |
第1著者 所属(和/英) |
早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.) |
第2著者 氏名(和/英/ヨミ) |
寺本 賢一 / Kenichi Teramoto / テラモト ケンイチ |
第2著者 所属(和/英) |
早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.) |
第3著者 氏名(和/英/ヨミ) |
石田 崇 / Takashi Ishida / イシダ タカシ |
第3著者 所属(和/英) |
早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.) |
第4著者 氏名(和/英/ヨミ) |
後藤 正幸 / Masayuki Goto / ゴトウ マサユキ |
第4著者 所属(和/英) |
早稲田大学 (略称: 早大)
Waseda University (略称: Waseda Univ.) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2010-07-22 09:50:00 |
発表時間 |
25分 |
申込先研究会 |
IT |
資料番号 |
IT2010-11 |
巻番号(vol) |
vol.110 |
号番号(no) |
no.137 |
ページ範囲 |
pp.1-6 |
ページ数 |
6 |
発行日 |
2010-07-15 (IT) |
|