Анекдотическое
16 Jul 2008 15:46![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
kondybas
Если кто помнит, в НИИЧАВО была славная когорта сотрудников, бравших отпуска, длительностью в бесконечность, красовавшаяся исцарапанными от бритья ушами, и утомлявшая коллег анекдотами о теореме Лопиталя. Я, к сожалению (или к счастью) ни одного такого анекдота не знаю, но зато я знаю много рецептов приготовления теоремы Лопиталя в домашних условиях. Хочу поделиться одним из них.
Теорема Лопиталя, если кто забыл, гласит, что отношение двух функций равно отношению их производных, и часто используется там, где сравнить две функции напрямую невозможно. Например, часто бывает необходимо сравнивать логины, выбираемые пользователями, для того, чтобы обеспечить их уникальность. Простое побайтное сравнение строк позволяет отличить только байтовое представление строк, но бывают проблемы с различением собственно начертания строк. Скажем, два имени пользователя, набранные кириллицей и латиницей могут визуально совпадать до неотличимости. Например, логин СТЕПАН может быть составлен 32-мя побайтно-различными способами, которые визуально будут идентичны.
Разумеется, это может приводить к очень плохим последствиям, если под видом одного пользователя будет работать двойник. Но, к счастью, эту проблему легко побороть. Нужно лишь сравнивать не сами строки, а их производные.
Первой производной от строки можно считать приведение всех символов к одному регистру.
Второй производной - табличную замену символов в латиницу с учетом начертания/произношения:
исходный символ: ABCDEFGHIJKLMNOPQRSTUVWXYZАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ результирующий: ABCDEFGHIJKLMNOPQRSTUVWXYZABBHDEEGZIJKLMHOPPCTYFHCCSSZYZEUJСпецифичные символы можно заменять на любой латинский - это непринципиально.
Третьей производной можно считать упрощение дифтонгов, вроде
th=Z, дж=G, cz=Z, фф=F, цц=тс=тьс=Z и так далее.
Если мы получаем на вход некоторую строку, мы последовательно берем от нее первую(регистровую) производную, затем вторую(графическую/фонетическую), третью(ди/трифтонговую) и получаем некоторую строку, которая уже неплохо пригодна для побайтного сравнения с образцами из базы.
Например, любое написание слова, извините, XYJ будет приводить к совпадению с шаблоном из базы - со всеми вытекающими.
Разумеется, механизм достаточно накладен в вычислительном отношении, но бывают случаи, когда это - не главное.
Вот, собственно, и все. Если кому пригодится - не забудьте помянуть в титрах.
Упд.
Поскольку народ хочет уточнений, уточняю: для некоммерческого использования достаточно упоминания в титрах, а для коммерческого - уже в платежной ведомости :)
(no subject)
Date: 16 Jul 2008 13:25 (UTC)(no subject)
Date: 16 Jul 2008 13:35 (UTC)(no subject)
Date: 16 Jul 2008 13:44 (UTC)Наш ответ Чемберлену
Date: 16 Jul 2008 13:49 (UTC)Знавал я одного профессора, Франтишека Лавичку, дед его был известным конокрадом из Опавы. Попал он раз на ферму и увидел, как крестьяне стригут овец. Удивлению его не было меры. «Это зачем же действовать в этой сфере дедовскими методами, тратить уйму времени и труда, если на помощь простым людям может прийти наука», – были его слова. Неделю не выходил он из своего рабочего кабинета, а когда вышел, то помчался в академию наук бегом по улицах как Архимед. Голос его разносился по всем Градчанам: «Нашёл, нашёл!!!».
В самой уже академии он показал учёным мужам своё изобретение. Это был эликсир, при натирании которым вся шерсть у овец выпадала сама в кратчайшие строки. Но академики прорыва в науке не поняли и под предлогом проехать на пролётке в патентное бюро для регистрации изобретения завезли его в психушку.
А всё потому так скверно вышло, господин поручик, что надо было с умом подойти к презентации открытия. Неужто жалко было ему подарить по пузырьку эликсира каждому академику, чтобы их жёны дома, извиняюсь, волосики под мышками выводили? Вот к чему приводит слишком заумные объяснения!
Re: Наш ответ Чемберлену
Date: 16 Jul 2008 13:53 (UTC)Я так думаю, что кому надо - тот поймет. А кто не поймет - так и не очень-то и надо :) Опять же, я далеко, на дуровозе меня покатать сложновато будет :)
Re: Наш ответ Чемберлену
Date: 16 Jul 2008 13:55 (UTC)(no subject)
Date: 16 Jul 2008 14:08 (UTC)Производная в первую очередь характеризует скорость изменения функции, а символы ж тупо константы )
(no subject)
Date: 16 Jul 2008 15:04 (UTC)(no subject)
Date: 16 Jul 2008 16:12 (UTC)Символы - не константы. Строка - это функция, заданная на интервале таблично. Попробуй с этой стороны посмотреть ;)
(no subject)
Date: 16 Jul 2008 16:25 (UTC)Если по существу, то предлагаемый механизм позволяет определить, что КОНДЫБАС, кондыбас, kondybas и даже k0Hdb1Баs - суть одно и то же, но по-разному написанное. Фишка в том, что для подобного вывода совершенно не нужен семантический анализ, тупые табличные преобразования рулят.
(no subject)
Date: 16 Jul 2008 16:30 (UTC)Re: Наш ответ Чемберлену
Date: 16 Jul 2008 16:34 (UTC)(no subject)
Date: 16 Jul 2008 16:37 (UTC)(no subject)
Date: 16 Jul 2008 16:48 (UTC)Re: Наш ответ Чемберлену
Date: 16 Jul 2008 16:49 (UTC)(no subject)
Date: 16 Jul 2008 16:56 (UTC)Re: Наш ответ Чемберлену
Date: 16 Jul 2008 18:59 (UTC)Re: Наш ответ Чемберлену
Date: 16 Jul 2008 19:14 (UTC)Re: Наш ответ Чемберлену
Date: 16 Jul 2008 19:49 (UTC)(no subject)
Date: 16 Jul 2008 21:28 (UTC)(no subject)
Date: 16 Jul 2008 22:35 (UTC)Re: Наш ответ Чемберлену
Date: 17 Jul 2008 04:48 (UTC)(no subject)
Date: 17 Jul 2008 04:48 (UTC)(no subject)
Date: 21 Jul 2008 14:09 (UTC)Очень познавательно
Date: 3 Feb 2011 08:56 (UTC)