Нахождение разницы между двумя строками в Java

1. Обзор

Этот краткий учебник покажет, как найти разницу между двумя строками с помощью Java.

В этом уроке мы собираемся использовать две существующие библиотеки Java и сравнить их подходы к этой проблеме.

2. Проблема

Давайте рассмотрим следующее требование: мы хотим найти разницу между строками “ ABCDELMN” и “ABCFGLMN”.

В зависимости от того, в каком формате нам нужен вывод, и игнорируя возможность написания собственного кода для этого, мы нашли два основных доступных варианта.

Первый – это библиотека, написанная Google под названием diff-match-patch . Как они утверждают, библиотека предлагает надежные алгоритмы для синхронизации обычного текста .

Другой вариант-класс StringUtils из Apache Commons Lang.

Давайте рассмотрим различия между этими двумя.

3. diff-match-patch

Для целей этой статьи мы будем использовать вилку оригинальной библиотеки Google , так как артефакты для оригинальной библиотеки не выпускаются на Maven Central. Кроме того, некоторые имена классов отличаются от исходной кодовой базы и более соответствуют стандартам Java.

Во-первых, нам нужно будет включить его зависимость в ваш pom.xml файл:


    org.bitbucket.cowwoc
    diff-match-patch
    1.2

Тогда давайте рассмотрим этот код:

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

Если мы запустим приведенный выше код, который создает разницу между text1 и text2 , то печать переменной diff приведет к получению этого вывода:

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

Фактически, выводом будет список Diff объектов , каждый из которых сформирован типом операции ( ВСТАВКА , УДАЛЕНИЕ или РАВНЫЙ ) и часть текста, связанная с операцией .

При выполнении различия между text2 и text1, мы получим этот результат:

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

4. СтрингУтилы

Класс из Apache Commons имеет более упрощенный подход .

Во-первых, мы добавим зависимость Apache Commons Lang к вашему pom.xml файл:


    org.apache.commons
    commons-lang3
    3.11

Затем, чтобы найти разницу между двумя текстами с помощью Apache Commons, мы вызовем StringUtils#Difference :

StringUtils.difference(text1, text2)

Полученный вывод будет представлять собой простую строку :

FGLMN

В то время как запуск разницы между text2 и text1 вернет:

DELMN

Этот простой подход может быть улучшен с помощью | StringUtils.indexOfDifference() , который вернет | индекс, при котором две строки начинают отличаться (в нашем случае четвертый символ строки). Этот индекс можно использовать для получения подстроки исходной строки , чтобы показать , что общего между двумя входными данными , в дополнение к тому, что отличается.

5. Производительность

Для наших тестов мы генерируем список из 10 000 строк с фиксированной частью из 10 символов , за которой следует 20 случайных буквенных символов .

Затем мы перебираем список и выполняем различие между элементом n ^th и элементом n+1 ^th списка:

@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 .