Метрика строки
Метрика, измеряющая расстояние между двумя строками текста

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

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

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

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

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

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

ИмяОписаниеПример
Расстояние ХэммингаТолько для строк одинаковой длины. Количество измененных символов.« ка рол ин » и « ка тр ин » — это 3.
Расстояние Левенштейна и расстояние Дамерау–ЛевенштейнаОбобщение расстояния Хэмминга, допускающее строки различной длины и (совместно с Дамеро) транспозициикотенок и сидящий находятся на расстоянии 3 .​​​
  1. k itten → s itten (замена "s" на "k")
  2. sitt e n → sitt i n (замена «i» на «e»)
  3. сидеть → сидеть g (вставка "g" в конце).
Расстояние Яро–ВинклераJaroWinklerDist("МАРТА","МАРХТА") =
г дж = 1 3 ( м | с 1 | + м | с 2 | + м − т м ) = 1 3 ( 6 6 + 6 6 + 6 − 2 2 6 ) = 0,944 {\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 м} — количество совпадающих символов ;
  • т {\displaystyle т} составляет половину числа транспозиций ( "MARTHA"[3]!=H, "MARHTA"[3]!=T).
Наиболее часто встречающиеся символы kMostFreqKeyПохожие ( ' исследование ' , 'исследование ' , 2 ) = 2

Ссылки

  1. ^ Лу, Цзяхенг и др. (2013). «Меры схожести строк и соединения с синонимами». Труды Международной конференции ACM SIGMOD 2013 года по управлению данными . С.  373–384 . doi :10.1145/2463676.2465313. ISBN 9781450320375. S2CID  2091942.
  2. ^ Наварро, Гонсало (2001). «Путеводитель по приближенному сопоставлению строк». ACM Computing Surveys . 33 (1): 31– 88. doi : 10.1145/375360.375365. hdl : 10533/172862 . S2CID  207551224.
  3. ^ Шломи Долев ; Мохаммад, Ганайим; Александр, Бинун; Сергей, Френкель; Йели, С. Сан (2017). «Взаимосвязь Жаккара и расстояния редактирования при кластеризации вредоносных программ и онлайн-идентификации». 16-й Международный симпозиум IEEE по сетевым вычислениям и приложениям : 369–373 .
  4. ^ abcde Метрики строк Сэма - Компьютерная лингвистика и фонетика
  5. ^ Рассел, Дэвид Дж. и др. «Метрика расстояния на основе грамматики обеспечивает быструю и точную кластеризацию больших наборов последовательностей 16S». BMC bioinformatics 11.1 (2010): 1-14.
  6. ^ Коэн, Уильям; Равикумар, Прадип; Файнберг, Стивен (01.08.2003). «Сравнение метрик расстояний строк для задач сопоставления имен»: 73–78 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  • Метрики схожести строк для интеграции информации Достаточно полный обзор Архивный индекс на Wayback Machine
  • Библиотека с открытым исходным кодом Университета Карнеги-Меллона
  • Проект StringMetric — библиотека Scala строковых метрик и фонетических алгоритмов.
  • Проект Natural — библиотека обработки естественного языка JavaScript , которая включает в себя реализацию популярных строковых метрик.
Получено с "https://en.wikipedia.org/w/index.php?title=String_metric&oldid=1239983587"