PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

うたろうあいきょう
9 years ago
Views:

1 データを圧縮する大量のデータを小さく収納するには? 国立情報学研究所定兼邦彦 0 年月日

2 データとはデータ圧縮とは数値の集まり,.5, 00, 3.4, 意味のあるデータが情報文字, 画像, 音声, 動画などコンピュータ中では, 全てのデータは0,の列で表される圧縮とはビットデータを表現する0, 列の長さを短くすること圧縮されたデータから元のデータを求めることを, 復元, 伸長, 復号, 解凍などと言う

3 可逆圧縮完全に元に戻る圧縮法文書,プログラムなど非可逆圧縮種類の圧縮法人間には区別できない程度の違いがある画像 (JPEG), 音声 (mp3), 動画 (MPEG) など今日の話は可逆圧縮のみ 3

4 本の検索人が検索するとき本の索引を使う索引に載っていない単語は見つからない計算機で検索するとき本の索引のようなデータ構造を用いる索引の見出しを増やせば,データ量 ( 索引のページ数 ) も増える全単語を索引に載せると本のページ数が倍以上になる 4

5 NTCIR-4 PATENT ( 日本語特許公報全文 5 年分 ) 文書数 3,496,5 索引の例サイズ 3.8G bzipでの圧縮サイズ 5.G 従来の索引 ( 接尾辞配列 ) + データ 680.4G 簡潔データ構造 ( 索引 +データ).6G 約 /30 に圧縮 5

6 簡潔データ構造データに索引を追加しても,サイズが増えない (データも圧縮できる) 圧縮されていない索引を用いた場合とほぼ同じ速度で検索ができる 6

7 データ圧縮の基本 7

8 次のデータは何を表しているでしょう? D 9 国 A7 立 F EE 情 F 報 A 77 学 C A4 研 B 86 究 F 8A 所 8

00000000000000000 000 0 00 000 8D 9 国 00 0 00 0 97 A7 立 000

9 サクラサクデータ圧縮法長い文章を短いものに置き換える本当はビットで良い ( = 合格, 0 = 不合格 ) 全ての圧縮法はこれを行っているビットだと, 種類の文章しか表現できない特定の文章だけでなく,どんな文章でも表現できるようにするには? 9

10 プライバシー保護のためこの画像の自動ダウンロードをブロックしましたモールス符号 ( 信号 ) 830 年代に提案短点と長点 - の組み合わせ長点は短点 3つ分の長さ SOS = 英語で使われる頻度の高い e, t は短い符号, - になっているデータ圧縮文字符号文字符号 A - N - B - O --- C - - P -- D - Q -- - E R - F - S G -- T - H U - I V - J --- W -- K - - X - - L - Y - -- M -- Z -- 0

は短い符号, - になっているデータ圧縮文字符号文字符号 A - N - B - O --- C - - P -- D - Q

11 次の符号は何を表しているでしょう? D X Y Z G O つの文字を表す符号がどこで切れているのか分からない一意に復号可能ではないモールス符号では, 文字間には短点 3つ分の空きを入れる X Y Z D 文字符号文字符号 A - N - B - O --- C - - P -- D - Q -- - E R - F - S G -- T - H U - I V - J --- W -- K - - X - - L - Y - -- M -- Z --

12 一意に復元可能な符号符号を先頭から ( 左から) 見ていったときに, 通りにしか復号されない符号モールス符号では空白を入れる必要がある一意ではない - 文字符号文字 A - N - 符号 B - O --- E - T C - - P -- D - Q -- - E R - I A N M F - S G -- T - H U - I V - H S U R W D - K G V F L P J B X C Y Z Q O J --- W -- K - - X - - L - Y - -- M -- Z --

13 コンピュータで表現するには? モールス符号には短点, 長点, 空白の3 種類の文字が必要これらを 0, のビットで表現する必要がある例 : 短点 0 長点空白 X Y Z

14 各文字の符号の最後に, 空白を表す0 をつけると一意に復号可能になる E: 0 0 I: A: 木の内部に符号が割り当てられない I 0 0 E 0 0 A N T M O H S V F U L R P W J B D X C K Y Z G Q 4

15 どのような符号が良いか ABCABCAABAACAABC を圧縮する場合符号 : A 00 B 0 C 0 のとき = 3 ビット符号 : A 00 B C 0 のとき = 8 ビット符号 3: A 0 B 0 C のとき = 4 ビット A B C 0 0 A C B A B C

0 のとき 00000000000000000000 8 + 4 + 4 = 8 ビット符号 3: A 0 B 0 C

16 符号,,3の中で, 符号 3が一番小さくなっている多く現れる文字 (A) の符号が短いから A: 8 回, B: 4 回, C: 4 回どのような符号を使うと一番圧縮できるか? 文字 A, B, C の符号の長さを x, y, z とする文字列の符号の長さは L = 8x + 4y + 4z 一意に復号できる符号のみ考える + + を満たす必要がある x y z (クラフトの不等式 ) L が最小になる x, y, z は? x =, y =, z = つまり符号 3が最適 6

