diff(差分検出アルゴリズム)のJavaライブラリが無いか探したので、参考URLの調査メモ。

study-java-diff-implements.md

diff(差分検出アルゴリズム)のJava実装調査メモ

diff(差分検出アルゴリズム)のJavaライブラリが無いか探したので、参考URLの調査メモ。

※URLなどは2018-01-04時点のもの。

アルゴリズムの種類

diffツールでのアルゴリズムについては、ざっくりと以下のWiki参照：

• https://ja.wikipedia.org/wiki/Diff
• https://en.wikipedia.org/wiki/Diff_utility

Myerのアルゴリズム系

正確には複数の論文で改良が加えられていったアルゴリズムだが、Java実装のドキュメントでよく "Myer's diff" と参照されているので「Myerのアルゴリズム系」と総括した。

参考記事：

• diffの動作原理を知る～どのようにして差分を導き出すのか
  • http://gihyo.jp/dev/column/01/prog/2011/diff_sd200906
• 差分検出アルゴリズム三種盛り - Object.create(null)
  • http://susisu.hatenablog.com/entry/2017/10/09/134032
• Diff algorithm - 枕を欹てて聴く
  • http://constellation.hatenablog.com/entry/20091021/1256112978
• Diff Algorithm - Stack Overflow
  • https://stackoverflow.com/questions/805626/diff-algorithm
• An O(ND) Difference Algorithm for C#
  • http://www.mathertel.de/Diff/
• Diff Algorithm
  • http://wiki.c2.com/?DiffAlgorithm
• Java Notes
  • http://bmsi.com/java/#diff

patience, histogramアルゴリズム

git-diff で実装され、JGitでも使われている。ソースコードの差分比較で、より人間が見やすい形で差分をまとめてくれる。 ちなみに "patience" とは「根気」。

• algorithm - What's the difference between git diff --patience and git diff --histogram? - Stack Overflow
  • https://stackoverflow.com/questions/32365271/whats-the-difference-between-git-diff-patience-and-git-diff-histogram
• vimdiffでより賢いアルゴリズム (patience, histogram) を使う - Qiita
  • https://qiita.com/takaakikasai/items/3d4f8a4867364a46dfa3

Java実装

java-diff-utils

軽くぐぐったところ、Google Codeのオリジナル版からGitHubにforkしたものや、独自実装でたまたまリポジトリ名が同じになったものなど複数あった。

Google Code のオリジナル版：

• https://code.google.com/archive/p/java-diff-utils/
  • 2011-06-08の1.2.1が最終リリースで終わっている。
  • ライセンスは APL 2.0
  • diffアルゴリズムはMyerのdiffアルゴリズムに対応
  • http://search.maven.org/#search%7Cgav%7C1%7Cg%3A%22com.googlecode.java-diff-utils%22%20AND%20a%3A%22diffutils%22

GitHubでのfork：

• https://github.com/dnaumenko/java-diff-utils
  • authorの名前的に、これがオリジナル版作者による公式forkと思われる。
  • こちらで 2013-05-05に 1.3.0 がリリースされているが、それ以降はリリースの動きがなく、開発も止まっている。
  • Issueも、差分計算の根本に関わりそうなIssueが未解決のまま放置されている。
• https://github.com/KengoTODA/java-diff-utils
  • こちらで 2014年に 1.4.0, 1.4.1, 1.5.0 とリリースされている。
  • http://search.maven.org/#search%7Cgav%7C1%7Cg%3A%22jp.skypencil.java-diff-utils%22%20AND%20a%3A%22diffutils%22
• https://github.com/is/java-diff-utils : 特に動きなし。
• https://github.com/johanvanl/java-diff-utils : 特に動きなし。
• https://github.com/lanwen/java-diff-utils : 特に動きなし。
• https://github.com/wumpz/java-diff-utils
  • こちらが 2017年に 2.2 と大幅なアップデートリリースをしている。
  • http://search.maven.org/#artifactdetails%7Ccom.github.wumpz%7Cdiffutils%7C2.2%7Cjar
  • アルゴリズムもJGitよりHistogramDiffを追加しているので、恐らく2017年末時点で "java-diff-utils" 系列で最新と思われる。

ライセンスについてはいずれもAPL 2.0が維持されている。

google-diff-match-patch

