java string similarity
v2.0.0
Библиотека, реализующая различные меры сходства и расстояния строк. В настоящее время реализовано дюжина алгоритмов (включая расстояние редактирования Левенштейна и братьев и сестер, Яро-Винклера, самую длинную общую подпоследовательность, косинусное сходство и т. д.). Полный список смотрите в сводной таблице ниже...
Использование Мавена:
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-string-similarity</artifactId>
<version>RELEASE</version>
</dependency>
Или посмотрите выпуски.
Для этой библиотеки требуется Java 8 или более поздняя версия.
Основные характеристики каждого реализованного алгоритма представлены ниже. Столбец «стоимость» дает оценку вычислительных затрат на вычисление сходства между двумя строками длины m и n соответственно.
| Нормализовано? | Метрика? | Тип | Расходы | Типичное использование | ||
|---|---|---|---|---|---|---|
| Левенштейн | расстояние | Нет | Да | О(м*п) 1 | ||
| Нормализованный Левенштейн | расстояние сходство | Да | Нет | О(м*п) 1 | ||
| Взвешенный Левенштейн | расстояние | Нет | Нет | О(м*п) 1 | оптическое распознавание символов | |
| Дамерау-Левенштейна 3 | расстояние | Нет | Да | О(м*п) 1 | ||
| Оптимальное выравнивание струн 3 | расстояние | Нет | Нет | О(м*п) 1 | ||
| Яро-Винклер | сходство расстояние | Да | Нет | О(м*п) | исправление опечатки | |
| Самая длинная общая подпоследовательность | расстояние | Нет | Нет | О(м*п) 1,2 | утилита diff, сверка GIT | |
| Метрическая самая длинная общая подпоследовательность | расстояние | Да | Да | О(м*п) 1,2 | ||
| N-грамм | расстояние | Да | Нет | О(м*п) | ||
| Q-грамма | расстояние | Нет | Нет | Профиль | О(м+п) | |
| Косинусное подобие | сходство расстояние | Да | Нет | Профиль | О(м+п) | |
| Индекс Жаккара | сходство расстояние | Да | Да | Набор | О(м+п) | |
| Коэффициент Соренсена-Дайса | сходство расстояние | Да | Нет | Набор | О(м+п) | |
| Рэтклифф-Оберсхелп | сходство расстояние | Да | Нет | ? |
[1] В этой библиотеке расстояние редактирования Левенштейна, расстояние LCS и их родственные элементы вычисляются с использованием метода динамического программирования , стоимость которого составляет O(mn). Для расстояния Левенштейна алгоритм иногда называют алгоритмом Вагнера-Фишера («Проблема построчной коррекции», 1974). Исходный алгоритм использует матрицу размера mxn для хранения расстояния Левенштейна между префиксами строк.
Если алфавит конечен, то для ускорения вычислений можно использовать метод четырех русских (Арлазаров и др. «Об экономическом построении транзитивного замыкания ориентированного графа», 1970). Это было опубликовано Масеком в 1980 году («Быстрый алгоритм вычисления расстояний редактирования строк»). Этот метод разбивает матрицу на блоки размером tx t. Каждый возможный блок предварительно вычисляется для создания таблицы поиска. Эту таблицу поиска затем можно использовать для вычисления сходства строк (или расстояния) в O(нм/t). Обычно t выбирается как log(m), если m > n. Таким образом, итоговая стоимость вычислений составит O(mn/log(m)). Этот метод не реализован (пока).
[2] В книге «Длина максимальных общих подпоследовательностей» К.С. Ларсен предложил алгоритм, который вычисляет длину LCS за время O(log(m).log(n)). Но алгоритм требует памяти O(m.n²) и поэтому здесь не реализован.
[3] Существует два варианта расстояния Дамерау-Левенштейна: Дамерау-Левенштейна с соседними транспозициями (также иногда называемое неограниченным расстоянием Дамерау-Левенштейна) и оптимальное выравнивание строк (также иногда называемое ограниченным расстоянием редактирования). Для оптимального выравнивания строк ни одну подстроку нельзя редактировать более одного раза.
Хотя тема может показаться простой, существует множество различных алгоритмов для измерения сходства или расстояния текста. Поэтому библиотека определяет некоторые интерфейсы для их классификации.
Как правило, алгоритмы, реализующие NormalizedStringSimilarity, также реализуют NormalizedStringDistance, а сходство = 1 — расстояние. Но есть несколько исключений, таких как сходство и расстояние N-грамм (Кондрак)...
Интерфейс MetricStringDistance: некоторые расстояния на самом деле являются метрическими расстояниями, что означает, что необходимо проверить неравенство треугольника d(x, y) <= d(x,z) + d(z,y). Например, Левенштейн — это метрическое расстояние, а Нормализованный Левенштейн — нет.
Многие алгоритмы поиска ближайших соседей и структуры индексации полагаются на неравенство треугольника. Вы можете проверить «Поиск по сходству, подход метрического пространства» Зезулы и др. для опроса. Их нельзя использовать с неметрическими мерами сходства.
Прочтите Javadoc для подробного описания.
Некоторые алгоритмы работают путем преобразования строк в наборы n-грамм (последовательности из n символов, также иногда называемые k-шинглами). Сходство или расстояние между строками является тогда сходством или расстоянием между наборами.
Некоторые из них, например жаккард, рассматривают струны как наборы черепиц и не учитывают количество вхождений каждой черепицы. Другие, такие как косинусное сходство, работают с использованием так называемого профиля струн, который учитывает количество вхождений каждой черепицы.
Для этих алгоритмов возможен другой вариант использования при работе с большими наборами данных:
Расстояние Левенштейна между двумя словами — это минимальное количество односимвольных правок (вставок, удалений или замен), необходимых для превращения одного слова в другое.
Это расстояние в метрической строке. В этой реализации используется динамическое программирование (алгоритм Вагнера-Фишера) всего с двумя строками данных. Таким образом, требуемое пространство составляет O(m), а алгоритм работает за O(mn).
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
Levenshtein l = new Levenshtein ();
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
}
}Это расстояние рассчитывается как расстояние Левенштейна, разделенное на длину самой длинной строки. Результирующее значение всегда находится в интервале [0,0 1,0], но оно больше не является метрикой!
Сходство вычисляется как 1 – нормализованное расстояние.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
NormalizedLevenshtein l = new NormalizedLevenshtein ();
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
}
}Реализация Левенштейна, позволяющая определять разные веса для разных замен символов.
Этот алгоритм обычно используется для приложений оптического распознавания символов (OCR). Для OCR стоимость замены P и R ниже, чем стоимость замены P и M, например, потому что с точки зрения OCR P аналогичен R.
Его также можно использовать для автокоррекции набора текста с клавиатуры. Здесь стоимость замены E и R ниже, например, потому, что они расположены рядом друг с другом на клавиатуре AZERTY или QWERTY. Следовательно, вероятность того, что пользователь ошибся в вводе символов, выше.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
WeightedLevenshtein wl = new WeightedLevenshtein (
new CharacterSubstitutionInterface () {
public double cost ( char c1 , char c2 ) {
// The cost for substituting 't' and 'r' is considered
// smaller as these 2 are located next to each other
// on a keyboard
if ( c1 == 't' && c2 == 'r' ) {
return 0.5 ;
}
// For most cases, the cost of substituting 2 characters
// is 1.0
return 1.0 ;
}
});
System . out . println ( wl . distance ( "String1" , "Srring2" ));
}
}Подобно Левенштейну, расстояние Дамерау-Левенштейна с транспозицией (также иногда называемое неограниченным расстоянием Дамерау-Левенштейна) — это минимальное количество операций, необходимых для преобразования одной строки в другую, где операция определяется как вставка, удаление или замена строки. один символ или транспозиция двух соседних символов .
Оно учитывает неравенство треугольника и, таким образом, является метрическим расстоянием.
Это не следует путать с оптимальным расстоянием выравнивания строки, которое представляет собой расширение, при котором ни одну подстроку нельзя редактировать более одного раза.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
Damerau d = new Damerau ();
// 1 substitution
System . out . println ( d . distance ( "ABCDEF" , "ABDCEF" ));
// 2 substitutions
System . out . println ( d . distance ( "ABCDEF" , "BACDFE" ));
// 1 deletion
System . out . println ( d . distance ( "ABCDEF" , "ABCDE" ));
System . out . println ( d . distance ( "ABCDEF" , "BCDEF" ));
System . out . println ( d . distance ( "ABCDEF" , "ABCGDEF" ));
// All different
System . out . println ( d . distance ( "ABCDEF" , "POIU" ));
}
}Будет производить:
1.0
2.0
1.0
1.0
1.0
6.0
Вариант Дамерау-Левенштейна для оптимального выравнивания строк (иногда называемый ограниченным расстоянием редактирования) вычисляет количество операций редактирования, необходимых для выравнивания строк при условии, что ни одна подстрока не редактируется более одного раза , тогда как истинный вариант Дамерау-Левенштейна не представляет такого ограничение. Отличием от алгоритма для расстояния Левенштейна является добавление одной рекуррентности для операций транспонирования.
Обратите внимание, что для оптимального расстояния выравнивания струны неравенство треугольника не выполняется и поэтому не является истинной метрикой.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
OptimalStringAlignment osa = new OptimalStringAlignment ();
System . out . println ( osa . distance ( "CA" , "ABC" ));;
}
}Будет производить:
3.0
Яро-Винклер — это расстояние редактирования строки, которое было разработано в области связывания записей (обнаружения дубликатов) (Winkler, 1990). Метрика расстояния Джаро-Винклера разработана и лучше всего подходит для коротких строк, таких как имена людей, а также для обнаружения опечаток транспозиции.
Джаро-Винклер вычисляет сходство между двумя строками, и возвращаемое значение лежит в интервале [0,0, 1,0]. Это (примерно) вариант Дамерау-Левенштейна, где перестановка двух близких символов считается менее важной, чем перестановка двух символов, находящихся далеко друг от друга. Яро-Винклер наказывает дополнения или замены, которые не могут быть выражены как транспозиции.
Расстояние рассчитывается как 1 – сходство Яро-Винклера.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
JaroWinkler jw = new JaroWinkler ();
// substitution of s and t
System . out . println ( jw . similarity ( "My string" , "My tsring" ));
// substitution of s and n
System . out . println ( jw . similarity ( "My string" , "My ntrisg" ));
}
}будет производить:
0.9740740656852722
0.8962963223457336
Задача о самой длинной общей подпоследовательности (LCS) состоит в нахождении самой длинной подпоследовательности, общей для двух (или более) последовательностей. Она отличается от задач поиска общих подстрок тем, что в отличие от подстрок подпоследовательности не обязаны занимать последовательные позиции внутри исходных последовательностей.
Он используется утилитой diff, Git для согласования нескольких изменений и т. д.
Расстояние LCS между строками X (длиной n) и Y (длиной m) равно n + m - 2 |LCS(X, Y)| мин = 0 макс = n + m
Расстояние LCS эквивалентно расстоянию Левенштейна, когда разрешены только вставки и удаления (без замены) или когда стоимость замены в два раза превышает стоимость вставки или удаления.
Этот класс реализует подход динамического программирования, для которого требуется пространство O(mn) и стоимость вычислений O(mn).
В книге «Длина максимальных общих подпоследовательностей» К.С. Ларсен предложил алгоритм, который вычисляет длину LCS за время O(log(m).log(n)). Но алгоритм требует памяти O(m.n²) и поэтому здесь не реализован.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
LongestCommonSubsequence lcs = new LongestCommonSubsequence ();
// Will produce 4.0
System . out . println ( lcs . distance ( "AGCAT" , "GAC" ));
// Will produce 1.0
System . out . println ( lcs . distance ( "AGCAT" , "AGCT" ));
}
}Метрика расстояния, основанная на самой длинной общей подпоследовательности, из заметок Дэниела Баккелунда «Строковая метрика на основе LCS». http://heim.ifi.uio.no/~danielry/StringMetric.pdf
Расстояние вычисляется как 1 - |LCS(s1, s2)| / макс(|s1|, |s2|)
public class MyApp {
public static void main ( String [] args ) {
info . debatty . java . stringsimilarity . MetricLCS lcs =
new info . debatty . java . stringsimilarity . MetricLCS ();
String s1 = "ABCDEFG" ;
String s2 = "ABCDEFHJKL" ;
// LCS: ABCDEF => length = 6
// longest = s2 => length = 10
// => 1 - 6/10 = 0.4
System . out . println ( lcs . distance ( s1 , s2 ));
// LCS: ABDF => length = 4
// longest = ABDEF => length = 5
// => 1 - 4 / 5 = 0.2
System . out . println ( lcs . distance ( "ABDEF" , "ABDIF" ));
}
}Нормализованное расстояние N-грамм, определенное Кондраком, «Сходство и расстояние N-грамм», Обработка строк и поиск информации, Конспект лекций по информатике, том 3772, 2005, стр. 115–126.
http://webdocs.cs.ualberta.ca/~kondrak/papers/spire05.pdf
Алгоритм использует добавление специального символа 'n' для увеличения веса первых символов. Нормализация достигается путем деления общего показателя сходства на исходную длину самого длинного слова.
В статье Кондрак также определяет меру сходства, которая (пока) не реализована.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
// produces 0.583333
NGram twogram = new NGram ( 2 );
System . out . println ( twogram . distance ( "ABCD" , "ABTUIO" ));
// produces 0.97222
String s1 = "Adobe CreativeSuite 5 Master Collection from cheap 4zp" ;
String s2 = "Adobe CreativeSuite 5 Master Collection from cheap d1x" ;
NGram ngram = new NGram ( 4 );
System . out . println ( ngram . distance ( s1 , s2 ));
}
}Некоторые алгоритмы работают путем преобразования строк в наборы n-грамм (последовательности из n символов, также иногда называемые k-шинглами). Сходство или расстояние между строками является тогда сходством или расстоянием между наборами.
Затраты на вычисление этих сходств и расстояний в основном связаны с k-шинглингом (преобразованием строк в последовательности из k символов). Поэтому обычно существует два варианта использования этих алгоритмов:
Непосредственно вычислите расстояние между строками:
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
QGram dig = new QGram ( 2 );
// AB BC CD CE
// 1 1 1 0
// 1 1 0 1
// Total: 2
System . out . println ( dig . distance ( "ABCD" , "ABCE" ));
}
}Или, для больших наборов данных, предварительно вычислите профиль всех строк. Затем можно вычислить сходство между профилями:
import info . debatty . java . stringsimilarity . KShingling ;
import info . debatty . java . stringsimilarity . StringProfile ;
/**
* Example of computing cosine similarity with pre-computed profiles.
*/
public class PrecomputedCosine {
public static void main ( String [] args ) throws Exception {
String s1 = "My first string" ;
String s2 = "My other string..." ;
// Let's work with sequences of 2 characters...
Cosine cosine = new Cosine ( 2 );
// Pre-compute the profile of strings
Map < String , Integer > profile1 = cosine . getProfile ( s1 );
Map < String , Integer > profile2 = cosine . getProfile ( s2 );
// Prints 0.516185
System . out . println ( cosine . similarity ( profile1 , profile2 ));
}
}Обратите внимание, это работает только в том случае, если для анализа всех входных строк используется один и тот же объект KShingling!
Расстояние Q-граммы, определенное Укконеном в «Приблизительном сопоставлении строк с q-граммами и максимальными совпадениями» http://www.sciencedirect.com/science/article/pii/0304397592901434
Расстояние между двумя строками определяется как норма L1 разницы их профилей (количества вхождений каждой n-граммы): SUM( |V1_i - V2_i| ). Расстояние Q-граммы является нижней границей расстояния Левенштейна, но может быть вычислено за O(m + n), где Левенштейн требует O(mn)
Сходство между двумя строками представляет собой косинус угла между представлением этих двух векторов и вычисляется как V1 . V2 / (|V1| * |V2|)
Расстояние вычисляется как 1 - косинусное сходство.
Подобно расстоянию Q-грамм, входные строки сначала преобразуются в наборы n-грамм (последовательности из n символов, также называемые k-шинглами), но на этот раз мощность каждой n-граммы не учитывается. Каждая входная строка представляет собой просто набор n-грамм. Затем индекс Жаккара вычисляется как |V1 inter V2| / |V1 объединение V2|.
Расстояние рассчитывается как 1 – сходство. Индекс Жаккара – это метрическое расстояние.
Аналогично индексу Жаккара, но на этот раз сходство вычисляется как 2 * |V1 inter V2| / (|V1| + |V2|).
Расстояние рассчитывается как 1 – сходство.
Распознавание образов Рэтклиффа/Оберсхелпа, также известное как сопоставление гештальт-образцов, представляет собой алгоритм сопоставления строк для определения сходства двух строк. Он был разработан в 1983 году Джоном Рэтклиффом и Джоном А. Обершелпом и опубликован в журнале Dr. Dobb's Journal в июле 1988 года.
Ratcliff/Obershelp вычисляет сходство между двумя строками, и возвращаемое значение лежит в интервале [0,0, 1,0].
Расстояние рассчитывается как 1 – сходство Рэтклиффа/Оберсхелпа.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
RatcliffObershelp ro = new RatcliffObershelp ();
// substitution of s and t
System . out . println ( ro . similarity ( "My string" , "My tsring" ));
// substitution of s and n
System . out . println ( ro . similarity ( "My string" , "My ntrisg" ));
}
}будет производить:
0.8888888888888888
0.7777777777777778
SIFT4 — это алгоритм определения расстояния между строками общего назначения, вдохновленный JaroWinkler и Longest Common Subsequence. Он был разработан для измерения расстояния, максимально приближенного к человеческому восприятию расстояния между струнами. Следовательно, он учитывает такие элементы, как замена символов, расстояние между символами, самая длинная общая подпоследовательность и т. д. Он был разработан с использованием экспериментального тестирования и без теоретической подготовки.
import info.debatty.java.stringsimilarity.experimental.Sift4;
public class MyApp {
public static void main(String[] args) {
String s1 = "This is the first string";
String s2 = "And this is another string";
Sift4 sift4 = new Sift4();
sift4.setMaxOffset(5);
double expResult = 11.0;
double result = sift4.distance(s1, s2);
assertEquals(expResult, result, 0.0);
}
}
Используйте сходство Java-строок в своем проекте и хотите, чтобы об этом упомянули здесь? Не стесняйтесь, напишите мне!
