Строковая метрика - String metric

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

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

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

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

Список строковых показателей

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

ИмяПример
Расстояние Хэмминга"кароллв" и "качтв"равно 3.
Расстояние Левенштейна и Расстояние Дамерау – Левенштейнаkэтоеп и sэтояпграмм иметь расстояние 3.
  1. kиттен → sиттен (замена "k" на "s")
  2. ситтеп → ситтяп (замена «i» на «e»)
  3. сижу → сижуграмм (вставка "g" в конце).
Расстояние Яро – ВинклераJaroWinklerDist («МАРТА», «МАРХТА») =
  • это количество совпадающие символы;
  • это половина числа транспозиции(«МАРТА» [3]! = H, «МАРХТА» [3]! = T).
Наиболее часто встречающиеся символы kMostFreqKeySimilarity ('реsеарch ',' sеекороль ', 2) = 2

Рекомендации

  1. ^ Лу, Цзяхэн; и другие. (2013). «Меры сходства строк и соединения с синонимами». Материалы международной конференции ACM SIGMOD 2013 по управлению данными: 373–384. Дои:10.1145/2463676.2465313. ISBN  9781450320375.
  2. ^ Наварро, Гонсало (2001). «Экскурсия по приблизительному сопоставлению строк». Опросы ACM Computing. 33 (1): 31–88. Дои:10.1145/375360.375365.
  3. ^ Коэн, Уильям; Равикумар, Прадип; Финберг, Стивен (2003-08-01). «Сравнение показателей расстояния между строками для задач сопоставления имен»: 73–78. Цитировать журнал требует | журнал = (помощь)

внешняя ссылка