データを 圧 縮 する 大 量 のデータを 小 さく 収 納 するには? 国 立 情 報 学 研 究 所 定 兼 邦 彦 0 年 月 日
データとは データ 圧 縮 とは 数 値 の 集 まり,.5, 00, 3.4, 意 味 のあるデータが 情 報 文 字, 画 像, 音 声, 動 画 など コンピュータ 中 では, 全 てのデータは0,の 列 で 表 される 圧 縮 とは ビット データを 表 現 する0, 列 の 長 さを 短 くすること 圧 縮 されたデータから 元 のデータを 求 めることを, 復 元, 伸 長, 復 号, 解 凍 などと 言 う
可 逆 圧 縮 完 全 に 元 に 戻 る 圧 縮 法 文 書,プログラムなど 非 可 逆 圧 縮 種 類 の 圧 縮 法 人 間 には 区 別 できない 程 度 の 違 いがある 画 像 (JPEG), 音 声 (mp3), 動 画 (MPEG) など 今 日 の 話 は 可 逆 圧 縮 のみ 3
本 の 検 索 人 が 検 索 するとき 本 の 索 引 を 使 う 索 引 に 載 っていない 単 語 は 見 つからない 計 算 機 で 検 索 するとき 本 の 索 引 のようなデータ 構 造 を 用 いる 索 引 の 見 出 しを 増 やせば,データ 量 ( 索 引 のページ 数 ) も 増 える 全 単 語 を 索 引 に 載 せると 本 のページ 数 が 倍 以 上 になる 4
NTCIR-4 PATENT ( 日 本 語 特 許 公 報 全 文 5 年 分 ) 文 書 数 3,496,5 索 引 の 例 サイズ 3.8G bzipでの 圧 縮 サイズ 5.G 従 来 の 索 引 ( 接 尾 辞 配 列 ) + データ 680.4G 簡 潔 データ 構 造 ( 索 引 +データ).6G 約 /30 に 圧 縮 5
簡 潔 データ 構 造 データに 索 引 を 追 加 しても,サイズが 増 えない (データも 圧 縮 できる) 圧 縮 されていない 索 引 を 用 いた 場 合 とほぼ 同 じ 速 度 で 検 索 ができる 6
データ 圧 縮 の 基 本 7
次 のデータは 何 を 表 しているでしょう? 000000000000000 000000000000 00000000000000000 00000000000000000 000 0 00 000 8D 9 国 00 0 00 0 97 A7 立 000 0 0 8F EE 情 00 00 000 95 F 報 000 00 0 0 8A 77 学 000 00 00 000 8C A4 研 000 0 000 00 8B 86 究 000 000 00 8F 8A 所 8
サクラサク データ 圧 縮 法 長 い 文 章 を 短 いものに 置 き 換 える 本 当 はビットで 良 い ( = 合 格, 0 = 不 合 格 ) 全 ての 圧 縮 法 はこれを 行 っている ビットだと, 種 類 の 文 章 しか 表 現 できない 特 定 の 文 章 だけでなく,どんな 文 章 でも 表 現 できる ようにするには? 9
プライバシー 保 護 のため この 画 像 の 自 動 ダウンロードをブロックしました モールス 符 号 ( 信 号 ) 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
次 の 符 号 は 何 を 表 しているでしょう? - -- ---- 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 --
一 意 に 復 元 可 能 な 符 号 符 号 を 先 頭 から ( 左 から) 見 ていったときに, 通 り にしか 復 号 されない 符 号 モールス 符 号 では 空 白 を 入 れる 必 要 がある 一 意 ではない - 文 字 符 号 文 字 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 --
コンピュータで 表 現 するには? モールス 符 号 には 短 点, 長 点, 空 白 の3 種 類 の 文 字 が 必 要 これらを 0, のビットで 表 現 する 必 要 がある 例 : 短 点 0 長 点 空 白 0 - - - -- -- X Y Z 0000000 3
各 文 字 の 符 号 の 最 後 に, 空 白 を 表 す0 をつけると 一 意 に 復 号 可 能 になる E: 0 0 I: 0 0 0 A: - 0 0 0 木 の 内 部 に 符 号 が 割 り 当 てられない 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
どのような 符 号 が 良 いか ABCABCAABAACAABC を 圧 縮 する 場 合 符 号 : A 00 B 0 C 0 のとき 000000000000000000000000 8 + 4 + 4 = 3 ビット 符 号 : A 00 B C 0 のとき 00000000000000000000 8 + 4 + 4 = 8 ビット 符 号 3: A 0 B 0 C のとき 000000000000 8 + 4 + 4 = 4 ビット 0 0 0 A B C 0 0 A C B 0 0 5 A B C
符 号,,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
エントロピー 文 字 列 中 の 文 字 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 = + + 4 + 4 log 4 4 = + 3 4 log 4 7
どんな 符 号 でも, 文 字 あたりの 平 均 ビット 数 は エントロピーよりも 小 さくならない 符 号 3の 文 字 あたりの 平 均 ビット 数 は エントロピーと 一 致 する H = log = + + 4 + 4 log 4 4 = Aの 符 号 長 Aの 出 現 確 率 + 3 4 log 4 4 = 6 3 で 8
ハフマン 符 号 (95 年 ) 平 均 符 号 長 が 最 小 の (= 最 も 圧 縮 できる) 符 号 作 り 方 出 現 頻 度 が 最 小 の 文 字 と, 番 目 に 少 ない 文 字 に 0 と を 割 り 当 てる それらの 文 字 を 合 わせて,つの 文 字 にする A: 8 回, B: 4 回, C: 4 回 のとき,Bに0, Cにを 割 り 当 てる 0 B C B と C を 合 わせて 文 字 D が 8 回 現 れたとみなす 文 字 が 種 類 になるまで 繰 り 返 す 9
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
データ 圧 縮 の 欠 点 は? 復 元 が 遅 い 一 部 分 だけ 復 元 することが 難 しい ABCABCAABAACAABC の0 文 字 目 は? 符 号 : A 00 B 0 C 0 のとき 0 = 0ビット 目 を 見 ればいい 0 3 0 0 0 0 000000000000000000000000 符 号 3: A 0 B 0 C のとき 何 ビット 目 を 見 ればいいか 分 からない 000000000000
符 号 のように 全 ての 文 字 が 同 じビット 数 の 符 号 を 固 定 長 の 符 号 と 呼 ぶ 文 字 はlog σビットで 表 現 される(σ:アルファベットサイズ) コンピュータで 扱 うデータは 固 定 長 の 符 号 で 表 現 されている ( 無 圧 縮 ) 符 号 3のように 可 変 長 の 符 号 を 使 うと 圧 縮 できるが 復 元 が 遅 くなる 先 頭 から 文 字 ずつ 復 元 していかなければならない 000000000000
部 分 復 号 の 高 速 化 ABCABCAABAACAABCの0 文 字 目 を 復 元 する 000000000000 途 中 から 復 元 するために, 符 号 の 開 始 位 置 を 記 憶 文 字 目 は ビット 目 から 6 文 字 目 は 9 ビット 目 から 文 字 目 は 6 ビット 目 から 6 文 字 目 は 3 ビット 目 から どの 文 字 を 復 元 する 場 合 でも, 最 大 5 文 字 復 元 すればいい 開 始 位 置 は 何 ビットで 記 憶 できる? A 0 B 0 C 3
開 始 位 置 の 記 憶 文 字 列 の 長 さを n とする (n = 6) アルファベットサイズ σ は n 以 下 とする 圧 縮 後 のサイズを m とする m n log σ n log n d 文 字 おきに 開 始 位 置 を 記 憶 する (d = 5) n/d 個 の 開 始 位 置 を 記 憶 する 個 の 開 始 位 置 は 何 ビットで 表 現 できるか 開 始 位 置 は から m の 整 数 log m ビットで 表 現 できる 4
全 ての 開 始 位 置 を 記 憶 するには nlog m d nlog ( nlog n) d = log n とすると, 開 始 位 置 は n ビット 以 下 で 記 憶 できる 文 字 あたり ビット 以 下 d n log n d ある 文 字 を 復 元 するために 必 要 な 時 間 は d に 比 例 する < ビット 必 要 d を 大 きくすると 圧 縮 率 が 良 くなるが 復 元 が 遅 くなる 5
開 始 位 置 の 圧 縮 d を 小 さくすると 文 字 の 復 元 は 早 くなるが, サイズが 大 きくなってしまう 開 始 位 置 をビット 列 で 表 現 する ABCABCAABAACAABC 000000000000 圧 縮 された 文 字 列 00000000000000000000 5 文 字 おきの 開 始 位 置 ビット 列 の 番 目 のの 位 置 () 文 字 目 番 目 のの 位 置 (9) 6 文 字 目 3 番 目 のの 位 置 (6) 文 字 目 4 番 目 のの 位 置 (3) 6 文 字 目 6
簡 潔 データ 構 造 7
ビットベクトル 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 = 00000000000000000000 n = 4 8
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
大 ブロックの 長 さ m が log c n 以 下 のとき 長 さ ½ log n の 小 ブロックに 分 割 小 ブロックを 葉 に 持 つ 完 全 log n 分 木 を 構 築 木 のノードには,その 子 孫 のベクトルのの 数 を 格 納 大 ブロック 内 の の 数 は log n 各 ノードの 値 は log log n bits 9 log n 3 4 O(c) 0 0 B = 000000000000000000 m log c n 30
B は 約 n ビット (n + o(n)) で 表 現 でき,rank と select は 答 えを 圧 縮 しないで 記 憶 した 場 合 と 同 じ 時 間 ( 定 数 時 間 ) で 計 算 できる これを 簡 潔 データ 構 造 と 呼 ぶ 3
順 序 木 の 簡 潔 データ 構 造 各 節 点 を 対 応 する 括 弧 のペアで 表 現 n 節 点 で n bits (サイズの 下 限 と 一 致 ) 既 存 手 法 は 複 雑 でサイズが 大 きい 6 3 4 5 7 8 BP 6 3 4 5 7 8 ((()()())(()())) 3
圧 縮 全 文 索 引 ライブラリ フリーソフトとして 公 開 http://researchmap.jp/sada/csalib/ NTCIR-4 PATENT ( 日 本 語 特 許 公 報 全 文 993-997) 文 書 数 3,496,5 サイズ (タグ 除 去, utf8) 3.8G bzipでの 圧 縮 サイズ 5.G 圧 縮 索 引 のサイズ.6G 従 来 の 索 引 ( 接 尾 辞 配 列 ) 680.4G 文 書 中 の 頻 出 パタンの 列 挙 36 秒 ( 文 字 列 長 の0.0% 以 上 の 頻 度 ) 出 力 例 [9988894586,99844534] key = 図 である [8935087764,89475903] key = ることを 特 徴 とする [8897875,8937686] key = することができる 33