Строковая метрика

В математике и информатике строковая метрика (также известная как метрика сходства строк или функция расстояния строк ) — это метрика , которая измеряет расстояние («обратное сходство») между двумя текстовыми строками для приблизительного сопоставления или сравнения строк, а также при поиске нечетких строк . Требованием к метрике строки (например, в отличие от сопоставления строк ) является выполнение неравенства треугольника . Например, строки «Сэм» и «Самуэль» можно считать близкими. ^{[ 1 ]} Строковая метрика предоставляет число, указывающее расстояние, зависящее от алгоритма.

Наиболее широко известной строковой метрикой является элементарная метрика, называемая расстоянием Левенштейна (также известным как расстояние редактирования). ^{[ 2 ]} Он работает между двумя входными строками, возвращая число, эквивалентное количеству замен и удалений, необходимых для преобразования одной входной строки в другую. Упрощенные строковые метрики, такие как расстояние Левенштейна, расширились и теперь включают фонетические, токенарные , грамматические и символьные методы статистического сравнения.

Строковые метрики широко используются в интеграции информации и в настоящее время используются в таких областях, как обнаружение мошенничества , анализ отпечатков пальцев , обнаружение плагиата , слияние онтологий , анализ ДНК , анализ РНК, анализ изображений на основе фактических данных , машинное обучение , базы данных дедупликация данных , интеллектуальный анализ данных , инкрементальный анализ. поиск , интеграция данных , обнаружение вредоносных программ , ^{[ 3 ]} и семантическая интеграция знаний .

Список строковых метрик

Расстояние Левенштейна , или его обобщенное расстояние редактирования
Расстояние Дамерау – Левенштейна
Коэффициент Серенсена – Дайса
Расстояние блока или расстояние L1 или расстояние городского квартала
Расстояние Хэмминга
Простой коэффициент соответствия (SMC)
Сходство Жаккара или коэффициент Жаккара или коэффициент Танимото
Индекс Тверского
Коэффициент перекрытия
Вариационное расстояние ^{[ 4 ]}
Расстояние Хеллингера или расстояние Бхаттачарьи
Информационный радиус ( расхождение Дженсена – Шеннона )
Косая дивергенция ^{[ 4 ]}
Вероятность путаницы ^{[ 4 ]}
Тау-метрика , аппроксимация расходимости Кульбака – Лейблера.
Метрика Феллеги и Сантерса (SFS) ^{[ 4 ]}
Максимальные совпадения ^{[ 4 ]}
Дистанция, основанная на грамматике ^{[ 5 ]}
TFIDF Метрика расстояния ^{[ 6 ]}

Также существуют функции, которые измеряют различие между строками, но не обязательно удовлетворяют неравенству треугольника и как таковые не являются метриками в математическом смысле. Примером такой функции является расстояние Джаро–Винклера .

Примеры выбранных строковых мер

Имя	Описание	Пример
Расстояние Хэмминга	Только для строк одинаковой длины. Количество измененных символов.	" ка роль в "и" ка вброс " равен 3.
Расстояние Левенштейна и расстояние Дамерау – Левенштейна.	Обобщение расстояния Хэмминга, позволяющее использовать строки разной длины и (с Дамерау) транспозиции.	котенок и сидя на расстоянии 3 . Киттен → s itten (замена «s» на «k») тогда эн → sitt i n (замена «i» на «e») сижу → сидя г (вставка «г» в конце).
Расстояние Яро – Винклера		JaroWinklerDist("МАРТА","МАРХТА") = $d_{j}={\frac {1}{3}}\left({\frac {m}{\|s_{1}\|}}+{\frac {m}{\|s_{2}\|}}+{\frac {m-t}{m}}\right)={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6}}+{\frac {6-{\frac {2}{2}}}{6}}\right)=0.944$ $m$ количество совпадающих символов ; $t$ составляет половину количества транспозиций ( `"MARTHA"[3]!=H, "MARHTA"[3]!=T`).
Наиболее часто встречающиеся символы k		MostFreqKeySimilarity(' r e s e a r ch', 'see king ', 2) = 2

Ссылки

