平成23年度 第5回 Q&A - イベント - 国立情報学研究所 / National Institute of Informatics

イベント / EVENT

平成23年度 第5回 Q&A

第5回 2011年11月2日(水)

大量のデータを小さく収納するには?
データを圧縮する

定兼 邦彦(国立情報学研究所 准教授)

講演当日に頂いたご質問への回答(全18件)

※回答が可能な質問のみ掲載しています。

簡潔データ構造と圧縮接尾辞配列とでは、どちらが圧縮率が高いですか?またどちらが検索が速いですか?

圧縮接尾辞配列は、簡潔データ構造の一種で、文字列検索用のものです。

符号の列から文字に直したり、文字の列から意味を知ったりする為には送信側と受信側で同じ表(ルール)を持っていなければならないと思います。お互いに同じ表(ルール)を持つためには、別なルートで表(ルール)をやりとりしなければならないのでしょうか?

その通りです。文字の符号を送る前に表を送ります。また、文字を送りながら表を徐々に作っていく方法もあります。後者の例には動的ハフマン符号やLZ78符号があります。

(1)bzip 2はどのような圧縮方法でしょうか?(2)索引は圧縮の時、いらないのでは?(3)ハフマン符号がHと等しくなる、あるいは等しくならないのはどのような場合でしょうか?

(1) bzip2は圧縮接尾辞配列の元になった圧縮法なので基本的な考えは同じですが、bzip2ではメモリ量の制約から文字列を短く切ってそれぞれを独立に圧縮します。(2) 検索を必要としない圧縮であれば索引は不要です。(3) 一言では難しいですが、文字の出現確率が 1/2 のべき乗以外のものがあると等しくはなりません。

(1)日本語とか英語とか言語固有の最適な圧縮法はあるでしょうか?(2)JPEG、mp3、MPEGの圧縮方法の違いを教えてください。

(1) 最適かどうかを調べることは無理ですが、自然言語の場合には文法に関する知識を使えば圧縮率は上がります。しかしそのような圧縮法は実用化されていません。(2) どの手法も細かい部分を省略して圧縮率を上げるという点では共通していますが、実際の圧縮手法は異なりますので簡単には説明できません。

モールス符号において、よく使われるものに短い符号が割り当てられるということでしたが、何を基準に使われるものと使われないものに分けたのでしょうか?

英語の文章で使われる頻度の高い文字から順に短い符号を割り当てます。具体的に何の文章かは分かりません。

"解凍"の語源、北海道のプログラマ、LHAの方ですか?

その通りです。吉崎栄泰氏です。

音(mp3→WAV)や動画(MPEG)の圧縮したものは復元はできないのでしょうか?

音の場合は元々一定の時間間隔で区切って圧縮しているので部分復元可能です。動画の場合もキーフレーム単位の部分復元は可能です。

エントロピーなどに出てくる「log2 〇」という量は無理数になったりして計算できなくなることはないのですか?

その通りですので近似をします。

簡潔データ構造を使っている例は他に何がありますか?

Google IMEでは、単語の辞書を簡潔データ構造で圧縮しているようです。

(1)部分解凍はどのような時に使われるのでしょうか?利用シーンを教えてください。(2)圧縮されたものから何かを探す時は文字列を探すことが多いと思うのですが、説明では〇番目を見つける方法しかなく、なぜ〇番目だけで文字が探せるのかがよく分かりませんでした。

(1) たくさんのデータがあるときはまとめて圧縮ことで圧縮率を上げることができます。その場合は部分解凍があると便利です。(2) これは説明しませんでしたが、圧縮接尾辞配列では別の簡潔データ構造を用いて効率的な文字列検索ができます。

(1)可逆圧縮は学問的に研究しつくされているのか?(2)特許の壁は?

(1) 情報理論の分野で今も活発に行われています。(2) 以前はLZWや算術符号の特許の問題がありましたが、多くのものはすでに切れています。

「データを圧縮したまま使える最新の手法」というのが「簡潔データ構造」なのか?

その通りです。

(1)現在のコンピュータは処理のbit数が1byteである。連続的な圧縮bitはどのように処理されるか?(2)簡易データ構造は、圧縮/解凍を自動的にできるのか。全文検索に対応できるか?(3)画像データ等はピクセルとバイトに対応している。これは別の圧縮/解凍の原理の工夫?

(1) 1バイト(8ビット) に複数の符号を詰め込みます。(2) 圧縮接尾辞配列という簡潔データ構造を用いれば全文検索や部分解凍ができます。(3) バイト単位になっているのは処理の高速化のためです。

事例では〇番目の文字を探していましたが検索の場合は〇番目というよりも「文字列」を探したいと思うのですが...それでも見つかるのでしょうか?

圧縮接尾辞配列を用いればできます。圧縮接尾辞配列の内部で、○番目のデータを見つけるという処理が使われています。

圧縮の実用性、効用性の最新のもの(圧縮ソフト)を知りたかった。ですが、スライドの最後に紹介されたHPのURLを知りたかった。

圧縮率がいいものは7zipやLZMAがあります。私の作成したものは http://researchmap.jp/sada/csalib/ にあります。

スライド5について(1)従来の索引(接尾辞配列)+データの場合の検索に要する時間に比べると簡潔データ構造(索引+データ)の場合はどの程度検索に要する時間は増加しますか? (索引を用いないデータを検索する時間とほぼ同じとのことでしたが・・・)(2)簡潔データ構造のデータサイズの合計が21。6GBとのことですが、索引とデータはそれぞれどのくらいのサイズですか?

(1) 簡潔データ構造(圧縮接尾辞配列)では、数倍~数十倍遅くなってしまいますが、従来の索引をハードディスクに置くよりは高速です。(2) 圧縮されたデータが19G、索引が2G程度です。

スライド5について:日本語は冗長性が高いとのことですが、(データとしての)言語の冗長性はどのような要因で決まるのでしょうか? 他言語(英語? 中国語? ハングル?)との比較でご教示頂ければ幸いです。

言語の冗長性については専門家ではないので分かりませんが、言語による違いはあまり無いと思います。

部分復号の高速化で「どの文字を復元する場合でも最大5文字復元すればよい」とありますが、5文字の根拠は何でしょうか?

符号の開始位置を5文字おきに格納するとそうなります。

shimin 2011-qa_5 page2550

注目コンテンツ / SPECIAL