Часть №1. Алгоритмы сопоставления товаров при обработке прайс-листов

Часть №1. Алгоритмы сопоставления слов и вероятность распознавания наименований товаров при обработке и анализе прайс-листов

Содержание

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

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


В наше время компьютерные базы данных содержат очень большое число информации (данных в электронном виде). Однако извлечение текстовой информации затрудняется когда текст написан с оплошностями, либо как то на скорую руку, т.е. при этом данный информационный текст является не точным. При обработке прайс-листов данные проблемы довольно часто проявляются. Некоторые из методов описаных здесь внедрены в программу обработки прайс-листов 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 была предложена для наиболее совместного фонетического сопоставления.

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

 

 

Спешим рекомендовать Вам этих бизнес ассистентов