これまでのあらすじ chapter 1: 情報を測る エントロピー,情報量,情報源の性質 chapter 2: 情報をコンパクトに表現する

Slides:



Advertisements
Similar presentations
ゲームプログラミング講習 第2章 関数の使い方
Advertisements

サービス管理責任者等研修テキスト 分野別講義    「アセスメントと        支援提供の基本姿勢」 <児童発達支援管理責任者> 平成27年10月1日.
ヒトの思考プロセスの解明を目的とするワーキングメモリの研究
第27講 オームの法則 電気抵抗の役割について知る オームの法則を使えるようにする 抵抗の温度変化を理解する 教科書P.223~226
コラッツ予想の変形について 東邦大学 理学部 情報科 白柳研究室 山中 陽子.
コンパイラ 第3回 字句解析 ― 決定性有限オートマトンの導出 ―
第5章 家計に関する統計 ー 経済統計 ー.
公共財 公共経済論 II no.3 麻生良文.
VTX alignment D2 浅野秀光 2011年12月15日  放射線研ミーティング.
冷却フランシウム原子を用いた 電子の永久電気双極子能率探索のための ルビジウム磁力計の研究
生命情報学 (8) スケールフリーネットワーク
前半戦 「史上最強」風 札上げクイズ.

認知症を理解し 環境の重要性について考える
フッ化ナトリウムによる洗口 2010・9・13 宮崎市郡東諸県郡薬剤師会 学校薬剤師  日高 華代子.
食品の安全性に関わる社会システム:総括 健康弱者 ハイリスク集団 HACCP (食肉処理場・食品工場) 農場でのQAP 一般的衛生管理
規制改革とは? ○規制改革の目的は、経済の活性化と雇用の創出によって、   活力ある経済社会の実現を図ることにあります。
地域保健対策検討会 に関する私見(保健所のあり方)
公共政策大学院 鈴木一人 第8回 専門化する政治 公共政策大学院 鈴木一人
医薬品ネット販売規制について 2012年5月31日 ケンコーコム株式会社.
平成26年8月27日(水) 大阪府 健康医療部 薬務課 医療機器グループ
平成26年度 呼吸器学会からの提案結果 (オレンジ色の部分が承認された提案) 新規提案 既収載の変更 免疫組織化学染色、免疫細胞化学染色
エナジードリンクの危険性 2015年6月23日 経営学部市場戦略学科MR3195稲沢珠依.
自動吸引は 在宅を変えるか 大分協和病院 院長         山本 真.
毎月レポート ビジネスの情報 (2016年7月号).
医療の歴史と将来 医療と医薬品産業 個人的経験 3. 「これからの医療を考える」 (1)医薬品の研究開発 -タクロリムスの歴史-
社会福祉調査論 第4講 2.社会調査の概要 11月2日.
2015年12月28日-2016年3月28日 掲載分.
2010度 民事訴訟法講義 補論 関西大学法学部教授 栗田 隆.
腫瘍学概論 埼玉医科大学国際医療センター 包括的がんセンター 緩和医療科/緩和ケアチーム 奈良林 至
“企業リスクへの考え方に変化を求められています。 トータルなリスクマネジメント・サービスをプロデュースします。“
情報漏えい 経済情報学科 E  西村 諭 E  釣 洋平.
金融班(ミクロ).
第11回 2009年12月16日 今日の資料=A4・4枚+解答用紙 期末試験:2月3日(水)N2教室
【ABL用語集】(あいうえお順) No 用語 解説 12 公正市場価格 13 債権 14 指名債権 15 事業収益資産 16 集合動産 17
基礎理論(3) 情報の非対称性と逆選択 公共政策論II No.3 麻生良文.
浜中 健児 昭和42年3月27日生まれ 東京都在住 株式会社ピー・アール・エフ 代表取締役 (学歴) 高 校:千葉県立東葛飾高校 卒業
COPYRIGHT(C) 2011 KYUSHU UNIVERSITY. ALL RIGHTS RESERVED
Blosxom による CMS 構築と SEO テクニック
記入例 JAWS DAYS 2015 – JOB BOARD 会社名 採用職種 営業職/技術職/その他( ) 仕事内容 待遇 募集数
ネットビジネスの 企業と特性 MR1127 まさ.
Future Technology活用による業務改革
ネットビジネス論(杉浦) 第8回 ネットビジネスと情報技術.
g741001 長谷川 嵩 g740796 迫村 光秋 g741000 西田 健太郎 g741147 小井出 真聡
自然独占 公共経済論 II no.5 麻生良文.
Autonomic Resource Provisioning for Cloud-Based Software
Webショップにおける webデザイン 12/6 08A1022 甲斐 広大.
物理的な位置情報を活用した仮想クラウドの構築
ハイブリッドクラウドを実現させるポイントと SCSKのOSSへの取組み
寺尾 敦 青山学院大学社会情報学部 第12回 情報デザイン(4) 情報の構造化と表現 寺尾 敦 青山学院大学社会情報学部
【1−1.開発計画 – 設計・開発計画】 システム開発計画にはシステム開発を効率的、効果的に実行する根拠(人員と経験、開発手順、開発・導入するシステム・アプリケーション・サービス等)を記述すること。 システム開発の開始から終了までの全体スケジュールを記載すること。 アプリケーション機能配置、ソフトウェア、インフラ構成、ネットワーク構成について概要を示すこと。
6 日本のコーポレート・ガバナンス 2008年度「企業論」 川端 望.
急成長する中国ソフトウェア産業 中国ソフトウェアと情報サービス産業の規模 総売上高は5年間で約5.3倍の成長
米国ユタ州LDS病院胸部心臓外科フェローの経験
公益社団法人日本青年会議所 関東地区埼玉ブロック協議会 JCの情熱(おもい)育成委員会 2011年度第1回全体委員会
次世代大学教育研究会のこれまでの活動 2005年度次世代大学教育研究大会 明治大学駿河台校舎リバティタワー9階1096教室
子どもの本の情報 大阪府内の協力書店の情報 こちらをクリック 大阪府内の公立図書館・図書室の情報
第2回産業調査 小島浩道.
〈起点〉を示す格助詞「を」と「から」の選択について
広東省民弁本科高校日語専業骨幹教師研修会 ①日本語の格助詞の使い分け ②動詞の自他受身の選択について   -日本語教育と中日カルチャーショックの観点から- 名古屋大学 杉村 泰.
■5Ahバッテリー使用報告 事例紹介/東【その1】 ■iphon4S(晴れの昼間/AM8-PM3) ◆約1時間で68%⇒100%
『ワタシが!!』『地域の仲間で!!』 市民が始める自然エネルギー!!
ポイントカードの未来形を形にした「MUJI Passport」
SAP NetWeaver を支える Microsoft テクノロジーの全貌 (Appendix)
ガイダンス(内業) 測量学実習 第1回.
Python超入門 久保 幹雄 東京海洋大学.
熱力学の基礎 丸山 茂夫 東京大学大学院 工学系研究科 機械工学専攻
京都民医連中央病院 CHDF学習推進委員会
資料2-④ ④下水道.
Accessによる SQLの操作 ~実際にテーブルを操作してみよう!~.
Presentation transcript:

これまでのあらすじ chapter 1: 情報を測る エントロピー,情報量,情報源の性質 chapter 2: 情報をコンパクトに表現する レポート課題 ... 本日締め切り

chapter 2: 情報をコンパクトに表現する

chapter 2の目的 情報源からの記号(列)を,効率よく(コンパクトに)符号化する 情報源符号化 データ圧縮 情報源符号化の目的: 通信に適した表現方式への変換 情報の中の無駄な部分を整理し,捨て去る 目標とする符号化方式: できるだけ正確に元の情報を復元できること できるだけコンパクトな情報表現を与えること 0101101 符号化 情報源

議論の順序 情報源符号化の基礎 一意復号可能性 瞬時復号可能性 ハフマン符号 ハフマン符号の構成法 ハフマン符号の拡張 データ圧縮の理論限界 今日の目標

用語について はじめに,情報源の記号ごとに符号化を行う方式を考える 𝑀: 情報源が生成する記号の集合 𝑀 の各記号に対し,{0, 1}上の系列を対応付ける 符号語: 𝑀の記号に対応付けられた{0, 1}上の系列 符号語の長さは,同一である必要ない(非等長符号) 符号: 符号語の集合 2種類の文字 {0, 1} を使用...2元符号 M 晴 曇 雨 C 00 010 101 符号語は3つ; 00, 010, 101 符号 C = {00, 010, 101} 011 は符号語ではない

