データ圧縮アルゴリズムのライブラリZstandardとは

Google-Snappyという圧縮ライブラリの存在を知り、他にどんなものがあるか調べてみました。

d.hatena.ne.jp

⇧  上記サイト様によると、Google-Snappyは、C++で実装されてるようです。

 

データ圧縮アルゴリズムのライブラリいろいろ

最近(2017年12月3日に調べた段階)のものを上げるとこんな感じでしょうか? 

名前 使用言語 会社 開発元 リリース ライセンス
Zstandard
(Zstd)
C Facebook Yann Collet 2015/1/25 BSDライセンス
Brotli C Google Jyrki Alakuijala
Zoltán Szabadka
2015/9 Apache license
Zopfli C Google 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オーディオの場合「ヒトの聴覚では通常は識別できない」という意味であり、冒頭の「情報量を保ったまま」という定義を破っている。

データファイルのサイズを小さくする処理は一般にデータ圧縮と呼ばれるが、データを記録または転送する前に符号化するという意味では情報源符号化である

データ圧縮 - Wikipedia

どっちやねん...ということみたいです。ちなみに、MP3と音楽の流れとかは『誰が音楽をタダにした?』が面白いです。

www.hayakawa-online.co.jp

 

今回使っていきたいと思っている Zstandard は「可逆圧縮」のアルゴリズムであるということで、可逆圧縮についてもう少し見ていきます。

 

可逆圧縮とは?

Wikipediaさんによると、 

可逆圧縮(かぎゃくあっしゅく)とは、圧縮データを復元した時に、圧縮前の入力データが完全に復元されるような圧縮方法である。基本的には、入力データの統計的冗長性(出現する符号の偏り、規則性)を利用して、情報を失うことなくより稠密なデータに変換する。

データ圧縮 - Wikipedia

となっており、データの中の特定の個所(統計的冗長性)に着目してデータを符号化することのようです。符号化は、

符号化(ふごうか)とは、アナログ信号やデジタルデータに特定の方法で、後に元の(あるいは類似の)信号またはデータに戻せるような変換を加えることである。

一般的には、エンコードするための機器・回路・プログラムをエンコーダ、デコード(記事内後述を参照)するための機器・回路・プログラムをデコーダと呼んでいる。

エンコード - Wikipedia

となっています。

では、「可逆圧縮」の符号化にはどんな種類があるかというと、

連長圧縮 (RLE)

例えば、画像には数ピクセル同じ色が並んだ領域がよくみられる。そこでピクセル単位に色情報を並べて表現する代わりに、「n個の赤のピクセル」という形で符号化できる。このような種類の方法は連長圧縮(RLE)と呼ばれる。

データ圧縮 - Wikipedia

エントロピー符号化(ハフマン符号化、算術符号化など)  

多くの可逆圧縮で使われている方法として、出現頻度(確率)の高いものに短い符号を、出現頻度の低いものに長い符号を割り当てることで、データ全体でみたときの平均符号長を短くする方法がある。これをエントロピー符号化と呼び、具体的な方法としてハフマン符号化や算術符号化などがある。

データ圧縮 - Wikipedia

拡大情報源  

データを区間に区切って、それぞれで対応する符号を変えたり、n 個の連続した符号の列に対して符号を割り当てる方法(拡大情報源)など、冗長性を除去することでデータ量を低減させる様々な方法が存在する。

データ圧縮 - Wikipedia

LZ77(Lempel)、Lempel–Ziv–Storer–Szymanski (LZSS)

LZ77 (Lempel–Ziv) およびそれを改良したLempel–Ziv–Storer–Szymanski (LZSS) という圧縮法は、可逆記録方法としては最もよく使われているアルゴリズムである。

データ圧縮 - Wikipedia

Deflate 

DeflateはLZSSを伸長速度と圧縮率の面で最適化した派生技法だが、圧縮は時間がかかることがある。Deflateは、PKZIP英語版gzipPNGで採用されている。

データ圧縮 - Wikipedia

Lempel–Ziv–Welch (LZW)

Lempel–Ziv–Welch (LZW) はGIFで採用されている。

データ圧縮 - Wikipedia

LZR (Lempel-Ziv–Renau)

LZR (Lempel-Ziv–Renau) アルゴリズムZIPの基盤として採用されている。

データ圧縮 - Wikipedia

LZ 

LZでは、データに繰り返し出現する記号列をテーブルを使って置換する方式を採用している。多くのLZ系の技法では、このテーブルを動的に生成しつつ入力を先頭から順次処理していく。テーブル自体はハフマン符号で符号化されることが多い(例えば、SHRI、LZX)。LZXはDeflateよりも効率が良く、マイクロソフトCAB形式などで使われている。また、ハフマン符号に代わりRange Coderを採用したLZMAやLZMA2はさらに圧縮率が良い。

データ圧縮 - Wikipedia

乱数アルゴリズム(Prediction by Partial Matchingなど) 

圧縮効率が最も高い可逆圧縮法は乱択アルゴリズムを導入したもので Prediction by Partial Matching などがある。

データ圧縮 - Wikipedia

文法圧縮(Sequitur、Re-Pair、MPMなど) 

