Google-Snappyという圧縮ライブラリの存在を知り、他にどんなものがあるか調べてみました。
⇧ 上記サイト様によると、Google-Snappyは、C++で実装されてるようです。
データ圧縮アルゴリズムのライブラリいろいろ
最近(2017年12月3日に調べた段階)のものを上げるとこんな感じでしょうか?
名前 | 使用言語 | 会社 | 開発元 | リリース | ライセンス |
---|---|---|---|---|---|
Zstandard (Zstd) |
C | Yann Collet | 2015/1/25 | BSDライセンス | |
Brotli | C | Jyrki Alakuijala Zoltán Szabadka |
2015/9 | Apache license | |
Zopfli | C | Lode Vandevenne Jyrki Alakuijala |
2013/2 | Apache License 2.0 | |
Lizard (旧LZ5) |
- | - | - | - | BSD 2-Clauseライセンス |
LZ5 | - | - | - | - | - |
LZ4 | C | - | Yann Collet | 2011/4/24 | BSDライセンス |
かなり動きが激しいですね。Yann Colletさん、Jyrki Alakuijalaさんが有名なんですかね。ほとんどC言語で作られているみたいですね。
データ圧縮とは?
Wikipediaさんの見解によると、
というより正確には非可逆圧縮はデータ圧縮ではない。
可逆圧縮は統計的冗長性を特定・除去することでビット数を削減する。可逆圧縮では情報が失われない。
非可逆圧縮は不必要な情報を特定・除去することでビット数を削減する。しかしここで「不必要な」とは、例えばMP3オーディオの場合「ヒトの聴覚では通常は識別できない」という意味であり、冒頭の「情報量を保ったまま」という定義を破っている。
データファイルのサイズを小さくする処理は一般にデータ圧縮と呼ばれるが、データを記録または転送する前に符号化するという意味では情報源符号化である。
どっちやねん...ということみたいです。ちなみに、MP3と音楽の流れとかは『誰が音楽をタダにした?』が面白いです。
今回使っていきたいと思っている Zstandard は「可逆圧縮」のアルゴリズムであるということで、可逆圧縮についてもう少し見ていきます。
可逆圧縮とは?
Wikipediaさんによると、
可逆圧縮(かぎゃくあっしゅく)とは、圧縮データを復元した時に、圧縮前の入力データが完全に復元されるような圧縮方法である。基本的には、入力データの統計的冗長性(出現する符号の偏り、規則性)を利用して、情報を失うことなくより稠密なデータに変換する。
となっており、データの中の特定の個所(統計的冗長性)に着目してデータを符号化することのようです。符号化は、
符号化(ふごうか)とは、アナログ信号やデジタルデータに特定の方法で、後に元の(あるいは類似の)信号またはデータに戻せるような変換を加えることである。
一般的には、エンコードするための機器・回路・プログラムをエンコーダ、デコード(記事内後述を参照)するための機器・回路・プログラムをデコーダと呼んでいる。
となっています。
では、「可逆圧縮」の符号化にはどんな種類があるかというと、
連長圧縮 (RLE)
例えば、画像には数ピクセル同じ色が並んだ領域がよくみられる。そこでピクセル単位に色情報を並べて表現する代わりに、「n個の赤のピクセル」という形で符号化できる。このような種類の方法は連長圧縮(RLE)と呼ばれる。
多くの可逆圧縮で使われている方法として、出現頻度(確率)の高いものに短い符号を、出現頻度の低いものに長い符号を割り当てることで、データ全体でみたときの平均符号長を短くする方法がある。これをエントロピー符号化と呼び、具体的な方法としてハフマン符号化や算術符号化などがある。
拡大情報源
LZ77(Lempel)、Lempel–Ziv–Storer–Szymanski (LZSS)
LZ77 (Lempel–Ziv) およびそれを改良したLempel–Ziv–Storer–Szymanski (LZSS) という圧縮法は、可逆記録方法としては最もよく使われているアルゴリズムである。
Deflate
Lempel–Ziv–Welch (LZW)
Lempel–Ziv–Welch (LZW) はGIFで採用されている。
LZR (Lempel-Ziv–Renau)
LZ
LZでは、データに繰り返し出現する記号列をテーブルを使って置換する方式を採用している。多くのLZ系の技法では、このテーブルを動的に生成しつつ入力を先頭から順次処理していく。テーブル自体はハフマン符号で符号化されることが多い(例えば、SHRI、LZX)。LZXはDeflateよりも効率が良く、マイクロソフトのCAB形式などで使われている。また、ハフマン符号に代わりRange Coderを採用したLZMAやLZMA2はさらに圧縮率が良い。
乱数アルゴリズム(Prediction by Partial Matchingなど)
圧縮効率が最も高い可逆圧縮法は乱択アルゴリズムを導入したもので Prediction by Partial Matching などがある。
文法圧縮(Sequitur、Re-Pair、MPMなど)
文法圧縮を使った技法は、繰り返しが非常に多い場合に高い圧縮率を達成でき、同一あるいは関連する種の生物学的データ群、頻繁に改版される文書群、インターネットアーカイブなどの用途がある。文法圧縮では、入力文字列から文脈自由文法を構築する。コードが公開されているアルゴリズムとしては、Sequitur、Re-Pair、MPMがある。
⇩ 圧縮前に行うことで圧縮を効果的に行えるようにしてくれるようです。
⇩ アルゴリズムを組み合わせることで、圧縮を効果的にできるようです。
これらの技法をさらに洗練させるため、統計的予測と算術符号と呼ばれるアルゴリズムを組み合わせる。算術符号は Jorma Rissanen が考案し、Witten、Neal、Cleary がそれを実用的な技法に発展させ、ハフマン符号より優れた圧縮率を達成するようになった。統計的予測が文脈に強く依存する場合のデータ圧縮によく採用されている。二値画像圧縮の標準であるJBIG、文書(スキャン画像)圧縮の標準であるDjVuなどで使われている。テキスト入力システム Dasher は、いわば逆算術符号化器である。
ん~、あふれんばかりの圧縮技術の熱量ですね。いろいろ出てきましたが、『可逆圧縮』とは何か?ということを要約すると、
圧縮したデータを圧縮前と変わらない状態に戻せる
ってことですかね、たぶん。
Zstandardとは?
Wikipediaさんによると、
Zstandard(Zstd)は2015年からFacebookに所属しているYann Collet によって開発された可逆圧縮アルゴリズムである。 またCで書かれた前述のアルゴリズムのリファレンス実装の名前でもある。 この実装のバージョン1は2016年8月にフリーソフトウェアとして公開された。
Zstandardは辞書式圧縮アルゴリズム(LZ77)とFinal Stateエントロピー (tANS)ステージのエントロピー符号化を併用している。
ということみたいです。
JNI(Java Native Interface)とは?
まだ、出てきてない言葉ですが、
Java Native Interface (JNI) は、Javaプラットフォームにおいて、Javaで記述されたプログラムと、他の言語(たとえばCやC++など)で書かれた、実際のCPUの上で動作するコード(ネイティブコード)とを連携するためのインタフェース仕様である。
Java言語からネイティブコードを利用するためのABIと、逆にネイティブコードからJavaバイトコードを動作させるためのバーチャルマシンを利用するためのAPIの2つから成る。
JNIを使うことで、Java言語のバーチャルマシンで動作させるには処理速度の面で不利とされる計算量の多いプログラムを部分的にネイティブコードに置き換えて高速化したり、標準クラスライブラリからはアクセスできないオペレーティングシステムの機能を利用するプログラムを、あたかも通常のJavaクラスのように呼び出したりできるようになる。Java言語以外のJava VM上で動作する言語からも利用可能である。
ということらしく、今回使いたいZstandard がC言語で記述されているので、それをJavaで使えるようにしてくれるみたいです。
逆に、他の言語でJavaを使うこともできるみたいですね。
JNA (Java Native Access) とは?
JNIがあれば、JNAもあるらしい。
⇧ JNIの実装は結構に難しいみたいですね...。
Java Native Access (JNA) とは、JavaプログラムがJava Native Interfaceを用いずにネイティブの共有ライブラリにアクセスする方法を提供するライブラリである。
JNA は最小限の作業でネイティブコードにアクセスできることを目指して設計されており、決まりきったアクセスコードを書いたりグルーコードの生成を行ったりせず、ネイティブコードへ正しく簡単にアクセスすることを最優先としている(ただし、性能にも注意が払われている)。
JNAライブラリはネイティブコードを呼び出すためにlibffiを用いており、名前を指定してライブラリをロードするネイティブの関数を用いて、目的のライブラリ関数の関数ポインタを取得する。
ネイティブコードにアクセスする過程で静的なバインディング、ヘッダファイル、またコンパイルは必要ない。アプリケーションの開発者はJavaのインターフェイスを用いて対象のネイティブライブラリの関数や構造体を記述する。
これによって、JNIコードを記述しビルドする大きな労力をかけずにきわめて簡単にネイティブプラットフォームの機能を利用することができる。
残念ながら、Zstandardは、2017年12月3日(日)現在、jniしか用意されてないっぽいですね(涙)。
Zstandard(Java用のライブラリ)をダウンロード
Zstandard - Real-time data compression algorithm にアクセスします。
下の方にスクロールすると、言語別にライブラリの導入の仕方が掲載されているので、今回はJava のURLをクリックします。
ページ遷移したら、下の方にスクロールし、
pom.xmlを使わない場合(動的Webプロジェクトなど)は、
https://repo1.maven.org/maven2/com/github/luben/zstd-jni/ にアクセスします。
バージョンごとのライブラリを選択してダウンロードできます。今回は、「1.3.2-6/」を選択しました。
「zstd-jni-1.3.2-6.jar」 のリンクをクリック。
毎回思うんですが、jarファイルをダウンロードするときの警告、止めて欲しいですね。「保存」を選択。
ダウンロードされました。jniという言葉が含まれているので、このjarは、「JNI(Java Native Interface)」ということになるようですね。
動的Webプロジェクトの作成
Eclipseを起動し、「パースペクティブ」が「Java EE」になっている状態で、「ファイル」>「新規(N)」>「動的 Web プロジェクト」を選択。
「プロジェクト名(M):」を入力し、「ターゲット・ランタイム(U)」でTomcatのバージョンを選択し、「ワーキング・セット」にプロジェクトを追加する場合は、「新規(W)...」か「選択(E)...」で。(Eclipse NeonをインストールしたときにTomcatも含める設定にしていた場合、Tomcat 8までは使えるようになっていると思われます。自分はTomcat 9を別途インストールしています。)
「次へ(N)>」をクリック。
「次へ(N)>」をクリック。
「完了(F)」をクリック。
プロジェクトができました。
libにzstd-jni-1.3.2-6.jarを配置
「WEB-INF」>「lib」にダウンロードした jarファイルを配置します。
ダウンロードした jarファイルを「コピー(C)」し、
「WEB-INF」>「lib」を右クリックした状態で、「貼り付け(P)」を選択。
「zstd-jni-1.3.2-6.jar」が配置されました。
Servletクラスを作成
まずは、Servletを作成。
「Javaリソース」>「src」を選択した状態で右クリックし、「新規(N)」>「サーブレット」を選択。
「Java パッケージ(K):」、「クラス名」を適当に入力し、「次へ(N)>」をクリック。
「URL マッピング(U):」を変更してます。(「URL マッピング(U):」のテキストエリアをダブルクリックすると変更ダイアログが出て編集できます。)
「次へ(N)>」をクリック。
「完了(F)」をクリック。
サーブレットが用意できました。
「WEB-INF」>「file」>「sample.txt」を作成して適当な文字をコピペして保存しておきます。自分は、10000000文字保存しました。サイズ的には「60,000,000 バイト」となってました。
ファイルを編集
Servletファイルを編集します。 (本当はJSPファイルに出力するつもりだったんですが、時間が無く今回は直接サーブレットで出力してます。)
package servlet; import java.io.IOException; import java.nio.charset.StandardCharsets; import java.nio.file.Files; import java.nio.file.Path; import java.nio.file.Paths; import javax.servlet.ServletContext; import javax.servlet.ServletException; import javax.servlet.annotation.WebServlet; import javax.servlet.http.HttpServlet; import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; import com.github.luben.zstd.Zstd; /** * Servlet implementation class ZstandardTest */ @WebServlet("/zstandardTest") public class ZstandardTest extends HttpServlet { private static final long serialVersionUID = 1L; /** * @see HttpServlet#HttpServlet() */ public ZstandardTest() { super(); // TODO Auto-generated constructor stub } /** * @see HttpServlet#doGet(HttpServletRequest request, HttpServletResponse response) */ protected void doGet(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException { // 文字コードを『UTF-8』に設定 response.setContentType("text/html; charset=" + StandardCharsets.UTF_8.toString()); // テキストファイルまでのパスの取得 ServletContext context = this.getServletContext(); String path = context.getRealPath("/WEB-INF/file/sample.txt"); // ファイル生成 Path txtFilePath = Paths.get(path); byte[] bytes = Files.readAllBytes(txtFilePath); // zstandard(zstd-jni)のメソッド利用 int[] level = {1, 3, 6, 9, 16}; byte[] compressed = Zstd.compress(bytes, level[0]); byte[] decompressed = Zstd.decompress(compressed, bytes.length); // 出力 response.getWriter() .append("圧縮: ") .append("" + compressed.length +"<br>") .append("展開: ") .append("" + decompressed.length); } /** * @see HttpServlet#doPost(HttpServletRequest request, HttpServletResponse response) */ protected void doPost(HttpServletRequest request, HttpServletResponse response) throws ServletException, IOException { // TODO Auto-generated method stub doGet(request, response); } }
⇩ Zstandard(zstd-jni)のメソッドの使い方は、Scalaで記述されたものOnlyかしら?
⇧ JNIの実装部分については、ライブラリでやってくれているみたいですね。『zstd-jni/src/test/scala/Zstd.scala』に使い方が載ってるっぽいですね。
Scalaも勉強せねばですね...。
Scala(スカラ(SKAH-lah)はオブジェクト指向言語と関数型言語の特徴を統合したマルチパラダイムのプログラミング言語である。名前の「Scala」は英語の「scalable language」に由来するものである。
ScalaはJavaプラットフォーム(Java仮想マシン)上で動作し、既存のJavaのプログラムと容易に連携させることができる。また、過去には下記のプラットフォームもサポートしていたが、現在は開発が中断している。
サーバー起動、ブラウザで確認
サーバーで実行します。プロジェクトを選択した状態で右クリックし、「実行(R)」>「1 サーバーで実行」を選択。
「サーバー」が選択されていることを確認し、「次へ(N)>」。
「構成済み(C):」にプロジェクトが追加されていることを確認し、「完了(F)」。
ブラウザで「http://localhost:8080/プロジェクト名/@WebServletの値」 でアクセスします。(自分の場合ですと、『http://localhost:8080/ZsTest/zstandardTest』ととなります。)
見事に圧縮されてますね。時間を計測してないですが、他の方の情報だと、かなり速いみたいです。
hidekatsu-izuno.hatenablog.com
フロントエンド覚えること多すぎる問題という記事を前に見かけたことがありますが、サーバーサイドも勉強すること多いですね(涙)。
今回はこのへんで。