Конструктор шаблона подобия для строк

Опубликовал Ярослав Волохов (YVolohov) в раздел Программирование - Практика программирования

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

 

Если бы удалось их этому научить, был бы сделан грандиозный прорыв в сфере информационных технологий. Например, интеллектуальная камера на улице могла бы выделить из толпы людей разыскиваемого преступника, сравнив лицо с образцом в базе данных. Интеллектуальный замок мог бы впустить владельца в квартиру или автомобиль, просто сравнив образцы голоса.
Сейчас существует множество алгоритмов для определения похожести различных сущностей, но в большинстве случаев или они слишком несовершенны или же сравниваемые сущности очень просты. 
В языке запросов 1С существует конструкция ПОДОБНО, которая дает возможность проверить подобие строки некоторому шаблону. 
Представленный алгоритм делает обратное. Он сравнивает два слова и создает на их основании шаблон подобия, заменяя различающиеся фрагменты звездочками. К сожалению для решения типичных задач 1С он не применим, зато будет интересен программистам, интересующимися нетривиальными задачами и алгоритмами вообще.

 

Скачать файлы

Наименование Файл Версия Размер
Конструктор шаблонов.epf
.epf 8,97Kb
17.08.10
35
.epf 8,97Kb 35 Скачать бесплатно

См. также

Комментарии
1. Аркадий Кучер (Abadonna) 3667 18.08.10 06:04 Сейчас в теме
(0) Пример несколько неудачный, ибо нет слова "разискивать", а есть слово "разыскивать" ;) Как иллюстрация работы пойдет, как иллюстрация русского языка - ну уж никак
2. Сергей Троицкий (tsd) 147 18.08.10 06:49 Сейчас в теме
(0)(1) Вы не поверите, но распознавание морды лица уже есть. И интеллектуальные камеры (правда это и не камеры вовсе, а все-таки некое ПО) таки пытаются их различить и выделить из толпы разыскиваемого преступника. Правда это пока экспериментальные разработки, но в Москве и Питере их время от времени на вокзалах запускают.
3. Ярослав Волохов (YVolohov) 698 18.08.10 07:00 Сейчас в теме
(1) Согласен :) сейчас поменяю.
(2) В том то и дело, что экспериментальные. На хабре была занятная статья о тестировании подобной системы http://habrahabr.ru/blogs/infosecurity/101692/
4. Аркадий Кучер (Abadonna) 3667 18.08.10 07:41 Сейчас в теме
(3) Плюсик на на (3) за адекватную реакцию ;)
5. Александр Цегельников (markers) 186 19.08.10 20:32 Сейчас в теме
(0) А почему не применим???? меняем * на % и юзаем в запросе с ПОДОБНО
пример:
Сущьность = "%ск%в%";
Запрос = Новый Запрос;
Запрос.Текст = "ВЫБРАТЬ
               |	Покупки.Ссылка
               |ИЗ
               |	Справочник.Покупки КАК Покупки
               |ГДЕ
               |	Покупки.Наименование ПОДОБНО &Покупка";
Запрос.УстановитьПараметр("Покупка", Сущьность);
Выборка = Запрос.Выполнить().Выбрать();
Пока Выборка.Следующий() Цикл 
	...
КонецЦикла;
...Показать Скрыть
6. Ярослав Волохов (YVolohov) 698 19.08.10 21:34 Сейчас в теме
(5) Хорошо если кому-то пригодиться. А то алгоритм очень интересный, корректно обрабатывает все возможные ситуации, жалко если будет просто припадать пылью.
Писал эту программку чисто ради интереса. Захотелось переложить на плечи компьютера "человеческую" задачу по выделению общей составляющей из двух строк. Человек с таким справляется на ура, а для компьютера это уже задача.
7. Артур Аюханов (artbear) 859 20.08.10 15:34 Сейчас в теме
(5) (6) Берем Сущьность = "%ск%в%" ну или "*ск*в*"
Проверяем слова Москва или Москьва :).
Ну, что очень похоже на сабжевые слова?
А ведь будет найдено :)
8. Ярослав Волохов (YVolohov) 698 20.08.10 19:37 Сейчас в теме
(7) Для этих двух слов общий шаблон будет "Моск*ва", на месте звездочки может быть сколько угодно символов, в том числе и ни одного.
9. Артур Аюханов (artbear) 859 21.08.10 09:59 Сейчас в теме
(7) Ты не понял :(
Я беру твой исходный шаблон по двум твоим словам с картинки и проверяю слова Москва или Москьва, твой код их обозначит как подходящий, хотя никакого сходства на самом деле нет.
10. Ярослав Волохов (YVolohov) 698 21.08.10 11:09 Сейчас в теме
(9) Между строками "*ск*в*", "Москва" сходство есть [*|Мо]ск[*|]в[*|а]
между строками "*ск*в*", "Москьва" соответственно [*|Мо]ск[*|ь]в[*|а]

Задача программы не проверить слово на соответствие шаблону а создать шаблон из двух слов, выделив общие для обеих части и заменив звездочками все, что не совпадает. Если снять флажок "Простое представление", вместо звездочек будет конструкция типа [часть первого слова|часть второго слова].

Тогда шаблон будет выглядеть так:
... [часть первого слова|часть второго слова]общая для обеих слов часть[часть первого слова|часть второго слова]общая для обеих слов часть ...

например для слов "солнце" и "солнечный" будет построен шаблон "солн[ц|]е[|чный]" или при простом представлении "солн*е*"
Оставьте свое сообщение