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