Сопоставление гештальт-паттернов - Gestalt Pattern Matching - Wikipedia

Сопоставление гештальт-паттернов,[1] также Распознавание образов Ratcliff / Obershelp,[2] это алгоритм сопоставления строк для определения сходство из двух струны. Он был разработан в 1983 г. Джон В. Рэтклифф и Джон А. Обершелп и опубликованы в Журнал доктора Добба в июле 1988 г.[2]

Алгоритм

Сходство двух струн и определяется по формуле, рассчитывая удвоенное количество совпадений символы делится на общее количество символов в обеих строках. Соответствующие символы определяются как самая длинная общая подстрока (LCS) плюс рекурсивно количество совпадающих символов в несовпадающих областях на обеих сторонах LCS:[2]

[3]

где показатель подобия может принимать значение от нуля до единицы:

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

Образец

S1WяKяMEDяА
S2WяKяMАNяА

Самая длинная общая подстрока - это WIKIM (серый) с 5 символами. Слева больше нет подстроки. Несовпадающие подстроки в правой части: EDIA и АНИЯ. У них снова самая длинная общая подстрока Я (темно-серый) длиной 2. Метрика подобия определяется:

Характеристики

Сложность

Время выполнения алгоритма в худшем случае и в среднем случае. Изменяя метод вычисления, время выполнения может быть значительно улучшено.[1]

Коммутативная собственность

Можно показать, что алгоритм сопоставления гештальт-шаблонов не коммутативный: [4]

Образец

Для двух струн

и

метрический результат для

является с подстроками ГЕСТАЛЬТ П, А, Т, E и для
метрика с подстроками ГЕСТАЛЬТ П, р, А, C, я.

Приложения

Алгоритм стал основой Python дифлиб библиотека, представленная в версии 2.1.[1] Из-за неблагоприятного поведения этой метрики подобия во время выполнения были реализованы три метода. Двое из них возвращают верхняя граница в более быстрое время выполнения.[1] Самый быстрый вариант сравнивает только длину двух подстрок:[5]

,
# Реализация Drqr на Pythondef real_quick_ratio(s1: ул, s2: ул) -> плавать:    "" "Очень быстро вернуть верхнюю границу ratio ()." ""    l1, l2 = len(s1), len(s2)    длина = l1 + l2    если нет длина:        возвращаться 1.0    возвращаться 2.0 * мин(l1, l2) / длина

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

,
# Реализация Dqr на Pythondef Коэффициент быстрой ликвидности(s1: ул, s2: ул) -> плавать:    "" "Относительно быстро вернуть верхнюю границу ratio ()." ""    длина = len(s1) + len(s2)    если нет длина:        возвращаться 1.0    пересекаться = коллекции.Прилавок(s1) & коллекции.Прилавок(s2)    совпадения = сумма(пересекаться.значения())    возвращаться 2.0 * совпадения / длина

Тривиально применяется следующее:

и
.

Рекомендации

дальнейшее чтение

  • Джон В. Рэтклифф и Дэвид Метценер: Сопоставление с образцом: гештальт-подход, Журнал доктора Добба, выпуск 46, июль 1988 г.

Смотрите также