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

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

Алгоритм

Сходство двух струн ${\displaystyle S_{1}}$ и ${\displaystyle S_{2}}$ определяется по формуле, рассчитывая удвоенное количество совпадений символы ${\displaystyle K_{m}}$ делится на общее количество символов в обеих строках. Соответствующие символы определяются как самая длинная общая подстрока (LCS) плюс рекурсивно количество совпадающих символов в несовпадающих областях на обеих сторонах LCS:^[2]

${\displaystyle D_{ro}={\frac {2K_{m}}{|S_{1}|+|S_{2}|}}}$^[3]

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

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

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

Образец

S1	W	я	K	я	M	E	D	я	А
S2	W	я	K	я	M	А	N	я	А

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

${\displaystyle {\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}}}$

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

Сложность

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

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

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

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

Образец

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

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

и

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

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

${\displaystyle D_{ro}(S_{1},S_{2})}$ является ${\displaystyle {\frac {24}{40}}}$ с подстроками ГЕСТАЛЬТ П, А, Т, E и для

${\displaystyle D_{ro}(S_{2},S_{1})}$ метрика ${\displaystyle {\frac {26}{40}}}$ с подстроками ГЕСТАЛЬТ П, р, А, C, я.

Приложения

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

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

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

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

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

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

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

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

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

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

1. diffflib - Помощники для вычисления дельт внутри документации Python
2. Национальный институт стандартов и технологий Распознавание образов Рэтклиффа / Обершелпа
3. Илья Ильянков: Сравнение алгоритмов Джаро-Винклера и Рэтклиффа / Обершелпа при проверке орфографии, Май 2014 г. (PDF)
4. Как работает Pythons SequenceMatcher? на stackoverflow.com
5. Заимствовано из Python 3.7.0, diffflib.py Строки 38–41 и 676–686

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

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

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

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