データ圧縮について
データを圧縮するって言われても、よくわかんねーじゃん。
ほんであれですわ、データ圧縮。
元に戻せるzipとかrarとかの可逆圧縮と、
元に戻せないjpgとかmp3みたいな非可逆圧縮があんのよ。
jpgとかmp3とか、ものすげぇ圧縮できるけど、完全に元に戻せないの。
どーでもいいところのデータ消してっから。
どーでもいいデータってなんじゃらほいって方は、食品偽装について考えてみよう。
例えば100円寿司で出るウナギ。
あれウナギじゃねぇのよ。
でもウナギじゃん、食うとウナギとしか思えないじゃん。
「ウナギっぽいからまぁいいんじゃね」
オリジナル:ウナギ・・・?
データ圧縮:100円回転寿司マジック
データ解凍:ウナギ!
これが非可逆圧縮。
可逆圧縮は、もうどうしようもなくオリジナルのものに戻したい場合。
例えば、水で元の大きさに戻るワカメ。
水に漬けたらワカメじゃなくてタバコになったら嫌でしょ?俺はうれしいけど。
オリジナル:ワカメ
データ圧縮:すげぇ縮んだワカメ
データ解凍:やっぱワカメ
これが可逆圧縮。
ほんで、今回は可逆圧縮について考えを深めていきましょうということなんですけども、
なんでかっつーと実はjpgとかmp3とかの非可逆圧縮の方が難しいんですよ。
デジタルでアナログを扱うのは非常に難しい。難しいことはよくわからない。難しいこと反対。
なので最初から最後までデジタルな可逆圧縮の方がアホ(俺)でも理解できるって寸法ですわ。
とりあえず、全世界のマニアが常に編集をして巨大なマニア本と化しているとっても素敵なWikipediaを見る。
データ圧縮 (Wikipedia)
わからん。
Wikipediaは超絶マニアが編集しててマニア向けすぎてわかんねー。
わかんねーから俺が解説してやんよ。
ってことなのよ。
まず、圧縮が得意とするデータは
「連続したデータ」
「同じ文字が何回も出現するデータ」
となっております。なんのこっちゃ、とね。
「連続したデータ」については、例えば
「AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDD」(40文字)
という文字列の場合。(ABCDそれぞれ10文字ずつ)
ポイントとしては同じ文字が連続している点。
この場合だとそれぞれ連続して10文字ずつになっていますので、
「A*10文字、B*10文字、C*10文字、D*10文字」
とすることができます。
単純に
「A10B10C10D10」(12文字)
とかやっちゃえば、12文字になります。
元のデータが40文字だったので、28文字もお得です。
極論で言えば、
Aという文字が1億文字連続である1億byte = 100Mbyteのデータがあったとしても、
この理屈で
「A100000000」(10文字)
に変換してあげれば、なんと100Mbyteがたったの10byteになってしまうんです。
逆にこの方法、連続していない文字に対しては逆効果。
「ABCD」
だった場合、それぞれ1文字ずつなので
「ABCD」
となり、変わりません。
また
「AABBCCDD」
とそれぞれ2文字ずつの場合でも
「A2B2C2D2」
となり、変わりません。
一般的な文字列の場合、連続して同じ文字を書くことはあまりないので、実際はあまり効果が無いんですねぇ。
西尾さんみたいに「キィィィィィィィィィ」とか書く場合にはもってこいなんですけど。
次に「同じ文字が何回も出現するデータ」について。
これは、いっぱい出る文字列をまとめちゃおうって寸法です。
例えば徹英語辞典があります。
徹英語辞典には以下の単語が登録されています。
1ページ目:hoge
2ページ目:fuck
3ページ目:unko
なんとも悲しい辞書です。
この辞書と、次の文字列があったとします。
「unko moreru, fuck daze. hogehoge」(32文字、ちなみに「ウンコ漏れる、ファックだぜ。ほげほげ」)
これを辞書と照らし合わせながら変換してあげるという感じです。
「3 moreru, 2 daze. 11」(20文字)
数字は辞書のページ番号になっています。
これだけでも12文字節約できました。
この場合の辞書はあらかじめ決められた辞書、というわけではなく、
文字列を全て参照し、多い順ランキングを作って、最も多く使われる文字を辞書にしてから、
ページ番号に変換してあげる、といった感じです。
例えば
「rHOGEoiuhgHOGEpncwyHOGEfpcpHOGEficuhpHOGE」
という文字だったら、なんか「HOGE」って文字がいっぱい入ってるから「HOGEは1にしよう」ってなって、
「r1oiuhg1pncwy1fpcp1ficuhp1」
に変換できるわけです。
ただ、この手法は圧縮したデータと「辞書データ」も必要になるため、短い文字列だと不利です。
ものすげぇ長い文章とかだと役に立ちます。
長編小説で主人公の名前が「1」になったり。(>>1さん・・・)
ということで、とにかく
「連続したデータ」
「同じ文字が何回も出現するデータ」
が重要ということがわかっていただけたかと思います、わからなかったらごめんなさい。
データ圧縮の作業は基本的に2段階あって、
・モデル化
・符号化
に分かれます。
んなことしらんわアホって感じなので、次回はとりあえずモデル化について解説します。
データを圧縮するって言われても、よくわかんねーじゃん。
ほんであれですわ、データ圧縮。
元に戻せるzipとかrarとかの可逆圧縮と、
元に戻せないjpgとかmp3みたいな非可逆圧縮があんのよ。
jpgとかmp3とか、ものすげぇ圧縮できるけど、完全に元に戻せないの。
どーでもいいところのデータ消してっから。
どーでもいいデータってなんじゃらほいって方は、食品偽装について考えてみよう。
例えば100円寿司で出るウナギ。
あれウナギじゃねぇのよ。
でもウナギじゃん、食うとウナギとしか思えないじゃん。
「ウナギっぽいからまぁいいんじゃね」
オリジナル:ウナギ・・・?
データ圧縮:100円回転寿司マジック
データ解凍:ウナギ!
これが非可逆圧縮。
可逆圧縮は、もうどうしようもなくオリジナルのものに戻したい場合。
例えば、水で元の大きさに戻るワカメ。
水に漬けたらワカメじゃなくてタバコになったら嫌でしょ?俺はうれしいけど。
オリジナル:ワカメ
データ圧縮:すげぇ縮んだワカメ
データ解凍:やっぱワカメ
これが可逆圧縮。
ほんで、今回は可逆圧縮について考えを深めていきましょうということなんですけども、
なんでかっつーと実はjpgとかmp3とかの非可逆圧縮の方が難しいんですよ。
デジタルでアナログを扱うのは非常に難しい。難しいことはよくわからない。難しいこと反対。
なので最初から最後までデジタルな可逆圧縮の方がアホ(俺)でも理解できるって寸法ですわ。
とりあえず、全世界のマニアが常に編集をして巨大なマニア本と化しているとっても素敵なWikipediaを見る。
データ圧縮 (Wikipedia)
わからん。
Wikipediaは超絶マニアが編集しててマニア向けすぎてわかんねー。
わかんねーから俺が解説してやんよ。
ってことなのよ。
まず、圧縮が得意とするデータは
「連続したデータ」
「同じ文字が何回も出現するデータ」
となっております。なんのこっちゃ、とね。
「連続したデータ」については、例えば
「AAAAAAAAAABBBBBBBBBBCCCCCCCCCCDDDDDDDDDD」(40文字)
という文字列の場合。(ABCDそれぞれ10文字ずつ)
ポイントとしては同じ文字が連続している点。
この場合だとそれぞれ連続して10文字ずつになっていますので、
「A*10文字、B*10文字、C*10文字、D*10文字」
とすることができます。
単純に
「A10B10C10D10」(12文字)
とかやっちゃえば、12文字になります。
元のデータが40文字だったので、28文字もお得です。
極論で言えば、
Aという文字が1億文字連続である1億byte = 100Mbyteのデータがあったとしても、
この理屈で
「A100000000」(10文字)
に変換してあげれば、なんと100Mbyteがたったの10byteになってしまうんです。
逆にこの方法、連続していない文字に対しては逆効果。
「ABCD」
だった場合、それぞれ1文字ずつなので
「ABCD」
となり、変わりません。
また
「AABBCCDD」
とそれぞれ2文字ずつの場合でも
「A2B2C2D2」
となり、変わりません。
一般的な文字列の場合、連続して同じ文字を書くことはあまりないので、実際はあまり効果が無いんですねぇ。
西尾さんみたいに「キィィィィィィィィィ」とか書く場合にはもってこいなんですけど。
次に「同じ文字が何回も出現するデータ」について。
これは、いっぱい出る文字列をまとめちゃおうって寸法です。
例えば徹英語辞典があります。
徹英語辞典には以下の単語が登録されています。
1ページ目:hoge
2ページ目:fuck
3ページ目:unko
なんとも悲しい辞書です。
この辞書と、次の文字列があったとします。
「unko moreru, fuck daze. hogehoge」(32文字、ちなみに「ウンコ漏れる、ファックだぜ。ほげほげ」)
これを辞書と照らし合わせながら変換してあげるという感じです。
「3 moreru, 2 daze. 11」(20文字)
数字は辞書のページ番号になっています。
これだけでも12文字節約できました。
この場合の辞書はあらかじめ決められた辞書、というわけではなく、
文字列を全て参照し、多い順ランキングを作って、最も多く使われる文字を辞書にしてから、
ページ番号に変換してあげる、といった感じです。
例えば
「rHOGEoiuhgHOGEpncwyHOGEfpcpHOGEficuhpHOGE」
という文字だったら、なんか「HOGE」って文字がいっぱい入ってるから「HOGEは1にしよう」ってなって、
「r1oiuhg1pncwy1fpcp1ficuhp1」
に変換できるわけです。
ただ、この手法は圧縮したデータと「辞書データ」も必要になるため、短い文字列だと不利です。
ものすげぇ長い文章とかだと役に立ちます。
長編小説で主人公の名前が「1」になったり。(>>1さん・・・)
ということで、とにかく
「連続したデータ」
「同じ文字が何回も出現するデータ」
が重要ということがわかっていただけたかと思います、わからなかったらごめんなさい。
データ圧縮の作業は基本的に2段階あって、
・モデル化
・符号化
に分かれます。
んなことしらんわアホって感じなので、次回はとりあえずモデル化について解説します。
Comment投稿
