Намиране на разликата между два струни в 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 обекти , всеки от които се формира от тип операция ( INSERT , DELETE или EQUAL ) и частта от текста, свързана с операцията .

Когато стартираме разликата между text2 и text1, ще получим този резултат:

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

4. StringUtils

Класът от Apache Commons има по -опростен подход .

Първо ще добавим зависимостта Apache Commons Lang към нашия файл pom.xml :

 org.apache.commons commons-lang3 3.9 

След това, за да намерим разликата между два текста с Apache Commons, бихме нарекли StringUtils # Difference :

StringUtils.difference(text1, text2)

Резултатът ще бъде прост низ :

FGLMN

Докато стартирането на разликата между 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.