文法圧縮を使った技法は、繰り返しが非常に多い場合に高い圧縮率を達成でき、同一あるいは関連する種の生物学的データ群、頻繁に改版される文書群、インターネットアーカイブなどの用途がある。文法圧縮では、入力文字列から文脈自由文法を構築する。コードが公開されているアルゴリズムとしては、Sequitur、Re-Pair、MPMがある。

データ圧縮 - Wikipedia

 

⇩  圧縮前に行うことで圧縮を効果的に行えるようにしてくれるようです。 

ブロックソートはデータの統計的モデリング技法であり、圧縮の前処理に使われる。

データ圧縮 - Wikipedia

⇩  アルゴリズムを組み合わせることで、圧縮を効果的にできるようです。 

これらの技法をさらに洗練させるため、統計的予測と算術符号と呼ばれるアルゴリズムを組み合わせる。算術符号は Jorma Rissanen が考案し、Witten、Neal、Cleary がそれを実用的な技法に発展させ、ハフマン符号より優れた圧縮率を達成するようになった。統計的予測が文脈に強く依存する場合のデータ圧縮によく採用されている。二値画像圧縮の標準であるJBIG、文書(スキャン画像)圧縮の標準であるDjVuなどで使われている。テキスト入力システム Dasher は、いわば逆算術符号化器である。

データ圧縮 - Wikipedia

 

ん~、あふれんばかりの圧縮技術の熱量ですね。いろいろ出てきましたが、『可逆圧縮』とは何か?ということを要約すると、

圧縮したデータを圧縮前と変わらない状態に戻せる

ってことですかね、たぶん。

 

Zstandardとは?

Wikipediaさんによると、 

Zstandard(Zstd)は2015年からFacebookに所属しているYann Collet によって開発された可逆圧縮アルゴリズムである。 またCで書かれた前述のアルゴリズムのリファレンス実装の名前でもある。 この実装のバージョン1は2016年8月にフリーソフトウェアとして公開された。

Zstandardは辞書式圧縮アルゴリズム(LZ77)とFinal Stateエントロピー (tANS)ステージのエントロピー符号化を併用している。

Zstandard - Wikipedia

ということみたいです。 

JNI(Java Native Interface)とは?

まだ、出てきてない言葉ですが、

Java Native Interface (JNI) は、Javaプラットフォームにおいて、Javaで記述されたプログラムと、他の言語(たとえばCC++など)で書かれた、実際のCPUの上で動作するコード(ネイティブコード)とを連携するためのインタフェース仕様である。

Java言語からネイティブコードを利用するためのABIと、逆にネイティブコードからJavaバイトコードを動作させるためのバーチャルマシンを利用するためのAPIの2つから成る。

JNIを使うことで、Java言語のバーチャルマシンで動作させるには処理速度の面で不利とされる計算量の多いプログラムを部分的にネイティブコードに置き換えて高速化したり、標準クラスライブラリからはアクセスできないオペレーティングシステムの機能を利用するプログラムを、あたかも通常のJavaクラスのように呼び出したりできるようになる。Java言語以外のJava VM上で動作する言語からも利用可能である。

Java Native Interface - Wikipedia

ということらしく、今回使いたいZstandard がC言語で記述されているので、それをJavaで使えるようにしてくれるみたいです。

逆に、他の言語でJavaを使うこともできるみたいですね。

 

JNA (Java Native Access) とは?

JNIがあれば、JNAもあるらしい。

marpapa.blogspot.jp

⇧   JNIの実装は結構に難しいみたいですね...。

Java Native Access (JNA) とは、JavaプログラムがJava Native Interfaceを用いずにネイティブの共有ライブラリにアクセスする方法を提供するライブラリである。

JNA は最小限の作業でネイティブコードにアクセスできることを目指して設計されており、決まりきったアクセスコードを書いたりグルーコードの生成を行ったりせず、ネイティブコードへ正しく簡単にアクセスすることを最優先としている(ただし、性能にも注意が払われている)。

JNAライブラリはネイティブコードを呼び出すためにlibffiを用いており、名前を指定してライブラリをロードするネイティブの関数を用いて、目的のライブラリ関数の関数ポインタを取得する。

ネイティブコードにアクセスする過程で静的なバインディング、ヘッダファイル、またコンパイルは必要ない。アプリケーションの開発者はJavaインターフェイスを用いて対象のネイティブライブラリの関数や構造体を記述する。

これによって、JNIコードを記述しビルドする大きな労力をかけずにきわめて簡単にネイティブプラットフォームの機能を利用することができる。

Java Native Access - Wikipedia

残念ながら、Zstandardは、2017年12月3日(日)現在、jniしか用意されてないっぽいですね(涙)。 

Zstandard(Java用のライブラリ)をダウンロード

Zstandard - Real-time data compression algorithm にアクセスします。

f:id:ts0818:20171202171426j:plain

下の方にスクロールすると、言語別にライブラリの導入の仕方が掲載されているので、今回はJava のURLをクリックします。

f:id:ts0818:20171202171832j:plain

 ページ遷移したら、下の方にスクロールし、

