2015年に業務委託としてJuicerのインフラの構築、その後コンサルティング契約を経て、2017年に中途入社。Juicer事業部でJuicerが持っているデータに価値を与える仕事に従事。, bz2, xz, Deflate, gzip, zip, snappy, …圧縮に関しての名前です。, なんとなく見覚えがあるだけのものから、普段使いしているものまで色々あって、なんとなく使ってはいるけれど、それぞれどのような意図を持って使い分けたら良いのでしょうか。そもそもどんな違いがあるのでしょうか。, この違いがちゃんとわかっていたら、なんとなくかっこいい気がしませんか？というわけで、今回は圧縮アルゴリズムの歴史と、特性を追っていきたいと思います。, 圧縮をまず大きく大別すると、可逆圧縮と非可逆圧縮に分けられます。その名の通り、元に戻せる圧縮方法と、元には戻せない圧縮方法です。非可逆圧縮の用途には音声、画像や動画などの圧縮があります。, データとしてはわざと欠落させるけれど、人間の認識には影響の少ないようにするものがあります。用途、画像でよく使われるJPEGや動画でよく使われるMPEG-2などが非可逆圧縮になります。, 2017年末に日本でもローンチされた音楽ストリーミングサービスのDeezerは可逆圧縮(ロスレス)で音楽を配信するため、データを欠落させていないので高音質と言われています。, 非可逆圧縮も日々進歩していますが、今回は可逆圧縮について掘り下げて行きたいと思います。, 可逆圧縮は元に戻せる圧縮方式ですが、その方法はざっくりいうとデータの中に冗長な部分や特徴を見つけて、そこを元に戻せる形で削減する方法です。, 可逆圧縮で人間にも理解しやすい方法として、ランレングスというのがあります。日本語だと連長圧縮と言われていたりする、同じものが連続している部分に注目して圧縮する方法です。, この方法は同じ値が連続することが多く、出現する値の種類が少ない場合に非常に使いやすく、画像やFAXなどで使いやすい圧縮の方法になります。, 「Abraham Lempel」と「Jacob Ziv」の二人によって 1977年に誕生したLZ77と、その翌年に同じ原理でありながら、別の手法を使ったLZ78があります。, 1977年と40年も前に誕生した原理でありながら、今現在も使われている圧縮の方法の多くはLZ法を改良したものになっています。, LZ77はLZ法の初期のアルゴリズムで、1977年に誕生しました。既に出てきている文字の並び(単語)が再度出てきたら、それをより短い符号に置換えていくというアルゴリズムです。, しかし、事前に出てきたデータをすべて検索し、符号化しようとするとすべてをメモリに載せるもしくは、何度も読み込みなおす必要が出てきてしまうため、圧縮の速度に影響を及ぼしてしまいます。そのため、sliding windowsというどの程度遡るかを決めるウィンドウを設けて現実的な速度を確保しています。, LZ78はLZ77の翌年に誕生したアルゴリズムで事前に出てきたデータを符号化するという点では同じなのですが、LZ77との違いとして辞書を利用します。辞書を利用する利点としては、LZ77ではsliding windowsと呼ばれるある範囲のみ遡って符号化しますが、LZ78の場合は明示的に破棄しない場合は出現したものすべてを辞書として保持します。, ここまでで上げたLZ77とLZ78が大きく2つの源流となっており、辞書型とsliding window型と呼ばれています。, LZ77を元に、不一致だったとしても符号化してしまい長くなってしまうという点を修正しています。この修正によりLZSSは劇的な性能向上を果たしており、現在の圧縮プログラムで多く使われるアルゴリズムになっています。, 圧縮アルゴリズムでLZ77と書かれている場合でも実装はLZSSが使われていることもあります。, LZ77系で私の主観として最も普及しているのがDeflateです。Deflateと聞いてもピンと来ないかもしれませんが、gzip, zip と言えばどれくらい普及しているか想像がつくのではないでしょうか。, deflateは、LZ77（実際にはその変種のLZSS）でデータを「文字そのもの」または （一致長, 一致位置） ペアに符号化する。その結果のうち、「文字そのもの」および「一致長」を合わせて一つのハフマン符号で符号化し、「一致位置」を別のハフマン符号で符号化する。deflateのハフマン符号化は、ブロック毎に符号を(再)構築する方式で、ダイナミックハフマン符号（英: Dynamic Huffman coding）と呼んでいる。, LZ78を元に作られたアルゴリズムでありますが、アルゴリズムどうこうというよりも、特許によって業界に旋風を巻き起こしました。, LZWの開発者の一人である、Terry Welch（LZWのWはWelchのW）は当時Sperryという会社の従業員であり、LZWの特許はSperryという会社が保有していました。その後SperryはBurroughsと合併し、Unisysとなり、LZWの権利もUnisysが持つことになります。Unisysになっても、LZWの利用に関し利用料を請求しないとしていたため、LZWはgifやtiffなどの画像の圧縮方式として普及していきました。, ところが、普及した後にUnisysは「LZWを用いてGIFを生成する機能を持つすべて商用ソフトウェアにライセンス利用の支払いを求める」と言い出したのです。単なる圧縮アルゴリズムであればよかったのですが、広く普及したgifという画像フォーマットに使われているために、大きな騒動になっていきました。, 最初は商用ソフトウェアに限定されていたものも一段落すると、今度はフリーソフトウェアにまでこの権利を主張し始めます。さらに、ライセンス料を支払っていないソフトウェアで作られたgifに関しては利用者からライセンス料を徴収するとまで言い出したので、手におえません。, そんな中GNUプロジェクトは早期にUnix由来のファイル圧縮プログラムのCompress(LZW) を捨て、GNU zip (gzip)をリリースしています。画像についてもいち早くgifではなく、pngを推奨していました。, LZ Familyには入りませんが,ブロックソート、MTF、ハフマン符号化を組み合わせた圧縮方法で、圧縮率がDeflateよりも高かったことと、動作の安定性で高く普及しました。しかし、Deflateに比べると、圧縮伸張時間で劣るため完全に置き換えるものではないが、OSのイメージや各種パッケージの配布などで利用されています。, bzip2は2となっていますが、もともとbzipというソフトウェアを開発していました。しかし、bzipで利用していた算術符号化は抜け穴が無いと言われる程に特許がとられており、算術符号化は使えないという事で開発を断念しています。, 算術符号化の部分をハフマン符号化に置換えbzip2になったという経緯があります。この算術符号化についてはのちにRange Coderによって解決されていきます。, 後半にRange Coderを利用することで、圧縮に時間はかかるが伸張の時間は短く、さらに圧縮率はDeflate やbzip2よりも高いという特徴があります。Range Coderは算術符号を利用していますが、特許に抵触しないように作られており、安心して使える算術符号です。, 冒頭にあった bz2, xz,Deflate, gzip, zip, snappy, … といった文字列がここまで出てきていないですね。, ここまでのお話は圧縮のアルゴリズムであり、どのようにデータを圧縮するかという話でした。しかし実際にコンピュータ上で使う時にはファイルとして扱う事も多く、圧縮プログラムはファイルとして出力することができるものが多いです。ここまでに出てきたアルゴリズムはDeflateであればlibzというライブラリにまとまり、gzipという圧縮プログラムで使用されています。, xzや7zと言った新しめの高圧縮プログラムではLZMA2,LZMAというアルゴリズムが利用されています。bzip2の場合はアルゴリズムと圧縮プログラムがほぼイコールですが、他の圧縮プログラムについては圧縮プログラムと圧縮アルゴリズムに別名が付いていることが多いです。, この関係性を覚えておくことで、実は解凍できてしまうものがあったり、圧縮プログラムのライセンスの違いをすり抜け利用することができたりします。, 圧縮のプログラムはデータの圧縮は行うけれど、ファイルをまとめる機能を持っていないことがほとんどです。.tarという拡張子を見たことは無いですか？, .tar.gzやtar.bz2といった形で目にする事が多いかと思います。これはtarというアーカイバプログラムで複数ファイルを1つのファイルにまとめ、まとめたものをgzipやbzip2で圧縮しています。, この1つのファイルにまとめるプログラムのことをアーカイバと呼びます。zipというプログラムはアーカイバと圧縮プログラムの両方を兼ね備えた便利なツールになっています。, 大きなファイルをインターネット越しで配布する場合、圧縮するのは一回に対して、複数回ダウンロードされるので、速度よりも圧縮率の高さを優先します。, サイトの閲覧のように小さいデータを高速に圧縮・伸張する必要がある場合には速度を優先したいので、Deflateのような圧縮率よりも圧縮、伸張時間が速いアルゴリズムを利用します。Apacheのmod_deflateというモジュールを触ったことのある人もいるのでは無いでしょうか？, 今回は紹介しませんでしたが、Facebookが開発したzstdやGoogleが開発したSnappyなども高速な圧縮アルゴリズムとして出てきています。こういった圧縮のアルゴリズムの違いを理解しておくことで、ネットワークの帯域を節約したり、もしくはコンピューティング能力の節約をすることが可能となってきます。, クラウド時代、そこまで気にすることはなくなってきましたが、今一度改めて圧縮について学ぶことで、コストを削減することが可能かもしれません。, 知っておきたい用語集からSEOの基本的な考え方、Goolgeが提唱する良いウェブページの定義など、全50ページに及び徹底解説をしています。今からSEOを始める方も、今の施策に疑問を感じている方も、まずはこちらをご覧ください。, 株式会社PLAN-Bは確実な成果に特化したデジタルマーケティングカンパニーです。4,000社を超えるマーケティング支援実績を元に、企業に役立つ情報を発信します。, A Universal Algorithm for Sequential Data Compression, Compression of individual sequences via variable-rate coding, http://hidekatsu-izuno.hatenablog.com/entry/2016/08/06/085923. ランレングス圧縮(連長圧縮)とは、可逆圧縮に分類されるアルゴリズムです。ある連続したデータをデータ1つ分と連続した長さで表して圧縮します。ファイル圧縮機能についてc#の実装サンプルがあります。 用語「ランレベル (Runlevel)」の説明です。正確ではないけど何となく分かる、IT用語の意味を「ざっくりと」理解するためのIT用語辞典です。専門外の方でも理解しやすいように、初心者が分かりやすい表現を使うように心がけています。 ランレングス圧縮関連の問題例 5. 先のランレングス法では文字単位でデータを見ました。 今度は見方を少し変えて，データの「固まり」で考えてみましょう。 図1のデータを見ると“@---”といった文字列が何度か現れていることがわかります。 Copyright © Nikkei Business Publications, Inc. All Rights Reserved. ランレングス圧縮（Run Length Encoding）とは 2. はじめに 1. 0. ランレングス圧縮の魅力 4. 圧縮アルゴリズム (1) ランレングス法. ある日のこと，ぼーっとした頭で仕事をしていると，同僚がそれはもう満面の笑みを浮かべて「プログラムで使っている画像データを圧縮するためにLZSS＊1を実装してみたんですよ。ふふん，どうよ」と話しかけてきました。「ぬあ?」とそれがどうした的に返事をしつつも，ふと気づいたのは，何らかの圧縮プログラムやアルゴリズムを作った経験を持つプログラマは意外に多いということです。すでにzlibなどの著名な圧縮ライブラリが公開されていますが，「ブロックソート」や「PPM」などの新しい圧縮方法が日夜開発されています。, どうも圧縮というのは，プログラマ心をそそる何かがあるようです。今回はそんな圧縮アルゴリズムの不思議で魅力的なところを紹介します。パズルのような圧縮アルゴリズムの楽しさを感じていただければと思います。, 「ジュゲムジュゲム…」と長い名前の代名詞であるジュゲムを人に何回も伝えることを想像してみてください。とんでもなく面倒そうですね。ですが，ジュゲムを“あ”という1文字で表すと決めたらどうでしょう。伝える相手には，「“あ”というのは“ジュゲム…”のことだよ」とあらかじめ1回だけ教えておきます。そうすれば，以後「“あ”ですよ“あ”」と言うだけで，相手は「ジュゲム…ですよジュゲム…」と言っていることがわかります。「ジュゲム…」という長い文字列を“あ”という1文字に置き換えることで，文章全体を短くできたわけです。, 圧縮の基本となる考え方は，このように「長いデータを短いデータに置き換える」ことです。つまり，データの中を調べ，何度も出てくるデータをもっと短いデータに置き換えて，全体のサイズを小さくする方法が圧縮アルゴリズムです。以下では圧縮アルゴリズムの例を三つ見てみることにしましょう。, 図1を眺めてみると“@”や“-”などの文字が横に連続して何度も出てきます。何となくもったいないように感じます。ここへ「同じ文字が連続して出ていたらそれを『文字×連続した個数』に置き換える」というルールを適用してみます。, いちばん下のラインを取り出して試してみましょう。行頭からスペースの文字が16個連続しています。これを[ ×16]に置き換えます。その先にある“=”も9個あるので[=×9]と置き換えて…とこれを行末まで繰り返します。すると，, [ ×16]`#@*[=×9]@[ ×4]`@[ ×4]`@[ ×7]-8[ ×12], という文字列になりました。見た目でもだいぶ短くなった感じがします。元に戻すときは，[ ×16]というのがあったら，スペースを16個ぶん置くようにします。これを全部の文字について実行すれば，乾燥麺がお湯を吸って膨らむがごとく元の文字列に戻ります。, これは，ランレングス法と呼ばれる最も基本的な圧縮方法です。実際にプログラムとして実装する場合には，[ ×16]などの部分をデータとしてどう表すかを決めなくてはなりません。簡単なのは，圧縮データの目印となる値（例えば0xff＊2）を決め，その後ろに「連続する文字」と「個数」並べる方法です。圧縮対象となるデータがASCII文字だけを含むなら，ASCIIが使わない最上位ビットをフラグとして利用する手もあります。, 先のランレングス法では文字単位でデータを見ました。今度は見方を少し変えて，データの「固まり」で考えてみましょう。図1のデータを見ると“@---”といった文字列が何度か現れていることがわかります。このようなデータは，「ある文字列が以前に出ていたら，その部分に対する参照で置き換える」ことで圧縮することができます。これはLZ77＊3と呼ばれる圧縮アルゴリズムです。, この方法は，圧縮よりもまず，展開する場合を先に考えてみるとわかりやすいでしょう。すでに現れた文字列を参照する場合には，目印となるマークに続いて，参照する文字列の相対的な位置と文字列長を書き込むことにします。今仮に，展開先バッファに「 @=**-」と出力した段階で，「相対位置＝8，文字列長＝2」という参照情報に出会ったとします。この場合は，現在位置から8文字ぶん前の位置から2文字だけコピーして展開先バッファに出力します。この例では「 @=**- 」となってスペースが二つ増えることになります。, 圧縮する際には，これから圧縮する文字列が，どの位置から何文字ぶん一致しているかを調べなくてはなりません。何度も文字列を比較するため，単に先頭から順に調べていくやり方だと処理が非常に遅くなってしまいます。そこで，比較を始める位置とその最初の1文字をまとめて管理したり，それらをツリー構造で管理してそこから探索したりするといった工夫をするのが一般的です。, この記事は会員登録で続きをご覧いただけます。次ページでログインまたはお申し込みください。, 2020年11月24日（火） 14：00～17:25 2020年11月25日（水）14:00-17:25, 2020年10月1日に起こったシステム障害と、過去の東証関連記事をまとめました。最新情報を随時追加します。. #ref(): File not found: "gazou1.jpg" at page "もっとも単純なランレングス圧縮" ここで注意しておきたいのはデータが連続しないときも符号をつかないといけないということです。 でないとプログラム側がデータか符号かがわかりませんから。 ランレングス圧縮【連長圧縮 / RLE / Run Length Encoding】とは、最も基本的な圧縮アルゴリズムの一つで、連続して現れる符号を、繰り返しの回数を表す値に置き換える方式。圧縮によって内容を損なわない可逆圧縮を行う。例えば、「AAAABBBBCCCC」という文字列を圧縮する場合、「A」が4回、「B」 … データ圧縮の仕組みは、主にデータが有する冗長性・出現確率性・不要性を考慮して変換し、符号化します。 最初の冗長性の例では、ランレングス符号化があります。 これは繰り返されるデータからなるストリングで構成されます。 Road to Millionaireは、予め株価の変動推移が与えられ、所持金を最大にするように株の売買をした結果を求める問題です*4。2日間で株価が変動しないところはその間で売買を行っても、変化がないため考慮が不要です。そこで、変動推移の数字列をランレングス圧縮してしまいます。そうすると圧縮後の数字列は変化点のみになり、この数値を使うことで株価変動無し時の考慮を省いて単純化して、売買アルゴリズムを実装するができるようになります！凄くないですか！？, ランレングス圧縮の効果を3つ挙げました。大きなデータを圧縮し、データサイズを小さくできる効果に加えて、抽象化してデータを考察、操作できるようになることが魅力と思います。また、簡単なアルゴリズムの割に応用範囲が広いところも良いなと思います。 [競プロ用]ランレングス圧縮まとめ - Qiita この方法をランレングス圧縮といい、圧縮の中では最も基本的な方法です。 単純なランレングスだとうまく行かない例 上のように簡単なやり方でも結構小さくなるデータもあるのですが、例えば今度は下のような例はどうでしょう？ ランレングス圧縮 (RLE: Run Length Encoding) とは、データ圧縮アルゴリズムの一種で、可逆圧縮に分類されます。このアルゴリズムでは、ある連続したデータをデータ1つ分と連続した長さで表して圧縮します。例えば "AAAAA" を "A" が 5回続くデータなので、 "A5" という風に圧縮します。, 「データ * 連続回数」の形に変換することになるので、1つのデータが長く続くデータや、そもそも出現するデータの種類が少ないデータなどは、圧縮効率が高くなる傾向にあります。, 逆に、データがあまり連続しないデータについては、圧縮効率が悪いどころか圧縮前よりデータサイズが大きくなってしまうこともあります。例えば "ABCDE" という5文字を「データ * 連続回数」の形に変換すると "A1B1C1D1E1" となり2倍のサイズになってしまいます。, 連続しないデータでも圧縮効率を下げないように改良したアルゴリズムとして、PickBits と呼ばれる方法もあります。, 上述の通り、ランレングス圧縮は連続しないデータ部分の圧縮効率が悪いどころか、逆にデータ量が増えてしまいます。その欠点を改良したものが、PickBits と呼ばれるアルゴリズムです。基本的な考え方は変わらないのですが、連続しないデータ部分が続く部分をフラグ管理することで圧縮率を高めます。, "AAABCDEE" という文字を通常のランレングス圧縮で圧縮すると、"A3B1C1D1E2" となり元のデータより大きなデータになってしまいます。これを PickBits では次のように圧縮します。, PickBits では連続しないデータが続く部分についてカウントし、「-(カウント) + 連続しないデータ」として表現します。上記の例では "-3BCD" の部分に該当します。これは 3つのデータ "B", "C", "D" について連続しない(つまり1文字のみ)という意味になります。, 通常圧縮は上記のように文字列で見るのではなく、バイト単位で圧縮を行います。したがって、1ビット分をマイナスのフラグとして使うと、連続数として表せるのが最大128までとなります。これ以上の連続するデータ部分が通常のランレングス圧縮に比べ圧縮効率が低下してしまいます。, 圧縮対象のファイルを通常のランレングス圧縮を用いて圧縮したファイルを生成するサンプルコードです。バイト単位で読み込んだファイル内容から圧縮ファイルを生成します。また生成した圧縮ファイルを元に戻す(解凍する)ことで圧縮前のファイルと同等のファイルを生成します。, 以下のようなモノクロビットマップ画像は非常に効率の良い圧縮が行われますが、日本語のテキストファイルなどはあまり効率よく圧縮されません。.