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

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

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? Если бы вы могли подсчитать количество последовательных символов и принять отношение к символам, не разделенным, возможно, это было бы хорошей эвристикой?

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

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

Ответ 1

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

Расстояние Левенштейна: минимальное количество односимвольных изменений, необходимых для смены одного слова на другое. Строки не должны быть одинаковой длины.
Расстояние Хэмминга: количество символов, которые отличаются в двух строках равной длины.
Smith-Waterman: Семейство алгоритмов для вычисления сходства подпоследовательности переменных.
Коэффициент Sørensen-Dice: алгоритм подобия, который вычисляет разностные коэффициенты соседних пар символов.

Посмотрите на них, а также на страницу wiki по этой теме.

Ответ 2

Расстояние Дамерау Левенштейна - еще один алгоритм для сравнения двух строк и аналогичен алгоритму расстояния Левенштейна. Разница между ними заключается в том, что он также может проверять перестановки между символами и, следовательно, может дать лучший результат для исправления ошибок.

Например: расстояние Левенштейна между night и nigth равно 2 но расстояние Дамерау Левенштейна между night и nigth будет равно 1, потому что это всего лишь своп пары символов.

Ответ 3

Вы можете использовать для этого ngrams. Например, преобразуйте две строки в словарные триграммы (обычно в нижнем регистре) и сравните их процент, равный друг другу.

Ваша задача - определить минимальный процент для сходства.

http://en.wikipedia.org/wiki/N-gram

Ответ 4

Другой алгоритм, который вы можете рассмотреть, - это сходство Саймона Уайта:

def get_bigrams(string):
    """
    Take a string and return a list of bigrams.
    """
    if string is None:
        return ""

    s = string.lower()
    return [s[i : i + 2] for i in list(range(len(s) - 1))]

def simon_similarity(str1, str2):
    """
    Perform bigram comparison between two strings
    and return a percentage match in decimal form.
    """
    pairs1 = get_bigrams(str1)
    pairs2 = get_bigrams(str2)
    union = len(pairs1) + len(pairs2)

    if union == 0 or union is None:
        return 0

    hit_count = 0
    for x in pairs1:
        for y in pairs2:
            if x == y:
                hit_count += 1
                break
    return (2.0 * hit_count) / union

Ответ 5

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

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