f:id:ts0818:20171202172631j:plain

pom.xmlを使わない場合(動的Webプロジェクトなど)は、

https://repo1.maven.org/maven2/com/github/luben/zstd-jni/ にアクセスします。

f:id:ts0818:20171202172848j:plain

バージョンごとのライブラリを選択してダウンロードできます。今回は、「1.3.2-6/」を選択しました。

f:id:ts0818:20171202173302j:plain

「zstd-jni-1.3.2-6.jar」 のリンクをクリック。

f:id:ts0818:20171202173551p:plain

毎回思うんですが、jarファイルをダウンロードするときの警告、止めて欲しいですね。「保存」を選択。

f:id:ts0818:20171202174019j:plain

ダウンロードされました。jniという言葉が含まれているので、このjarは、「JNI(Java Native Interface)」ということになるようですね。

f:id:ts0818:20171202174139j:plain

 

動的Webプロジェクトの作成

Eclipseを起動し、「パースペクティブ」が「Java EE」になっている状態で、「ファイル」>「新規(N)」>「動的 Web プロジェクト」を選択。

f:id:ts0818:20171202180725j:plain

「プロジェクト名(M):」を入力し、「ターゲット・ランタイム(U)」でTomcatのバージョンを選択し、「ワーキング・セット」にプロジェクトを追加する場合は、「新規(W)...」か「選択(E)...」で。(Eclipse NeonをインストールしたときにTomcatも含める設定にしていた場合、Tomcat 8までは使えるようになっていると思われます。自分はTomcat 9を別途インストールしています。)

「次へ(N)>」をクリック。

f:id:ts0818:20171202180905j:plain

「次へ(N)>」をクリック。

f:id:ts0818:20171202182238j:plain

「完了(F)」をクリック。

f:id:ts0818:20171202182304j:plain

プロジェクトができました。

f:id:ts0818:20171202182344j:plain

 

libにzstd-jni-1.3.2-6.jarを配置

「WEB-INF」>「lib」にダウンロードした jarファイルを配置します。

ダウンロードした jarファイルを「コピー(C)」し、

f:id:ts0818:20171202183329j:plain

「WEB-INF」>「lib」を右クリックした状態で、「貼り付け(P)」を選択。

f:id:ts0818:20171202183442j:plain

「zstd-jni-1.3.2-6.jar」が配置されました。

f:id:ts0818:20171202183552j:plain

 

Servletクラスを作成

まずは、Servletを作成。

Javaリソース」>「src」を選択した状態で右クリックし、「新規(N)」>「サーブレット」を選択。

f:id:ts0818:20171202200951j:plain

Java パッケージ(K):」、「クラス名」を適当に入力し、「次へ(N)>」をクリック。

f:id:ts0818:20171202201142j:plain

「URL マッピング(U):」を変更してます。(「URL マッピング(U):」のテキストエリアをダブルクリックすると変更ダイアログが出て編集できます。)

「次へ(N)>」をクリック。

f:id:ts0818:20171202201257j:plain

「完了(F)」をクリック。

f:id:ts0818:20171202201448j:plain

サーブレットが用意できました。

f:id:ts0818:20171202201845j:plain

「WEB-INF」>「file」>「sample.txt」を作成して適当な文字をコピペして保存しておきます。自分は、10000000文字保存しました。サイズ的には「60,000,000 バイト」となってました。

f:id:ts0818:20171203224300j:plain

 

ファイルを編集

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かしら?

github.com

⇧  JNIの実装部分については、ライブラリでやってくれているみたいですね。『zstd-jni/src/test/scala/Zstd.scala』に使い方が載ってるっぽいですね。

Scalaも勉強せねばですね...。

Scala(スカラ(SKAH-lah)はオブジェクト指向言語関数型言語の特徴を統合したマルチパラダイムプログラミング言語である。名前の「Scala」は英語の「scalable language」に由来するものである。

ScalaJavaプラットフォームJava仮想マシン)上で動作し、既存のJavaのプログラムと容易に連携させることができる。また、過去には下記のプラットフォームもサポートしていたが、現在は開発が中断している。

 

サーバー起動、ブラウザで確認

サーバーで実行します。プロジェクトを選択した状態で右クリックし、「実行(R)」>「1 サーバーで実行」を選択。

f:id:ts0818:20171203225652j:plain

「サーバー」が選択されていることを確認し、「次へ(N)>」。

f:id:ts0818:20171203225759j:plain

「構成済み(C):」にプロジェクトが追加されていることを確認し、「完了(F)」。

f:id:ts0818:20171203225900j:plain

ブラウザで「http://localhost:8080/プロジェクト名/@WebServletの値」 でアクセスします。(自分の場合ですと、『http://localhost:8080/ZsTest/zstandardTest』ととなります。)

f:id:ts0818:20171203230301j:plain

見事に圧縮されてますね。時間を計測してないですが、他の方の情報だと、かなり速いみたいです。

hidekatsu-izuno.hatenablog.com

 

フロントエンド覚えること多すぎる問題という記事を前に見かけたことがありますが、サーバーサイドも勉強すること多いですね(涙)。

今回はこのへんで。