| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | ISEC IT WBS |
| 開催期間 | 2011-03-03 - 2011-03-04 |
| 開催地（和） | 大阪大学 |
| 開催地（英） | Osaka University |
| テーマ（和） | 一般：情報通信基礎サブソサイエティ合同研究会 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | IT |
| 会議コード | 2011-03-ISEC-IT-WBS |
| 本文の言語 | 日本語 |
| タイトル（和） | 最多一致部分列に基づくユニバーサル情報源符号化法の実用的なアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A Practical Algorithm of Universal Source Coding by the Most Frequent Substring |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 最多一致部分列 / grammar based codes |
| キーワード(2)（和/英） | 情報源符号化 / most frequent substring |
| キーワード(3)（和/英） | 定常情報源 / source coding |
| キーワード(4)（和/英） | 文法に基づく符号 / stationary source |
| キーワード(5)（和/英） | ユニバーサル符号 / universal code |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 齋藤 津樹 / Tsuki Saito / サイトウ ツキ |
| 第1著者 所属（和/英） | 東京工業大学 (略称： 東工大) Tokyo Institute of Technology (略称： Tokyo Inst. of Tech) |
| 第2著者 氏名（和/英/ヨミ） | 松田 哲直 / Tetsunao Matsuta / マツタ テツナオ |
| 第2著者 所属（和/英） | 東京工業大学 (略称： 東工大) Tokyo Institute of Technology (略称： Tokyo Inst. of Tech) |
| 第3著者 氏名（和/英/ヨミ） | 松本 隆太郎 / Ryutaroh Matsumoto / マツモト リュウタロウ |
| 第3著者 所属（和/英） | 東京工業大学 (略称： 東工大) Tokyo Institute of Technology (略称： Tokyo Inst. of Tech) |
| 第4著者 氏名（和/英/ヨミ） | 植松 友彦 / Tomohiko Uyematsu / ウエマツ トモヒコ |
| 第4著者 所属（和/英） | 東京工業大学 (略称： 東工大) Tokyo Institute of Technology (略称： Tokyo Inst. of Tech) |
| 講演者 | 第1著者 |
| 発表日時 | 2011-03-04 09:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | IT |
| 資料番号 | IT2010-105, ISEC2010-109, WBS2010-84 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.442(IT), no.443(ISEC), no.444(WBS) |
| ページ範囲 | pp.243-248 |
| ページ数 | 6 |
| 発行日 | 2011-02-24 (IT, ISEC, WBS) |
[研究会発表申込システムのトップページに戻る]