Является ли это уже алгоритмом сходства строк?

Question

Я незнаком с строковыми алгоритмами сходства, за исключением Levenshtein Distance, потому что это то, что я использую, и оказалось, что это было не так идеально.

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

Вот алгоритм на примере:

строки 1: "Пол Джонсон"

строка 2: "Джон Полсон"

Шаг 1: найти все самые длинные матчи

Матч 1: "Пол"

Матч 2: "Джон"

Матч 3: "сын"

Матч 4: ""

Шаг 2: Вычислить оценки для каждого матча с этой формулой: ((match.len /string.len)*match.len) Это позволяет более длинным строкам взвешивать более сбалансированную скорость в зависимости от длины строки.

Матч 1: (4/12) * 4 = 1,333 ...

Матч 2: 1,333 ...

Матч 3: .75

матч 4: 0,083

Шаг 3: выполните шаги 1 и 2 на больших весах (совпадения совпадений). Этого я точно не понял. но я думаю, что если «сын» приходит после «Пола Иоанна», и это происходит после «Иоанна Павла», то это должно рассчитывать на что-то.

Шаг 4: суммируйте все оценки, которые были рассчитаны.

результаты: 1,333 + 1,333 + .75 + .083333 = 3,4999 ... (плюс все баллы шаг 3 производит)

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

Answer 1

То, что вы описали, несколько напоминает то, что следующая бумага вызывает самую длинную общую подстроку (LCS). Для краткого описания и сравнения с другими алгоритмами: A Comparison of Personal Name Matching

Этого алгоритм [11] несколько раз находит и удаляет самую длинную общую подстроку в двух строках по сравнению, до минимума длины (обычно устанавливаются 2 или 3).

...
Показатель подобия может быть рассчитан на , деля общую длину общих подстрок на минимум, максимальная или средняя длина двух исходных строк (аналогично Smith-Waterman).

...

этот алгоритм подходит для сложных имен, которые имеют слова (как given- и фамилия) выгружена.