符号化と復号 符号化... 与えられた記号から,対応する符号語を求めること 復号 ... 与えられた符号語から,対応する記号を求めること 晴 曇 雨 00 010 101 符号化 復号 encode = 符号化 decode = 復号 符号語間に,スペース,コンマ等の区切り記号は使わない 01000101101はOK, 010 00 101 101 はNG 「区切り記号 = 第3の文字」 ⇒ 「3元」符号を考えることになってしまう

一意復号可能性 符号は,一意に復号可能でないといけない 異なる記号が同じ符号語を持つのは,当然NG 異なる記号が異なる符号語を持つ,だけでも不十分 異なる記号系列は,異なる0-1系列に符号化されること a1 a2 a3 a4 C1 00 10 01 11 C2 011 111 C3 C4 C4 を使う場合... a1 a3 a1 a4 a2 0110 OK OK NG NG

一意性だけで十分か? C2 を使ってa1, a4, a4, a1を符号化,1bit/secでデータ送信 受信者が,最初の記号を確定できるのはいつか? 7秒経過後 ... 0111111 まで受信 次に 0 が来ると,0 - 111 - 111 - 0  a1, a4, a4, a1 次に 1 が来ると, 01 - 111 - 111  a2, a4, a4 7秒後でも,最初の記号すら確定できない  受信データのバッファが必要,復号遅延の問題...  動画ダウンロードだったら,どうなるか a1 a2 a3 a4 C2 01 011 111

× 瞬時復号可能性 実用的なシステムでは,瞬時に復号可能であることが望ましい 「符号語のパターンが出現したら,即時に復号して良い」 一意復号可能性の「上位」の性質 「瞬時復号可能」ならば「一意復号可能」である 符号 𝐶 が瞬時復号可能である必要十分条件: 任意の系列 𝑠∈ 0,1 ∗ に対し, 𝑠= 𝑐 1 𝑠 1 となる符号語 𝑐 1 ∈𝐶が存在するならば, 𝑠=𝑐 2 𝑠 2 となる他の符号語 𝑐 2 ∈𝐶 が存在しない × 𝑐1 𝑠1 𝑐2 𝑠2 =

語頭条件 符号が瞬時復号可能でないならば, 𝑠= 𝑐 1 𝑠 1 = 𝑐 2 𝑠 2 となる 系列𝑠∈ 0,1 ∗ と,二つの異なる符号語 𝑐 1 , 𝑐 2 が存在する 𝑐1 𝑠1 𝑐 1 と 𝑐 2 の長さは異なる 𝑐 1 は 𝑐 2 の語頭である,という ( 𝑐 1 のほうが短い場合) = 𝑐2 𝑠2 補題: 符号 C が瞬時復号可能である必要十分条件は,他の符号語の語頭となる符号語が存在しないこと (prefix condition, 語頭条件) a1 a2 a3 a4 C2 01 011 111 “0” は “01” と “011”の語頭 “01” は “011”の語頭

雑談:語頭条件とユーザインタフェース 語頭条件は,情報理論以外でも重要 graffiti (ver. 2) 2画の文字が出現 Palm Vx 1999発売 Sony Clie PEG-TH55 2004年発売 graffiti (ver. 2) 2画の文字が出現 語頭条件に反する “3-1”と書いたつもりが “3+” に... graffiti (ver. 1) すべて一筆書きでOK