Googleが実装した複数言語向けのdiff/patchライブラリ。

Google Code のオリジナル版：

• https://code.google.com/archive/p/google-diff-match-patch/
  • 2012-11-19のリリースが最終版。
  • ライセンスは APL 2.0
  • diffアルゴリズムはMyerのdiffアルゴリズムに対応
  • Mavenリポジトリには org.webjars からのartifactのみ登録されている。
  • http://search.maven.org/#search%7Cga%7C1%7Ca%3Agoogle-diff-match-patch

GitHubでのfork：

• https://github.com/sksamuel/google-diff-match-patch
  • 2013年ごろにJava実装だけ抜き出されたforkで、コードの中身には手が加えられていないようだ。
  • MavenリポジトリにJava実装が登録されている。
  • http://search.maven.org/#search%7Cgav%7C1%7Cg%3A%22com.sksamuel.diff%22%20AND%20a%3A%22diff%22
  • 開発自体は2013年一杯で終わったのか、それ以降のcommitログが無い。

他にもGitHubでのforkはあるが、他の言語実装が抜き出されてforkされたものも複数あり、全部は見きれなかった。 Java実装で一番スターを集めていたのが上記リポジトリで、今回はそれのみチェックして終わりとした。

日本語参考記事：

• JavaScript/Java/PythonでDiff·google-diff-match-patch MOONGIFT
  • http://www.moongift.jp/2007/06/google_diff_match_patch/

diff4j

Hudson(現Jenkins)のリードエンジニアである川口耕介氏が開発した差分ライブラリ。 実装コードをざっと眺めた所、テキストファイルを行単位で比較していくコードと、外部のdiffコマンドを呼び出すコードがdiff差分処理の中核となっている。 (逆に言えば、diffアルゴリズムの具体的なサポート状況は不明)

• https://github.com/cloudbees/diff4j
• http://diff4j.infradna.org/ のURLが載っているが、現在はCloudBeesのサイトにリダイレクトされてしまう。
• ライセンスは CDDL/GPLv2 のデュアルライセンス。
• ソースコードのcopyrightはSun Microsystemsとなっている。これは川口氏がSunのエンジニアだった名残と思われる。
• 2014-04-14 の 1.2 がMavenリポジトリ上の最新版
  • http://search.maven.org/#search%7Cgav%7C1%7Cg%3A%22com.cloudbees%22%20AND%20a%3A%22diff4j%22
• pom.xmlより、元はNetBeansにあったコードをパッケージングし直したもの。

※元Sunのエンジニアだった川口耕介氏は2010年4月Oracleを退社してInfraDNAを興しており、InfraDNAは2010年11月にCloudBeesに買収されている。

• InfraDNA, Inc.
  • https://github.com/infradna
• Hudson 勉強会 (2p目参照)
  • https://www.slideshare.net/InfraDNA/hudson-5761580

JGit

Eclipseで開発されている、Pure JavaでのGit実装。この中にGitで使うdiff実装が含まれている。 EclipseのGitプラグインであるEGitは、JGitのEclipse向けフロントエンドとなっている。

• http://www.eclipse.org/jgit/
  • ライセンスは Eclipse Distribution License v1.0
    • http://www.eclipse.org/org/documents/edl-v10.php
    • BSD 3-clauseライセンスと同じ。(copyrightがEclipseになってるのと、HOLDER -> OWNERに変更されてるだけ)
    • https://opensource.org/licenses/BSD-3-Clause
  • diffアルゴリズムとしてはMyerとHistogramの2種類が(少なくともコードをざっと眺めた範囲では)サポートされている。
• http://git.eclipse.org/c/jgit/jgit.git/
  • git clone http://git.eclipse.org/gitroot/jgit/jgit.git
  • diff差分処理を含むのは org.eclipse.jgit サブプロジェクト。
  • http://search.maven.org/#search%7Cgav%7C1%7Cg%3A%22org.eclipse.jgit%22%20AND%20a%3A%22org.eclipse.jgit%22

感想

• 複数のJava実装があり、どれを選択するのか悩みそう。
• 個人的には自分でテストコード書くなりして、実際に動かして比べてみるのが良さそう。
• それをする時間も無いなら、 多分 利用者が多くて広く使われているだろうから、JGitを選択するのが良さそう。