Javaで2つの文字列の違いを見つける
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);
text1とtext2の違いを生成する上記のコードを実行すると、変数diffを出力すると次の出力が生成されます。
[Diff(EQUAL,"ABC"), Diff(DELETE,"DE"), Diff(INSERT,"FG"), Diff(EQUAL,"LMN")]
実際、出力は差分オブジェクトのリストになり、各オブジェクトは操作タイプ( INSERT 、 DELETE 、または EQUAL )、および操作に関連するテキストの部分。
text2とtext1、の間で差分を実行すると、次の結果が得られます。
[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
text2とtext1の間で差分を実行すると、次の結果が返されます。
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でから入手できます。