Метрика похожести названий товаров при формировании прайсов

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

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

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

Дистанция Хэмминга

Для 2-ух строчек схожей длины, дистанция Хэмминга (Hamming distance) - число мест, в каких строчки имеют различные знаки.

Примеры

1. Дистанция Хэмминга от ALEXANDRE до ALEKSANDR: 6 (ALE схож, оставшиеся 6 знаков разны).

Дистанция редактирования

Дистанция редактирования (edit distance) меж 2 строчками ориентируется как наименьшее количество вставок, замен и удалений знаков необходых чтобы преобразовать первую строчку во вторую. Дистанция 0 значит, что строчки схожи.

Алгоритм был изобретён в 1965 русским ученым Владимиром Левенштейном. По данной первопричине Дистанция редактирования величается кроме того Дистанцией Левенштейна.

Имеются прогрессивные варианты метода, придавая различные веса вставке, замене и удалению.
Примеры

1. Дистанция редактирования от ALEXANDRE до ALEKSANDER: 4 (смена X на K, внедрение S опосля K, внедрение E опосля D, удаление E в конце).

Триграмма

Триграммное однообразие (trigram similarity) меж 2-мя строчками ориентируется количеством схожих символьных триплетов в двух строчках. Алгоритм можнож обобщить на n-граммы, где n=1, 2, ...

Строки string1 и string2 пополняются слева и справа одним знаком пробела. Затем строчки делятся на триплеты (триграммы). Окончательно, однообразие рассчитывается по формуле:

s = 2*m / (a + b).

Здесь:

m - количество схожих триграмм
a - количество триграмм в string1
b - количество триграмм в string2
Примеры

1. Сходство ALEXANDRE и ALEKSANDER: 2*3 / (9+10) = 0.32 (схожи _AL, ALE, AND).

Распознавание форм Ратклиффа/Обершелпа

Алгоритм Ратклиффа/Обершелпа (Ratcliff/Obershelp pattern recognition) вычисляет однообразие 2-ух строчек как двойное количество надлежащих знаков разделённое на абсолютное количество знаков в строчках. Соответствующие знаки присутствуют в лично длинноватой единой подпоследовательности плюс, рекурсивно, надлежащие знаки в остальной доли по любую сторону от самой длинной общей подпоследовательности.
Примеры

1. Сходство ALEXANDRE и ALEKSANDER: 2 * (3+3+1+1) / (9+10) = 0.84 (отвечают ALE, AND, E, R).

Джаро-Винклер

Сходство Джаро-Винклера (Jaro-Winkler similarity) было использовано в переписи Соединенных Штатов и применено в следующей обработке.

Для этих строчек string1 и string2, их однообразие задаётся формулой:

s = m/3a + m/3b + (m-t)/3m.

Здесь:

m - количество подходящих знаков
a - протяженность string1
b - протяженность string2
t - количество перестановок

Два знака являются подходящими, лишь коль скоро они пребывают не далее нежели (max(a,b)/2 - 1). Первый подходящий знак в string1 сравнивается с первым подходящим знаком в string2; 2 подходящий знак в string1 сравнивается со вторым надлежащим знаком в string2, и пр.. Число сообразных знаков делённое на 2 даёт количество перестановок.

Улучшенный способ Джаро-Винклера примет на вооружение веса прекрасные от 1/3. Он кроме того даёт наименьший авторитет каким-либо типам погрешностей: зрительного сканирования, клавишного ввода и в конце строчки.
Примеры

1. Сходство ALEXANDRE и ALEKSANDER: (8/9 + 8/10 + (8-1)/8) / 3 = 0.85 (отвечают A, L, E, A, N, D, R, E; 1 перестановка).

Опечатки

Имеются некие методы, учитывающие оплошности ввода на клавиатуре: V заместо B, 6 вместо Y и так далее. Особо часто путают при написание наименований товаров буквы латинских с кириллицей, если местным является кириллитический язык, одно из нововедений в программе обработкий прайсов было внедрение нового модуля который автоматически корректирует неправильное написание, а для тех наименований товаров где не возможна ручная корректировка предлагается в полуручном режиме скорректировать данные очепятки, т.е. опечатки.

Сравнение алгоритмов

Выбор кого-то из алгоритмов примерного сопоставления строчек основным образом находится в зависимости от природы промахов, оказывающих большое влияние на текст.
Алгоритм Тип Когда применять
Саундэкс фонетический английские слова с орфографическими оплошностями
Дэйч-Мокотофф фонетический европейские имени прописанные по-всякому
NYSIIS фонетический английские и некие заморские слова с орфографическими промахами
Метафон, Двойной метафон фонетический английские слова с орфографическими промахами
Каверфон 2.0 фонетический английские слова с орфографическими промахами
Хэмминг, Левенштейн идентичность локальные орфографические промахи
Триграмма, n-грамма идентичность орфографические промахи, редактированный текст
Ратклифф/Обершелп идентичность орфографические оплошности, редактированный текст
Джаро-Винклер идентичность оплошности орфографические и опечатки

Ресурсы

Смотрите и еще необъятную библиографию Интернета на британском языке.

1. Дистанция Левенштейна в Википедии — вольной энциклопедии.
http://ru.wikipedia.org/
2. Описание функций обработки строчек PHP: levenshtein, soundex, similar_text e metaphone.
http://www.php.net/manual/ru/ref.strings.php

Алгоритмы приблизительного сравнения текста