語頭条件を確保するには 語頭条件を満たす符号の作り方: 全ての符号語を,同じ長さで設計する; 等長符号 符号語の最後(だけ)に「特殊パターン」を置く C = {011, 1011, 01011, 10011} ; “コンマ符号” ... どちらも,(後述する)効率がよくない 木構造を利用して符号語を選ぶ (「符号木」) 2元符号の場合,次数が2の木を利用 𝑘元符号の場合,次数が𝑘の木を利用 次数3の 符号木

符号の構成法(𝑘元の場合) 𝑀個の符号語を持ち,語頭条件を満たす𝑘元符号の作り方 葉を𝑀個持つような,次数𝑘の木𝑇を構成する 𝑇の各枝に,0から𝑘−1の値をラベル付けする 兄弟が同じラベルを持つことは禁止 根節点から葉節点まで木をたどり,途中のラベルを連接する  連接の結果得られる系列を符号語とする

構成例 𝑀=4個の符号語を持つ𝑘=2元符号を構成する Step 1 Step 2 Step 3 1 1 00 01 10 11 1 1 00 01 10 11 構成された符号は {00, 01, 10, 11}

構成例(続き) 他の構成方法もアリ; 異なる木を使う,異なるラベル付けを行う... C1={0, 10, 110, 111} 1 1 1 1 C1={0, 10, 110, 111} C2={0, 11, 101, 100} 1 C3={01, 000, 1011, 1010} どのように作っても,語頭条件は保証される  瞬時復号可能な符号となる

? 「最良な」瞬時復号可能符号 1 1 C1={0, 10, 110, 111} C3={01, 000, 1011, 1010} 1 1 C1={0, 10, 110, 111} C3={01, 000, 1011, 1010} C1の符号語のほうが,C3の符号語より短そう... 符号語の長さ = [1, 2, 3, 3] vs. [2, 3, 4, 4] もっとコンパクトな瞬時復号可能符号はあるか? たとえば 符号語の長さ= [1, 1, 1, 1]? 符号語の長さ = [1, 2, 2, 3]? 符号語の長さ = [2, 2, 2, 3]? ? どこに壁がある?

クラフトの不等式 定理: A) 𝑘元符号 {𝑐1, …, 𝑐𝑀} (| 𝑐 𝑖 | = 𝑙 𝑖 とする)が瞬時復号可能なら, 𝑘 − 𝑙 1 +…+ 𝑘 − 𝑙 𝑀 ≤1 (クラフトの不等式)が成り立つ ... 次ページで証明 B) もし 𝑘 − 𝑙 1 +…+ 𝑘 − 𝑙 𝑀 ≤1なら, 瞬時復号可能な 𝑘元符号 {𝑐1, …, 𝑐𝑀} で |𝑐𝑖| = 𝑙 𝑖 となるものが存在する ... 深さ 𝑙 𝑖 に葉節点を配置していけばよい

定理Aパートの証明(𝑘=2の場合) A) 2元符号 {𝑐1, …, 𝑐𝑀} (| 𝑐 𝑖 | = 𝑙 𝑖 とする)が瞬時復号可能なら, 2 − 𝑙 1 +…+ 2 − 𝑙 𝑀 ≤1 (クラフトの不等式)が成り立つ 証明:ℎ= max 𝑙 𝑖 とし, 2 ℎ− 𝑙 1 +…+ 2 ℎ− 𝑙 𝑀 ≤ 2 ℎ を示せばよい 高さℎの完全2分木を考える 深さℎにある節点の総数= 2 ℎ 符号語 𝑐 𝑖 =深さ 𝑙 𝑖 の節点,先祖・子孫に他の符号語ナシ 深さℎにある 𝑐 𝑖 の子孫の数= 2 ℎ− 𝑙 𝑖 よって 2 ℎ− 𝑙 𝑖 ≤ 2 ℎ 𝑐 1 𝑐 2 𝑐 3 2 ℎ ℎ=4 2 ℎ−2 2 ℎ−3 2 ℎ−4

