gifts2017

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

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

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

 

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

 

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

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

См. также

Подписаться Добавить вознаграждение

Комментарии

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

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

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

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