17 エントロピー文字列中の文字 c の出現確率を p(c) とすると, 文字列のエントロピーは次のように定義される H = c A p c) log ( 文字 A の出現確率は文字 B, C の出現確率は p( c) A: アルファベット ( 文字の集合 ) A = {A, B, C,,Z} 8 = 6 4 = 6 4 H = log = log 4 4 = log 4 7

18 どんな符号でも, 文字あたりの平均ビット数はエントロピーよりも小さくならない符号 3の文字あたりの平均ビット数はエントロピーと一致する H = log = log 4 4 = Aの符号長 Aの出現確率 log 4 4 = 6 3 で 8

19 ハフマン符号 (95 年 ) 平均符号長が最小の (= 最も圧縮できる) 符号作り方出現頻度が最小の文字と, 番目に少ない文字に 0 とを割り当てるそれらの文字を合わせて,つの文字にする A: 8 回, B: 4 回, C: 4 回のとき,Bに0, Cにを割り当てる 0 B C B と C を合わせて文字 D が 8 回現れたとみなす文字が種類になるまで繰り返す 9

20 A: 8 回, D: 8 回なので,Aに0, Dにを割り当てる 0 A と D を合わせて文字 E が6 回現れたとみなす終了 A A D (E) 0 (D) 0 B C ハフマン符号の平均符号長 L は H L < H+ 0

21 データ圧縮の欠点は? 復元が遅い一部分だけ復元することが難しい ABCABCAABAACAABC の0 文字目は? 符号 : A 00 B 0 C 0 のとき 0 = 0ビット目を見ればいい符号 3: A 0 B 0 C のとき何ビット目を見ればいいか分からない

22 符号のように全ての文字が同じビット数の符号を固定長の符号と呼ぶ文字はlog σビットで表現される(σ:アルファベットサイズ) コンピュータで扱うデータは固定長の符号で表現されている ( 無圧縮 ) 符号 3のように可変長の符号を使うと圧縮できるが復元が遅くなる先頭から文字ずつ復元していかなければならない

23 部分復号の高速化 ABCABCAABAACAABCの0 文字目を復元する途中から復元するために, 符号の開始位置を記憶文字目はビット目から 6 文字目は 9 ビット目から文字目は 6 ビット目から 6 文字目は 3 ビット目からどの文字を復元する場合でも, 最大 5 文字復元すればいい開始位置は何ビットで記憶できる? A 0 B 0 C 3

24 開始位置の記憶文字列の長さを n とする (n = 6) アルファベットサイズ σ は n 以下とする圧縮後のサイズを m とする m n log σ n log n d 文字おきに開始位置を記憶する (d = 5) n/d 個の開始位置を記憶する個の開始位置は何ビットで表現できるか開始位置はから m の整数 log m ビットで表現できる 4

25 全ての開始位置を記憶するには nlog m d nlog ( nlog n) d = log n とすると, 開始位置は n ビット以下で記憶できる文字あたりビット以下 d n log n d ある文字を復元するために必要な時間は d に比例する < ビット必要 d を大きくすると圧縮率が良くなるが復元が遅くなる 5

26 開始位置の圧縮 d を小さくすると文字の復元は早くなるが, サイズが大きくなってしまう開始位置をビット列で表現する ABCABCAABAACAABC 圧縮された文字列文字おきの開始位置ビット列の番目のの位置 () 文字目番目のの位置 (9) 6 文字目 3 番目のの位置 (6) 文字目 4 番目のの位置 (3) 6 文字目 6

27 簡潔データ構造 7

28 ビットベクトル B: 長さ n の 0, ベクトル B[0]B[] B[n ] 操作 rank(b, x): B[0..x] = B[0]B[] B[x] 内のの数 select(b, i): B の先頭から i 番目のの位置 (i ) select 操作で開始位置が求まる select(b, ) = 文字目の開始位置 select(b, ) = 9 6 文字目の開始位置 select(b, 3) = 6 文字目の開始位置 B = n = 4 8

29 Selectの求め方 B を, を log n 個含む大ブロックに分割大ブロックごとに通りのデータ構造を使い分ける大ブロックの長さが log c n を超えるとき log n 個のの位置をそのまま格納つの大ブロックでそのような大ブロックは最大個全体で n log c = 4 とすると c log n n log n 3 n log bits bits n log n = log n c log n 3 n bits 9

30 大ブロックの長さ m が log c n 以下のとき長さ ½ log n の小ブロックに分割小ブロックを葉に持つ完全 log n 分木を構築木のノードには,その子孫のベクトルのの数を格納大ブロック内のの数は log n 各ノードの値は log log n bits 9 log n 3 4 O(c) 0 0 B = m log c n 30

31 B は約 n ビット (n + o(n)) で表現でき,rank と select は答えを圧縮しないで記憶した場合と同じ時間 ( 定数時間 ) で計算できるこれを簡潔データ構造と呼ぶ 3

32 順序木の簡潔データ構造各節点を対応する括弧のペアで表現 n 節点で n bits (サイズの下限と一致 ) 既存手法は複雑でサイズが大きい BP ((()()())(()())) 3

33 圧縮全文索引ライブラリフリーソフトとして公開 NTCIR-4 PATENT ( 日本語特許公報全文 ) 文書数 3,496,5 サイズ (タグ除去, utf8) 3.8G bzipでの圧縮サイズ 5.G 圧縮索引のサイズ.6G 従来の索引 ( 接尾辞配列 ) 680.4G 文書中の頻出パタンの列挙 36 秒 ( 文字列長の0.0% 以上の頻度 ) 出力例 [ , ] key = 図である [ , ] key = ることを特徴とする [ , ] key = することができる 33

KINGSOFT Office 2016 動作環境対応日本語版版共通利用上記動作以上以上空容量以上他接続環境推奨必要 2

KINGSOFT Office 2016 動作環境対応日本語版版共通利用上記動作以上以上空容量以上他接続環境推奨必要 2 目次動作環境特長方法方法起動終了方法方法操作方法使方使方使方詳細設定使方 KINGSOFT Office 2016 動作環境対応日本語版版共通利用上記動作以上以上空容量以上他接続環境推奨必要 2 KINGSOFT Office 2016 特長主特長以