Каковы некоторые алгоритмы для сравнения, насколько похожи две строки?

Мне нужно сравнить строки, чтобы решить, представляют ли они одну и ту же вещь. Это относится к названиям случаев, введенным людьми, где могут отличаться сокращения и другие мелкие детали. Например, рассмотрим следующие два заголовка:

std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";

В отличие от:

std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";

Человек может быстро определить, что это, скорее всего, одно и то же. Текущий подход, который я выбрал, состоит в том, чтобы нормализовать строки, поместив все буквы в нижний регистр и удалив все знаки препинания и пробелы, давая:

std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";

А также:

std::string secondNormalized = "harpervthelawofficesofhueylueyllp";

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

Может быть, какая-нибудь программа сравнения символов могла бы помочь? Я видел хорошие программы сравнения строк для сравнения различий в проверяемом коде, есть ли что-то подобное на символьной основе, может быть, в boost? Если бы вы могли посчитать общее количество последовательных символов и взять отношение к неразделенным символам, возможно, это было бы хорошей эвристикой?

В конце мне нужно логическое решение относительно того, считать ли их одинаковыми или нет. Он не должен быть идеальным, но в идеале он редко должен ошибаться.

Какой алгоритм я могу использовать, который даст мне определенную количественную оценку того, насколько похожи эти две строки друг на друга, которые я затем могу преобразовать в ответ да / нет с помощью некоторой эвристики?

Ответы на вопрос(3)

Ваш ответ на вопрос