1. 概要

このクイックチュートリアルでは、Javaを使用して2つの文字列の違いを見つける方法を示します。

このチュートリアルでは、 2つの既存のJavaライブラリを使用して、この問題に対するアプローチを比較します。

2. 問題

次の要件を考えてみましょう。文字列ABCDELMN」と「ABCFGLMN」の違いを見つけたいと思います。

出力に必要な形式に応じて、カスタムコードを作成する可能性を無視すると、2つの主要なオプションが利用可能であることがわかりました。

1つ目は、 diff-match-patchと呼ばれるGoogleによって作成されたライブラリです。彼らが主張するように、ライブラリはプレーンテキストを同期するための堅牢なアルゴリズムを提供します。

もう1つのオプションは、ApacheCommonsLangのStringUtilsクラスです。

これら2つの違いを調べてみましょう。

3. diff-match-patch

この記事では、元のGoogleライブラリのフォークを使用します。これは、元のライブラリのアーティファクトがMavenCentralでリリースされていないためです。 また、一部のクラス名は元のコードベースとは異なり、Java標準に準拠しています。

まず、その依存関係をpom.xmlファイルに含める必要があります。

<dependency>
    <groupId>org.bitbucket.cowwoc</groupId>
    <artifactId>diff-match-patch</artifactId>
    <version>1.2</version>
</dependency>

次に、このコードについて考えてみましょう。

String text1 = "ABCDELMN";
String text2 = "ABCFGLMN";
DiffMatchPatch dmp = new DiffMatchPatch();
LinkedList<Diff> diff = dmp.diffMain(text1, text2, false);

text1text2の違いを生成する上記のコードを実行すると、変数diffを出力すると次の出力が生成されます。

[Diff(EQUAL,"ABC"), Diff(DELETE,"DE"), Diff(INSERT,"FG"), Diff(EQUAL,"LMN")]

実際、出力は差分オブジェクトのリストになり、各オブジェクトは操作タイプ( INSERT DELETE 、または EQUAL )、および操作に関連するテキストの部分

text2text1、の間で差分を実行すると、次の結果が得られます。

[Diff(EQUAL,"ABC"), Diff(DELETE,"FG"), Diff(INSERT,"DE"), Diff(EQUAL,"LMN")]

4. StringUtils

Apache Commons のクラスには、より単純なアプローチがあります。

まず、 ApacheCommonsLang依存関係pom.xmlファイルに追加します。

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-lang3</artifactId>
    <version>3.12.0</version>
</dependency>

次に、Apache Commonsを使用した2つのテキストの違いを見つけるために、 StringUtils#Differenceを呼び出します。

StringUtils.difference(text1, text2)

生成される出力は、単純な文字列になります。

FGLMN

text2text1の間で差分を実行すると、次の結果が返されます。

DELMN

この単純なアプローチは、 StringUtils.indexOfDifference()を使用して拡張できます。これにより、は2つの文字列が異なり始めるインデックスを返します (この場合、文字列の4番目の文字)。 このインデックスを使用して、元の文字列のサブ文字列を取得し、 2つの入力に共通するものと、異なるものを示すことができます。

5. パフォーマンス

ベンチマークでは、 10文字の固定部分、続いて20個のランダムなアルファベット文字を含む10,000個の文字列のリストを生成します。

次に、リストをループして、リストのnth要素とn+1th要素の間で差分を実行します。

@Benchmark
public int diffMatchPatch() {
    for (int i = 0; i < inputs.size() - 1; i++) {
        diffMatchPatch.diffMain(inputs.get(i), inputs.get(i + 1), false);
    }
    return inputs.size();
}
@Benchmark
public int stringUtils() {
    for (int i = 0; i < inputs.size() - 1; i++) {
        StringUtils.difference(inputs.get(i), inputs.get(i + 1));
    }
    return inputs.size();
}

最後に、ベンチマークを実行して、2つのライブラリを比較してみましょう。

Benchmark                                   Mode  Cnt    Score   Error  Units
StringDiffBenchmarkUnitTest.diffMatchPatch  avgt   50  130.559 ± 1.501  ms/op
StringDiffBenchmarkUnitTest.stringUtils     avgt   50    0.211 ± 0.003  ms/op

6. 結論

純粋な実行速度に関しては、 StringUtilsの方が明らかにパフォーマンスが高くなります。ただし、2つの文字列が異なり始める部分文字列のみが返されます。

同時に、 Diff-Match-Patch は、パフォーマンスを犠牲にして、より徹底的な比較結果を提供します。

これらの例とスニペットの実装は、GitHubから入手できます。