^ Лу, Цзяхэн; и др. (2013). «Измерение сходства строк и объединение с синонимами» . Материалы Международной конференции ACM SIGMOD по управлению данными 2013 г. стр. 373–384. дои : 10.1145/2463676.2465313 . ISBN 9781450320375 . S2CID 2091942 .
^ Наварро, Гонсало (2001). «Экскурсия по приблизительному сопоставлению строк». Обзоры вычислительной техники ACM . 33 (1): 31–88. дои : 10.1145/375360.375365 . hdl : 10533/172862 . S2CID 207551224 .
^ Шломи Долев ; Мохаммад, Ганаим; Александр, Бинун; Сергей, Френкель; Йели, С. Сан (2017). «Связь Жаккара и расстояния редактирования в кластеризации вредоносных программ и онлайн-идентификации». 16-й Международный симпозиум IEEE по сетевым вычислениям и приложениям : 369–373.
^ Перейти обратно: ^а ^б ^с ^д ^и Строковые метрики Сэма — компьютерная лингвистика и фонетика
^ Рассел, Дэвид Дж. и др. «Метрика расстояния на основе грамматики обеспечивает быструю и точную кластеризацию больших наборов последовательностей 16S». Биоинформатика BMC 11.1 (2010): 1-14.
^ Коэн, Уильям; Равикумар, Прадип; Файнберг, Стивен (1 августа 2003 г.). «Сравнение показателей расстояния между строками для задач сопоставления имен» : 73–78. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

Внешние ссылки

Метрики сходства строк для интеграции информации. Достаточно полный обзор. Архивный указатель на Wayback Machine.
Библиотека с открытым исходным кодом Университета Карнеги-Меллона
StringMetric — проект библиотеки Scala строковых метрик и фонетических алгоритмов.
Natural project — библиотека обработки естественного языка JavaScript , которая включает реализации популярных строковых метрик.

[1] Лу, Цзяхэн; и др. (2013). «Измерение сходства строк и объединение с синонимами» . Материалы Международной конференции ACM SIGMOD по управлению данными 2013 г. стр. 373–384. дои : 10.1145/2463676.2465313 . ISBN 9781450320375 . S2CID 2091942 .

[2] Наварро, Гонсало (2001). «Экскурсия по приблизительному сопоставлению строк». Обзоры вычислительной техники ACM . 33 (1): 31–88. дои : 10.1145/375360.375365 . hdl : 10533/172862 . S2CID 207551224 .

[3] Шломи Долев ; Мохаммад, Ганаим; Александр, Бинун; Сергей, Френкель; Йели, С. Сан (2017). «Связь Жаккара и расстояния редактирования в кластеризации вредоносных программ и онлайн-идентификации». 16-й Международный симпозиум IEEE по сетевым вычислениям и приложениям : 369–373.

[sam-4] Перейти обратно: ^а ^б ^с ^д ^и Строковые метрики Сэма — компьютерная лингвистика и фонетика

[5] Рассел, Дэвид Дж. и др. «Метрика расстояния на основе грамматики обеспечивает быструю и точную кластеризацию больших наборов последовательностей 16S». Биоинформатика BMC 11.1 (2010): 1-14.

[6] Коэн, Уильям; Равикумар, Прадип; Файнберг, Стивен (1 августа 2003 г.). «Сравнение показателей расстояния между строками для задач сопоставления имен» : 73–78. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

v т и Струны
Строковая метрика	Примерное соответствие строк Алгоритм битап Расстояние Дамерау – Левенштейна Изменить расстояние Сопоставление гештальт-образцов Расстояние Хэмминга Расстояние Яро – Винклера Расстояние Ли Автомат Левенштейна Расстояние Левенштейна Алгоритм Вагнера-Фишера
Алгоритм поиска строк	Алгоритм Апостола – Джанкарло Алгоритм поиска строк Бойера – Мура Алгоритм Бойера – Мура – Хорспула Алгоритм Кнута – Морриса – Пратта Алгоритм Рабина – Карпа Алгоритм Райта Триграммный поиск Алгоритм двустороннего сопоставления строк Алгоритм сопоставления строк Чжу – Такаока
Поиск нескольких строк	Ахо – Корасик Алгоритм Комментца-Вальтера
Регулярное выражение	Сравнение механизмов регулярных выражений Регулярная грамматика Конструкция Томпсона Недетерминированный конечный автомат
Выравнивание последовательности	ВЗРЫВ Алгоритм Хиршберга Алгоритм Нидлмана – Вунша Алгоритм Смита – Уотермана
Структура данных	ДАФСА Суффиксный массив Суффиксный автомат Суффиксное дерево Обобщенное суффиксное дерево Веревка Тернарное дерево поиска Три
Другой	Разбор Сопоставление с образцом Сопоставление сжатого шаблона Самая длинная общая подпоследовательность Самая длинная общая подстрока Последовательный анализ шаблонов Сортировка Системы перезаписи строк Строковые операции