В стандартном интернет-магазине, как и в любой другой современной учетной системе есть категории, товары и производители, как и любая другая учетная система, все они имеют свои уникальные коды (ID), для последующей идентификации в пределах базы данных интернет-магазина. У категорий товаров может быть еще второй код идентификации, который ссылается на родительскую категорию, для создания иерархии категорий (структура категорий и подкатегорий). Например товар "А" имеет уникальный числовой код 1(ID=1), имеет ссылку на категорию с кодом 34, а так же ссылку на производителя с кодом 14. При этом в справочнике категорий, с кодом 34 числится категория "Струйные", которая имеет, код родительской категории равный 11, при этом в том же справочнике категорий с кодом 11 числится категория "Принтеры". Это означает что: 11 это главная категория ("Принтеры"), т.е. родитель по отношению к категории с кодом 34 ("Струйные"), то есть 34 является подкатегорией 11, а товар "А" с уникальным кодом 1 находится в категории 34, т.е. в категории "Струйные", и следовательно так устанавливается иерархия категорий и товаров. В справочнике производителей с кодом 14 хранится название производителя "Б", т.к. товар ссылается на этого производителя, то он принадлежит к этому производителю.

Пример хранения данных в справочнике категорий:
ID  | Родительский ID  |  Название категории
11      0                                Принтеры
34      11                              Струйные
35      11                              Лазерные
36      11                              Матричные

Все ID являются уникальными и не могут повторяться (кроме родительского ID).

Структуру сайта (интернет-магазина), вместе с категориями, товарами и производителями , а так же их ID нужно загрузить один раз в программу серии E-Trade, чтобы программа понимала, какая на данный момент существует иерархия категорий, дать ей тем самым информацию об этих уникальных кодах, чтобы она не создавала такие же и не было наложений новых кодов на старые. В программе настраиваются прайс-листы поставщиков и добавляются новые товары в категории из интернет-магазина, все корректировки и добавления товаров, а также удаления все должно происходить через программу.

Рассмотрим пример на всем известном сайте ЯндексМаркет.

http://market.yandex.ru/catalogmodels.xml?CAT_ID=108206
Данная ссылка ссылается на категорию Телевизоры, ее уникальный код 108206

http://market.yandex.ru/model.xml?hid=&modelid=6138284
Данная ссылка ссылается на товар с уникальным кодом 6138284

Именно эти данные и нужны программе.

Правильнее, более функциональнее и выгоднее для Вас будет один раз загрузить категории и товары в программу и уже иметь единую учетную систему. Затем можно будет получать сводный прайс, либо же обновлять этими данными магазин, либо и то и то. Тем самым у Вас будет эталонная учетная система, в которой Вы сможете делать корректировки, отслеживать актуальность наличия и цен. С легкостью этими данными обновлять магазин и получать сводный прайс на основания прайс-листов от поставщиков.

Информационные технологии (ИТ, от англ. information technology, IT) — широкий класс дисциплин и областей деятельности, относящихся к технологиям управления и обработки данных, в том числе, с применением вычислительной техники.

Содержание

* Введение
* Фонетическое кодирование
* Саундэкс
* Саундэкс Дэйча-Мокотоффа
* Система идентификации и сведений штата Нью-Йорк
* Метафон
* Двойной метафон
* Каверфон
* Метрика похожести
* Дистанция Хэмминга
* Дистанция редактирования
* Триграмма
* Распознавание форм Ратклиффа/Обершелпа
* Джаро-Винклер
* Опечатки
* Сравнение алгоритмов
* Ресурсы

Введение в тему распознавания наименований товаров при обработке прайс-листов

В наше время компьютерные базы данных содержат очень большое число информации (данных в электронном виде). Однако извлечение текстовой информации затрудняется когда текст написан с оплошностями, либо как то на скорую руку, т.е. при этом данный информационный текст является не точным. При обработке прайс-листов данные проблемы довольно часто проявляются. Некоторые из методов описаных здесь внедрены в программу обработки прайс-листов E-Trade PriceList Importer.

Эта заметка приурочена к методам примерного сопоставления строчек текста (слов). Она даёт упрощенное, хотя понятное описание алгоритмов с образцами работы с этими алгоритмами.

Во-первых, мы собираемся разъяснить упражнения конструирующие фонетические коды для выискиваемого слова, которые звучат в равной степени, хотя пишется разнообразно. Во-вторых, мы поясним упражнения дающие различные разновидности метрик похожести слова, применяемых в поиске дозволяющем промахи, т.е. похожести слов или ошибочном написании операторами (менеджерами) компаний занимающихся формированием прайс-листов. В данной статье, приведенные методы сравниваются, дабы читатель сумел подобрать более оптимальный метод под его нужды. Смотрите помимо прочего ресурсы в конце заметки.

Фонетическое кодирование

Обсуждаемые тут упражнения употребляются для облегчения поиска в базах этих, когда известно, как текст произносится, хотя не как пишется. Для данного конструируются фонетические коды для выискиваемого слова, на тот момент как информационная база сначала индексируется используя данные коды. Фамилии, которые звучат в равной степени, хотя пишутся по-всякому, как SMITH и SMYTH, имеют однообразный вид написания и имеют все шансы бить тревогу об ошибочной записи. Использование алгоритмов фонетического кодирования уменьшает трудности с ошибочным либо различным написанием одинаковых слов.

