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

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

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

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

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

Примеры выбранных строковых мер [ править ]

ИмяПример
Расстояние Хэмминга« Ка рол в » и « ка Чет в » является 3.
Расстояние Левенштейна и Damerau-расстояние Левенштейнаk itt e n и s itt i n g имеют расстояние 3.
  1. k itten → s itten (замена «k» на «s»)
  2. sitt e n → sitt i n (замена «i» на «e»)
  3. sittin → sittin g (вставка буквы "g" в конце).
Расстояние Яро – ВинклераJaroWinklerDist («МАРТА», «МАРХТА») =
  • это количество совпадающих символов ;
  • составляет половину количества транспозиций ( "MARTHA"[3]!=H, "MARHTA"[3]!=T).
Наиболее часто встречающиеся символы kMostFreqKeySimilarity (' r e s e a r ch', 's ee king', 2) = 2


Ссылки [ править ]

  1. ^ Лу, Цзяхэн; и другие. (2013). «Сходство строк измеряет и объединяется с синонимами» . Материалы Международной конференции по управлению данными ACM SIGMOD 2013 : 373–384. DOI : 10.1145 / 2463676.2465313 . ISBN 9781450320375.
  2. Перейти ↑ Navarro, Gonzalo (2001). «Экскурсия по приблизительному сопоставлению строк». ACM Computing Surveys . 33 (1): 31–88. DOI : 10.1145 / 375360.375365 . ЛВП : 10533/172862 .
  3. ^ Шломи Долев ; Мохаммад, Ганаим; Александр, Бинун; Сергей, Френкель; Йили, С. Сан (2017). «Взаимосвязь Жаккара и расстояния редактирования в кластеризации вредоносных программ и онлайн-идентификации». 16-й Международный симпозиум IEEE по сетевым вычислениям и приложениям : 369–373.
  4. ^ Коэн, Уильям; Равикумар, Прадип; Финберг, Стивен (2003-08-01). «Сравнение метрик расстояния строк для задач сопоставления имен» : 73–78. Cite journal requires |journal= (help)


Внешние ссылки [ править ]

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