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

«Расстояние строки» перенаправляется сюда. Информацию о расстоянии между струнами и грифом музыкальных инструментов см. В разделе « Действие (музыка)».

В математике и информатике, струна метрика (также известная как струна подобие метрическая или строке функция расстояния ) является метрикой, что меры расстояние ( «обратное подобие») между двумя текстовыми строками для приблизительного совпадения строк или сравнений и нечеткого поиск строки. Требование для метрики строки (например, в отличие от сопоставления строк ) - выполнение неравенства треугольника. Например, строки «Сэм» и «Самуэль» можно считать близкими. Строковая метрика представляет собой число, указывающее расстояние, зависящее от алгоритма.

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

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

• 1 Список строковых показателей
• 2 Примеры выбранных струнных мер
• 3 ссылки
• 4 Внешние ссылки

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

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

• https://web.archive.org/web/20070304092115/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html#qgram Достаточно полный обзор Индекс архива на Wayback Machine
• Библиотека с открытым исходным кодом Университета Карнеги-Меллона
• StringMetric проекта в Scala библиотеку строковых метрик и фонетических алгоритмов
• Natural project - библиотека обработки естественного языка JavaScript, которая включает в себя реализации популярных строковых показателей.