|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Astafiev 2:5000/228.16 27 Sep 2001 18:12:40
To : All
Subject : Похожесть стpок
--------------------------------------------------------------------------------
EJ>> Как вычислить сабж? Желательно вещественной величиной в интеpвале
EJ>> 0..1. То естьумножаем на 100 и получаем пpоцентную похожесть...
EJ>> Как вообще похожестьнаходится?
AD>
AD> ftp://ftp.simtel.net/pub/simtelnet/gnu/djgpp/v2apps/
AD> edi0441s.zip||rh1478s.zip
Ищи в сети "мягкое сравнение" или "мягкую похожесть" или же "нечеткое
сравнение", "нечеткую похожесть" - т.е.
+soft +compare
+fuzzy +compare
на www.google.com или на ya.ru
еще с год-полтора назад была действительно(!) хорошая статья Андрея Фионика в
RU.DELPHI.DB
после чего я заинтересовался этой проблемой и собрал несколько алгоритмов в
облaсти нечеткого сравнения строк.
Тема действительно, очень интересная.
После чего я заинтересовался нечеткой логикой... :)
Д RU.DELPHI.DB (2:5000/130.53) ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД RU.DELPHI.DB Д
Msg : 2 of 70 +44 45 47 51 61
From : Andrew V. Fionik 2:5020/400 02 Aug 00 00:40:02## To : All 02 Aug 00 10:42:38
Subj : DX. Правильное заполнение справочников или метод параметрической коррел
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
From: "Andrew V. Fionik" <ender@sonda.miass.chel.su>
Subject: DX. Правильное заполнение справочников или метод параметрической
корреляции
Привет всем.
Возникла тут у меня задача, решил ее как то. Решив, понял что можно решить
еще на один раз и на порядок круче, однако хотелось бы передать знания, так
сказать тем у кого их нет, и, может быть узнать мнение тех кто знает больше
меня.
Hи на какое авторство я не претендую, ибо сам узнал это от моего коллеги,
мужика чрезвычайно умного. Весь метод и терминология с его слов.
Итак! Часто возникает ситуация когда пользователь может выбрать некоторую
информацию из справочника (для заполнения какой-либо формы), так-же он может
ввести ее в строке ввода (для скорости). При этом возможны следующие
варианты дальнейшего развития событий:
1. Введенное значение ошибочно и его нет в справочнике.
2. Введенное значение правильно, но его еще нет в справочнике.
Ситуация, когда введенное значение присутствует в справочнике нами
рассматриваться не будет, т.к. тут нет никакой проблемы. Организационные
методы борьбы с ошибками ввода информации тоже рассматривать не будем.
Таким образом встает задача - найти в справочнике слова, похожие на
введенное и отсутствующее в справочнике, и предложить пользователю выбрать
одно из них. Вопрос в том, как определить похожие слова? Есть алгоритм
SoundEx (http://physics.nist.gov/cuu/Reference/soundex.html), который
кодирует каждое слово определенным образом. Говорят что коды потом можно
сравнивать. Сравнив введенное слово по очереди с каждым элементовм
справочника получим возможность определить похожесть слов. У этого алгоритма
есть недостатки: работает только по ограниченному набору букв, языкозависим
(где взять таблицу кодирования для русского языка я не знаю, а для прочих и
подавно) неустойчив к ошибкам первой буквы (что встречается довольно часто).
Другой алгоритм, который может решать подобную задачу, алгоритм
параметрической корреляции. По крайней мере так его мне назвали устно, может
быть его официальное название совсем другое. Его и рассмотрим.
Суть алгоритма заключается в том, чтобы подсчитать количество совпадающих
последовательных букв в "сравниваемых" словах. Причем совпадающие буквы
необязательно должны идти строго друг за другом. Слова с наибольшим
количеством совпадающих букв и будут похожими. Кроме того, анализ
производится не только с начала тестируемого слова но и может начинаться с
других его позиций.
Hапример, рассмотрим случай с человеческими именами:
Алексей - Александр, степень похожести 5
Алексей - Алексей, степень похожести 7
[теперь будем нарочно ошибаться]
Пропустим букву в слове: лексей, Алексе, Алесей - Алексей, степень похожести
6
Ошибочно напишем букву в слове: АXексей - Алексей, 5 (в то время как для
Александра будет 3)
Добавим лишнюю букву в слово: Aлексейц - Алексей, 7 (для Александра будет 5)
Общие закономерности можно вывести такие:
1. Чем длиннее само имя, тем меньшее влияние оказывают ошибки.
2. Hаиболее тяжело переносятся ошибки на границе между составляющими частями
слова: АлексXей даст одинаковую степень похожести для "Александр" и
"Алексей". Грань между изначально похожими словами становится ощутимо
тоньше.
3. Алгоритм языконезависим.
Для проверки взял готовый справочник из уже имеющейся базы данных и вот что
получилось:
Заранее слово с ошибкой:
Исходное слово: "Алексй"
6, Алексей
5, Александр
5, Александра
4, Абдулибек
4, Алекбер
4, Алектер
3, Адолет
3, Аксентий
3, Алена
3, Алеся
3, Алефтина
3, ...
3, Исламбек
3, Саламбек
3, Талайбек
3, Феликс
2, Аатолий
2, Абалгизи
... ниже еще более тысячи имен, набранных с ошибками и без, со степенями
схожести 2 и ниже.
Исходное слово: "Эндер"
5, Эскандер
5, Эскендер
4, Искандер
3, Айдер
3, Андре
3, Андрей
3, Аниде
3, Вальдемар
3, Владимер
3, Годерзи
3, Мохдзахер
3, Эндир
3, Эреджер
2, Абдель
2, Абдулибек
... ниже еще более тысячи имен, набранных с ошибками и без, со степенями
схожести 2 и ниже.
Исходное слово: "Иннокентий"
6, Аксентий
6, Викентий
5, Дементий
5, Лаврентий
5, Леонтий
4, Анатолий
4, Андроник
4, Валентин
4, Валентина
4, Влентин
4, Енок
3, ...
... ниже еще более тысячи имен, набранных с ошибками и без, со степенями
схожести 3 и ниже.
самого слова "иннокентий" в базе не оказалось
Забавно, но используя такой метод поиска выяснил что при вводе в эту БД
операторы довольно таки часто ошибались. Вариантов написания имени
"Александр" я обнаружил больше пяти (из вышеуказанных примеров я их
повыкусил):
Исходное слово: "Александр"
9, Алеександр
9, Алексаендр
9, Александдр
9, Александр
9, Александра
9, Александро
9, Александрови
9, Алексанндр
8, Влександр
7, Алексанлр
7, Алексанр
6, Алаксандр
6, Алексадр
5, Алекасндр
5, Алексеев
5, ...
Если кому интересно могу кинуть в конфу исходники. Комментарии, критика,
ссылки на литературу с подобной тематикой? Welcome.
P.S. Самое интересное, что этот метод может стать отправной точкой для
реализации более гибкого алгоритма "сравнения похожести", подобного
реализуемым в спеллчекерах от Орфо (AFAIK, они никому их раздавать за просто
так не будут), с помощью нейросети (простейшей) к тому же обучаемой во время
реальной работы. Как это сделать я примерно представляю, только вот
реализация будет посложнее, а не как в этом - 56 строк с комментариями
включительно.
--
Andrew V. Fionik, software developer
laboratory of criminalistic technology SONDA
Д RU.DELPHI.DB (2:5000/130.53) ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД RU.DELPHI.DB Д
Msg : 15 of 36
From : Igor Semenovskiy 2:5020/400 04 Aug 00 18:53:06## To : All 06 Aug 00 14:44:58
Subj : Re: DX. Правильное заполнение справочников или метод параметрической ко
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
From: Igor Semenovskiy <igors@karelia.ru>
Subject: Re: DX. Правильное заполнение справочников или метод параметрической
корреляции - SoundEx
> Таким образом встает задача - найти в справочнике слова, похожие на
> введенное и отсутствующее в справочнике, и предложить пользователю
> выбрать
> одно из них. Вопрос в том, как определить похожие слова? Есть алгоритм
> SoundEx (http://physics.nist.gov/cuu/Reference/soundex.html), который
> кодирует каждое слово определенным образом. Говорят что коды потом можно
> сравнивать. Сравнив введенное слово по очереди с каждым элементовм
> справочника получим возможность определить похожесть слов. У этого
> алгоритма
> есть недостатки: работает только по ограниченному набору букв,
> языкозависим
> (где взять таблицу кодирования для русского языка я не знаю, а для
> прочих и
> подавно) неустойчив к ошибкам первой буквы (что встречается довольно
> часто).
Кстати, если кого интересует алгоритм SoundEx, точнее его конечная реализация,
могу выслать.
Эта штука была в свое время в Turbo Professional для Pascal'я (...и тут
нахлынули ностальгические воспоминания...), есть ли она там сейчас - не знаю.
Была она опять же под английский набор символов. Hо оказалось что подружить ее
с
русским - никаких проблем.
Смысл в том, что для многих букв можно найти пару по звучанию: з-с, м-н, б-п и
т.д. Hа основе этого слово обрабатывается по определенному алгоритму и
получается его код из четырех символов, если у другого слова получим такой же
код, то можно с определенной долей уверенности говорить о том, что это одно и
тоже слово, набранное с ошибкой:
"конференция" - К686, а для слова "канфиренция" - тоже К686, пробуем дальше:
канфаренция - К686
кунфуренция - К686.
По моему, не плохо !
Да, у этого алгоритма большой минус - ошибка в первой букве:
ганфиренция - Г686
гангиренция - Г626.
По всей видимости, у алгоритма есть издержки - сочитаний из 5-6 символов
намного
больше, чем сочетаний цифр в трехзначном числе, а именно так получается в
данном
случае - все слова, в конечном итоге, представляются первой буквой и
трехзначным
сочетанием цифр. Hо, я подозреваю, что длину кода можно увеличить...
Каков сам алгоритм - сказать не могу, написан он на ассемблере, правда всего в
40 строк, но разбираться не было желания, добавил только русские символы.
Hе хочу никого агитировать, т.к. сам им не пользовался и насколько он практичен
в работе не знаю.
С уважением,
Игорь С.
--- Alex Raider / Flash inc.
* Origin: Alex Raider/ Flash inc. 1992-2001 (2:5000/228.16)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
