Расстояние между двумя строками

Question

Я не верю, что стандартная библиотека предоставляет что-либо, чтобы вычислить расстояние между двумя строками, и я не могу найти ничего в Boost StringAlgo. Итак, есть ли какая-нибудь другая библиотека, которую я мог бы использовать?

Я не слишком придирчив к алгоритму. Яро-Винклер тоже, Левенштейн тоже, и я открыт для предложений, я не хочу кодировать то, что кто-то уже закодировал.

Answer 1

Вы не определяете свой вопрос с фактической метрикой расстояния, поэтому я предполагают, он просто должен удовлетворять условиям в «Metric (mathematics)»:

метрика на множестве X является функцией (называется функцией расстояния или просто расстояние) д: X × X → R (где к множество действительных чисел). Для всех х, у, г в X, эта функция должна удовлетворять следующие условия:

• д (х, у) ≥ 0 (неотрицательность, или разделение аксиома)
• д (х, y) = 0 тогда и только тогда, когда x = y (тождество неразличимых или аксиома совпадения)
• d (x, y) = d (y, x) (симметрия)
• d (x, z) ≤ d (x, y) + d (y, z) (неравенство субаддитивности/треугольника).

Предположим, мы определим d как таковой:

  { 0 if x = y 
d(x, y) = { 
      { 1 otherwise 

Так что первые три условия:

• d(x, y) ≥ 0
• d(x, y) = 0 iff x = y
• d(x, y) = d(y, x) = 0 for x = y, и d(x, y) = d(y, x) = 1 for x ≠ y

Для последнего условия, есть два случая:

• d(x, z) = 0. Единственными возможными значениями для правой части являются 0, 1 и 2, любые из которых удовлетворяли бы условию.
• d(x, z) = 1. Предположим, что правая сторона не равна больше или равна единице. Это означает, что он должен быть равен нулю. Тогда оба термина на правой стороне должны были бы быть 0, что означает, что x = y и y = z. Второе условие означает, что x = z, что, в свою очередь, означает, что d(x, z) = 0. Это противоречие, поэтому правая часть должна быть больше или равна единице.

Тогда мы можем определить метрику как:

int d(std::string x, std::string y) { 
    if (x == y) { 
     return 0; 
    } else { 
     return 1; 
    } 
} 

Answer 2

This related question contains a code snippet демонстрирующего расстояние Левенштейна. Он также был implemented for MySQL in this C code.

Answer 3

Вы можете попробовать SimString.

SimString - это простая библиотека для быстрого приближения строки. Приблизительное извлечение строк находит строки в базе данных, чье соответствие с строкой запроса не меньше порогового значения. Поиск не только идентичные, но похожие строки, примерное извлечение строк имеет различные приложения, включая коррекцию орфографии, гибкое сопоставление словаря , дублирование обнаружения и запись.

SimString поддерживает коэффициенты косинуса, жаккарда, кости и перекрытия как показатели сходства. SimString использует буквенные n-граммы как функции для вычислительной последовательности.

или SimMetric библиотека.

SimMetrics - это метрическая библиотека сходства, например. от расстояния редактирования (Левенштейн, Gotoh, Jaro и т. д.) до других показателей (например, Soundex, Chapman). Работа, предоставляемая британским университетом Шеффилда, финансируемая (AKT) a IRC, спонсируемая EPSRC, номер гранта GR/N15764/01.

Или libdistance библиотека, которая имеет реализацию Левенштейна, Dameru, Needleman-Wunsch, Хэмминга, Блум фильтр, Jaccard и расстояния Минковского.

Phonetic algorithms также может представлять интерес.