講演抄録/キーワード |
講演名 |
2011-03-04 09:25
最多一致部分列に基づくユニバーサル情報源符号化法の実用的なアルゴリズム ○齋藤津樹・松田哲直・松本隆太郎・植松友彦(東工大) IT2010-105 ISEC2010-109 WBS2010-84 |
抄録 |
(和) |
KiefferとYangによって提案された文法に基づく符号では、入力された系列だけを生成する文脈自由文法を作成した後、得られた文法を二元系列に変換する。林らは系列中に最頻出する部分列、すなわち最多一致部分列の簡約化を行う文法に基づく符号を提案し、提案符号のユニバーサル性、すなわち提案符号の平均符号長が、入力系列長が長くなるにつれて情報源のエントロピーレートに漸近することを示した。しかしながら、林らの文法変換法が実用的な計算量で実行できるのかについては明らかではなかった。本論文では、最多一致部分列による文法に基づく符号を新たに提案し、提案符号がユニバーサル符号であり、長さ$n$の入力系列に対し文法変換が$O(n^2)$の計算量で実行できることを示す。 |
(英) |
In the grammar based code proposed by Kieffer and Yang, a context-free grammar which only produces the input sequence is constructed, and the obtained grammar is encoded into a binary sequence. Lin et al. proposed a grammar based code by using the most frequent substring. Their proposed code is based on the reduction of the string which appears most frequently in the sequence. Lin et al. also proved that their code is a universal code whose average length converges to the entropy rate of the source as the length of the input sequence tends to infinity. However, it is not clear whether the grammar transformation proposed by Lin et al. can be executed in practical computational complexity. In this paper, we propose a new grammar based code by using the most frequent substring. We prove that the proposed code is a universal code, and that the proposed grammar transformation can be executed in $O(n^2)$ for the length of the input sequence $n$. |
キーワード |
(和) |
最多一致部分列 / 情報源符号化 / 定常情報源 / 文法に基づく符号 / ユニバーサル符号 / / / |
(英) |
grammar based codes / most frequent substring / source coding / stationary source / universal code / / / |
文献情報 |
信学技報, vol. 110, no. 442, IT2010-105, pp. 243-248, 2011年3月. |
資料番号 |
IT2010-105 |
発行日 |
2011-02-24 (IT, ISEC, WBS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2010-105 ISEC2010-109 WBS2010-84 |