Фонетическое кодирование может быть чрезвычайно полезно для соединения выбранных личных имён или же имён фирм. Оно и еще употребляется для опознавания речи и в поисковыых системах баз этих в том числе анти-террористических. Как оказалось фонетическое кодирование так же полезно при обработке прайс-листов поставщиков в программе обработки прайс-листов E-Trade PriceList Importer.

Саундэкс как первый помошник в решении распознавания наименований товаров при обработке прайс-листов

Саундэкс (Soundex) конструирует фонетические коды для своих имён. Результирующий код состоит из одной буквы и трёх цифр, любая из которых подходит 6 согласным звукам. Алгоритм в первый раз был применён в переписи Соединенные Штаты в 1880 году.


Процедура

1. Взять первую букву.
2. Транслировать оставшиеся буквы:
B, F, P, V > 1
C, G, J, K, Q, S, X, Z > 2
D, T > 3
L > 4
M, N > 5
R > 6
3. Удалить соседние буквы имеющие однообразный код.
4. Удалить неначальные A, E, I, O, U, Y, W и H.
5. Взять 1-ые 4 буквы наполняя справа нулями.

Примеры

1. ALEXANDRE > A4E2A536E > A4E2A536E > A42536 > A425.
2. ALEKSANDER > A4E22A53E6 > A4E2A53E6 > A42536 > A425.

Саундэкс Дэйча-Мокотоффа

В 1985 году свежий метод Саундэкс Дэйча-Мокотоффа (Daitch-Mokotoff Soundex) был применён для фонетического кодировки имен славянских и идиш с схожим произношением хотя различным написанием. Наиболее актуальные совершенствования сравнивая с Саундэкс: наиболее длиннющий код - 6 знаков; изготавливаются 2 различных кода, как скоро вероятны 2 различных произношения; кодирование применяет 10 цифр от 0 к 9.

Система идентификации и сведений штата Нью-Йорк

Система идентификации и сведений штата Нью-Йорк (NYSIIS - New York State Identification and Intelligence System) была разработана в 1970 году при помощи жесткого эпирического анализа. В данном методе конструируется фонетический код до 6 букв.

Процедура

1. Транслировать 1-ые буквы фамилии:
MAC > MCC
PH > FF
KN > NN
PF > FF
K > C
SCH > SSS
2. Транслировать заключительные буквы фамилии:
EE > Y
IE > Y
DT, RT, RD, NT, ND > D
3. Транслировать оставшиеся буквы по правилами, букву за буквой:
EV > AF; по другому E, I, O, U > A
Q > G
Z > S
M > N
KN > N; по другому K > C
SCH > SSS
PH > FF
H > предшествующая буква, ежели предшествующая либо дальнейшая - не гласная
W > предшествующая буква, коль скоро предшествующая - гласная
4. Проверить заключительную букву:
когда заключительная буква - S, удалить её
раз заключительные буквы - AY, сменить на Y
коль скоро заключительная буква - A, удалить её
5. Удалить вторую из двойных букв.
6. Взять первые шесть букв.
Примеры

1. ALEXANDRE > ALAXANDRA > ALAXANDR > ALAXANDR > ALAXAN
2. ALEKSANDER > ALACSANDAR > ALACSANDAR > ALACSANDAR > ALACSA

Метафон

Алгоритм Метафон (Metaphone) фонетически кодирует слова методом убавления их до 16 согласных звуков: B, X, S, K, J, T, F, H, L, M, N, P, R, 0, W, Y. Ноль дает звук "th"; X предполагает "sh".

Процедура

1. Удалить вторую из двойных букв, кроме C.
2. Если слово наступает с KN, GN, PN, AE, WR, удалить первую букву.
3. Удалить B в конце слова опосля M.
4. C > X в CIA или же CH; C > S в CI, CE либо CY; C > K иначе.
5. D > J в DGE, DGY либо DGI; D > T иначе.
6. Удалить G в GH и ежели не в конце или же перед гласным в GN либо GNED; G > J перед I либо E или же Y когда не двойная GG; G > K при другом развитии событий.
7. Удалить H опосля гласной и в случае если последующая буква не гласная.
8. Удалить K в последствии C.
9. P > F в PH.
10. Q > K.
11. S > X в SH или же SIO или же SIA.
12. T > X в TIA или же TIO; T > 0 в TH; T удаляется в TCH.
13. V > F.
14. Если слово наступает с WH, удалить H; удалить W когда грядущая буква не гласная.
15. Если слово наступает с X, в тех случаях X > S; X > KS иначе.
16. Удалить Y раз последующая буква не гласная.
17. Z > S.
18. Гласные сберегаются исключительно как скоро они присутствуют сначала слова.
19. Во всех оставшихся вариантах буквы не изменяются.

Примеры

1. ALEXANDRE > ALEKSANTRE > ALKSNTR
2. ALEKSANDER > ALEKSANTER > ALKSNTR

Двойной метафон - именно данный эффективный метод помог облегчить распознавание наименований товаров при обработке прайс-листов

Двойной метафон (Double metaphone) - улучшенный вариант Метафона. Этот метод фонетически кодирует слова методом убавления их до 12 согласных звуков. Он отдаёт 2 кода в случае если слово имеет 2 вероятных произношения. Данный метод был использован при поиске соответствия в обрабатываемых прайс-листах в программе обработки прайсов E-Trade PriceList Importer.

Каверфон

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

Новая версия Каверфон 2.0 была предложена для наиболее совместного фонетического сопоставления.

Алгоритмы примерного сопоставления слов, вероятность распознавания наименований товаров.
Конец первой части.

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

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

Многие из данных упражнений вычисляют однообразие 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

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