具体例に戻って考える できるだけコンパクトな瞬時復号可能な 2元符号を作りたい 符号語の長さ = [1, 2, 2, 3]? … 2 −1 + 2 −2 + 2 −2 + 2 −3 = 9 8 >1 瞬時復号可能な符号は構成できない 符号語の長さ = [2, 2, 2, 3]? … 2 −2 + 2 −2 + 2 −2 + 2 −3 = 7 8 <1 瞬時復号可能な符号を構成可能...符号木を使えば簡単

次の段階へ 情報源符号化の基礎 一意復号可能性 瞬時復号可能性 ハフマン符号 ハフマン符号の構成法 ハフマン符号の拡張 データ圧縮の理論限界

「コンパクトさ」の指標 情報をコンパクトに表現する符号を作りたい 1個の記号を表現する符号語の長さの期待値を小さくしたい = 平均符号語長 𝑎1 𝑎2 : 𝑎𝑀 確率 𝑝1 𝑝2 𝑝𝑀 符号語 𝑐1 𝑐2 𝑐𝑀 長さ 𝑙1 𝑙2 𝑙𝑀 平均符号語長は 𝑖=1 𝑀 𝑝 𝑖 𝑙 𝑖 ビット (記号)

平均符号語長の計算例 記号 𝑎1 𝑎2 𝑎3 𝑎4 確率 0.4 0.3 0.2 0.1 𝐶1 10 110 111 𝐶2 111 110 10 110 111 𝐶2 111 110 10 𝐶3 00 01 10 11 𝐶1: 0.4×1+ 0.3×2+ 0.2×3+ 0.1×3 = 1.9 𝐶2: 0.4×3+ 0.3×3+ 0.2×2+ 0.1×1 = 2.6 𝐶3: 0.4×2+ 0.3×2+ 0.2×2+ 0.1×2 = 2.0 𝐶1 が最も効率よく(=コンパクトに)情報を表現できる(はず)

ハフマン符号 ハフマンアルゴリズム: 平均符号語長の小さな瞬時復号可能符号を作る方法 M 個の節点を準備し,各節点に記号の 確率を付与する (節点 = サイズ 1の木) 木が一個になるまで,以下の操作を繰り返す 確率最小の木を二個選択 ... T1, T2 とする 新しい節点を導入し, T1, T2 を新節点の子とする (二個の木を一個に併合) T1, T2 の確率の和を,併合してできた木の確率とする David Huffman 1925-1999

例 “資本の小さな会社の合併劇” 0.05 D 0.1 C 0.25 B 0.6 A 0.05 D 0.1 C 0.15 0.25 B 0.4 0.6 A 0.05 D 0.1 C 0.15 0.25 B 0.4 0.6 A 1.0 1

練習問題 A B C D E 確率 0.2 0.1 0.3 符号語 「等長符号」と平均符号語長を比べると,ありがたみがわかる

符号構成の自由度について ハフマンアルゴリズムの実行結果は,一意でない可能性も... 同じ確率を持つ節点が多数存在 枝へのラベル付けにも,自由度がある 異なる選択肢を取ると異なるハフマン符号ができあがる,が, 平均符号語長は,どの選択肢を取っても変わらない 0.4 a1 0.2 a2 a3 0.1 a4 a5 0.4 a1 0.2 a2 a3 0.1 a4 a5

ここまでのまとめ 情報源符号化の基礎 一意復号可能性 瞬時復号可能性 ハフマン符号 ハフマン符号の構成法 ハフマン符号の拡張 データ圧縮の理論限界

練習問題 A B C D E F 確率 0.3 0.2 0.1 符号語 右図に示す記号に対し ハフマン符号を構成し, その平均符号語長を求めよ