1. Обзор
В этом кратком руководстве показано, как найти разницу между двумя строками с помощью Java.
В этом уроке мы будем использовать две существующие библиотеки Java и сравним их подходы к решению этой проблемы.
2. Проблема
Рассмотрим следующее требование: мы хотим найти разницу между строками « ABCDELMN» и «ABCFGLMN».
В зависимости от того, в каком формате нам нужен вывод, и игнорируя возможность написать собственный код для этого, мы нашли два основных доступных варианта.
Первая — это написанная Google библиотека под названием diff-match-patch . Как они утверждают, библиотека предлагает надежные алгоритмы синхронизации простого текста .
Другой вариант — класс StringUtils из Apache Commons Lang.
Давайте рассмотрим различия между этими двумя.
3. diff-match-patch
Для целей этой статьи мы будем использовать форк оригинальной библиотеки Google , так как артефакты для оригинальной не выпускаются на Maven Central. Кроме того, некоторые имена классов отличаются от исходной кодовой базы и больше соответствуют стандартам 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);
Если мы запустим приведенный выше код, который создает разницу между текстом1 и текстом2 , печать переменной diff приведет к следующему результату:
[Diff(EQUAL,"ABC"), Diff(DELETE,"DE"), Diff(INSERT,"FG"), Diff(EQUAL,"LMN")]
На самом деле на выходе будет список объектов Diff , каждый из которых формируется типом операции ( INSERT , DELETE или EQUAL ), и частью текста, связанной с операцией .
При запуске diff между text2 и text1 мы получим такой результат:
[Diff(EQUAL,"ABC"), Diff(DELETE,"FG"), Diff(INSERT,"DE"), Diff(EQUAL,"LMN")]
4. Строковые утилиты
Класс от Apache Commons имеет более упрощенный подход .
Во- первых, мы добавим зависимость Apache Commons Lang в наш файл pom.xml :
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-lang3</artifactId>
<version>3.12.0</version>
</dependency>
Затем, чтобы найти разницу между двумя текстами с помощью Apache Commons, мы вызываем StringUtils#Difference :
StringUtils.difference(text1, text2)
Результатом будет простая строка :
FGLMN
В то время как запуск diff между text2 и text1 вернет:
DELMN
Этот простой подход можно улучшить с помощью StringUtils.indexOfDifference() , который вернет индекс, с которого две строки начинают различаться (в нашем случае это четвертый символ строки). Этот индекс можно использовать для получения подстроки исходной строки , чтобы показать, что общего между двумя входными данными , в дополнение к тому, что отличается.
5. Производительность
Для наших тестов мы генерируем список из 10 000 строк с фиксированной частью из 10 символов , за которыми следуют 20 случайных буквенных символов .
Затем мы перебираем список и выполняем сравнение между n -м элементом и n+1 -м элементом списка:
@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();
}
Наконец, давайте запустим тесты и сравним две библиотеки:
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 явно производительнее , хотя и возвращает только ту подстроку, с которой начинают различаться две строки.
В то же время Diff-Match-Patch обеспечивает более тщательный результат сравнения , за счет производительности.
Реализация этих примеров и фрагментов доступна на GitHub .