Сопоставление гештальт-образцов

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

Алгоритм

Сходство двух струн $S_{1}$ и $S_{2}$ определяется по формуле, вычисляющей удвоенное количество совпадающих символов $K_{m}$ разделить на общее количество символов обеих строк. Соответствующие символы определяются как некоторая самая длинная общая подстрока. плюс рекурсивно количество совпадающих символов в несовпадающих областях по обе стороны самой длинной общей подстроки:

$D_{ro}={\frac {2K_{m}}{|S_{1}|+|S_{2}|}}$

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

$0\leq D_{ro}\leq 1$

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

Образец

С 1	В	я	К	я	М	И	Д	я	А
SS2	В	я	К	я	М	А	Н	я	А

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

${\frac {2K_{m}}{|S_{1}|+|S_{2}|}}={\frac {2\cdot (|{\text{''WIKIM''}}|+|{\text{''IA''}}|)}{|S_{1}|+|S_{2}|}}={\frac {2\cdot (5+2)}{9+9}}={\frac {14}{18}}=0.{\overline {7}}$

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

Соответствующие символы Рэтклиффа/Оберсхелпа могут существенно отличаться от каждой самой длинной общей подпоследовательности данных строк. Например $S_{1}=q\;ccccc\;r\;ddd\;s\;bbbb\;t\;eee\;u$ и $S_{2}=v\;ddd\;w\;bbbb\;x\;eee\;y\;ccccc\;z$ иметь $ccccc$ как их единственная самая длинная общая подстрока, и никаких общих символов справа от ее появления, а также слева, что приводит к $K_{m}=5$. Однако самая длинная общая подпоследовательность $S_{1}$ и $S_{2}$ является $(ddd)\;(bbbb)\;(eee)$, общей длиной $10$.

Сложность

Время выполнения алгоритма $O(n^{3})$ в худшем случае и $O(n^{2})$ в среднем случае. Изменив метод вычислений, время выполнения можно значительно улучшить.

Коммутативное свойство

Реализация алгоритма сопоставления гештальт-образцов в библиотеке Python не является коммутативной :

$D_{ro}(S_{1},S_{2})\neq D_{ro}(S_{2},S_{1}).$

Образец

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

$S_{1}={\text{GESTALT PATTERN MATCHING}}$

и

$S_{2}={\text{GESTALT PRACTICE}}$

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

$D_{ro}(S_{1},S_{2})$ является ${\frac {24}{40}}$ с подстроками GESTALT P, A, T, E и для

$D_{ro}(S_{2},S_{1})$ метрика ${\frac {26}{40}}$ с подстроками GESTALT P, R, A, C, I.

Приложения

Питон ​ difflib библиотека, представленная в версии 2.1, реализует аналогичный алгоритм, предшествовавший алгоритму Рэтклиффа-Оберсхелпа. Из-за неблагоприятного поведения этой метрики сходства во время выполнения были реализованы три метода. Два из них возвращают верхнюю границу за более быстрое время выполнения. Самый быстрый вариант сравнивает только длину двух подстрок:

$D_{rqr}={\frac {2\cdot \min(|S1|,|S2|)}{|S1|+|S2|}}$,

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

$D_{qr}={\frac {2\cdot {\big |}\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big |}}{|S1|+|S2|}}$

# Dqr Implementation in Python
def quick_ratio(s1: str, s2: str) -> float:
    """Return an upper bound on ratio() relatively quickly."""
    length = len(s1) + len(s2)

    if not length:
        return 1.0

    intersect = collections.Counter(s1) & collections.Counter(s2)
    matches = sum(intersect.values())
    return 2.0 * matches / length

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

$0\leq D_{ro}\leq D_{qr}\leq D_{rqr}\leq 1$ и

$0\leq K_{m}\leq |\{\!\vert S1\vert \!\}\cap \{\!\vert S2\vert \!\}{\big |}\leq \min(|S1|,|S2|)\leq {\frac {|S1|+|S2|}{2}}$.

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

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

См. также

• Сопоставление с образцом