Анекдотическое

[kondybas]

Если кто помнит, в НИИЧАВО была славная когорта сотрудников, бравших отпуска, длительностью в бесконечность, красовавшаяся исцарапанными от бритья ушами, и утомлявшая коллег анекдотами о теореме Лопиталя. Я, к сожалению (или к счастью) ни одного такого анекдота не знаю, но зато я знаю много рецептов приготовления теоремы Лопиталя в домашних условиях. Хочу поделиться одним из них.

Теорема Лопиталя, если кто забыл, гласит, что отношение двух функций равно отношению их производных, и часто используется там, где сравнить две функции напрямую невозможно. Например, часто бывает необходимо сравнивать логины, выбираемые пользователями, для того, чтобы обеспечить их уникальность. Простое побайтное сравнение строк позволяет отличить только байтовое представление строк, но бывают проблемы с различением собственно начертания строк. Скажем, два имени пользователя, набранные кириллицей и латиницей могут визуально совпадать до неотличимости. Например, логин СТЕПАН может быть составлен 32-мя побайтно-различными способами, которые визуально будут идентичны.

Разумеется, это может приводить к очень плохим последствиям, если под видом одного пользователя будет работать двойник. Но, к счастью, эту проблему легко побороть. Нужно лишь сравнивать не сами строки, а их производные.

Первой производной от строки можно считать приведение всех символов к одному регистру.
Второй производной - табличную замену символов в латиницу с учетом начертания/произношения:

исходный символ: ABCDEFGHIJKLMNOPQRSTUVWXYZАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
результирующий:  ABCDEFGHIJKLMNOPQRSTUVWXYZABBHDEEGZIJKLMHOPPCTYFHCCSSZYZEUJ

Специфичные символы можно заменять на любой латинский - это непринципиально.

Третьей производной можно считать упрощение дифтонгов, вроде
th=Z, дж=G, cz=Z, фф=F, цц=тс=тьс=Z и так далее.

Если мы получаем на вход некоторую строку, мы последовательно берем от нее первую(регистровую) производную, затем вторую(графическую/фонетическую), третью(ди/трифтонговую) и получаем некоторую строку, которая уже неплохо пригодна для побайтного сравнения с образцами из базы.

Например, любое написание слова, извините, XYJ будет приводить к совпадению с шаблоном из базы - со всеми вытекающими.

Разумеется, механизм достаточно накладен в вычислительном отношении, но бывают случаи, когда это - не главное.

Вот, собственно, и все. Если кому пригодится - не забудьте помянуть в титрах.

Упд.
Поскольку народ хочет уточнений, уточняю: для некоммерческого использования достаточно упоминания в титрах, а для коммерческого - уже в платежной ведомости :)

Comments

[kondybas.livejournal.com]

Лейбниц-ньютоновская производная - возможно. Но аналитические функции - не единственные возможные, а производная по переменной - не единственная допустимая.

Символы - не константы. Строка - это функция, заданная на интервале таблично. Попробуй с этой стороны посмотреть ;)

[yuriyi.livejournal.com]

технично.

[bluesbreaker.livejournal.com]

Для dF(x)/dx Лопиталя работает, а для прочих? Не в курсе.

[kondybas.livejournal.com]

Ну, как видим, таблично заданная производная для таблично заданной функции позволяет неплохо разрешать неопределенности ;)

[bluesbreaker.livejournal.com]

:D