На днях сделал пару страшных вещей - собрал модули для PHP и Perl.
Немного по порядку и за жизнь...

Началось все это со сравнения строк. Строки - это очень страшные вещи на самом деле. Правда чтобы это понять, сначала надо вспомнить про обычные числа.
Вот все знают, что 2+2=4. И 4=4, а 5!=4. Сравнивать целые числы одно удовольствие.

Хотя сравнения целых чисел тоже хранят опасности:

short i = 0;
int max=1000000;
while(i<max) {
 i++;
}

зависает в бесконечном цикле.
но это к теме не относится.

А вот когда появляются вещественные числа, то становится интереснее.

#define PI 3.1415926548
if(sin(PI/2) == sqrt(2) / 2) {...}

В общем случае синус пи-пополам не равен корню-из-двух-на-два. Почему? Из за неизбешных округление вещественных чисел в компе. Можно повышать разрядность (double - 32 битный), но никогда они не сравняются.
Да и что там...

sqrt(2) == sqrt(2)

В общем случае не равны!
Так же не советую сравнивать вещественное с целым

sqrt(2) * sqrt(2) == 2

Вот значит...
А сравнивать вещественные числа надо.
Отдельно от компьютеров жила-была теория эксперимента, погрешностей и всякого разного. Там уж точно научились сравнивать числа.
Принцип такой - если разница между двумя числами меньше определеного числа эпсилон, то числа равны. Еще точнее - модуль разницы. Ну и эпсилон тоже по модулю можно писать.
|a-b| < |ε|
Остается пробелема - как выбрать ε? Тут уже ничем не поможешь - надо оценивать свои расчеты и решить какой ε нам подойдет. Где-то хватит и 0.01. Где-то и 0.00001 мало.
Оказывается формула такая крутая, что легко переносится на другие случаи.
Допустим нам надо сравнить два комплексных числа. С комплексными числами такая штука, что для них не существует операций "больше" и "меньше". Только равенство. Но про равенство мы уже убедились выше.
А вот модуль для комплексных чисел возвращает обычное вещественное число, которое уже можно сравнивать. Это кстати очень важная аналогия!
Тут конечно мои знания алгебры групп слабоваты, так что я не могу гарантировать, что эта формула будет всегда верна.

Теперь, когда мы что-то поняли в сравнении чисел можно поговорить про строки. До этого мы работали с цифрами - и там было все просто с арифметикой. Но можно ли вычитать буквы? С одной стороны в компе строки - это набор битов и есть ASCII таблица. Далее строку можно рассматривать как n-мерный вектор кодов, где n-длина строки. Можно даже начать строить векторную алгебру на этом но...
Как обычно сначала кажется, что все просто. Сравним строку по символьно. "Mama"=="Mama" - все просто. Да. Просто. Прямо как с целыми числами.
Хотя даже "в лоб" сравнить строки - это не так-то просто. Ну например немецкий язык (не самый экзотический): ß равно ss, ä равно ae. В русском языке так же часто не пишут точки над ё. А если строки в разные кодировках?
А теперь вылазим из "целых строк" на "вещественные".
Сравним-ка:
[list]
[*]re-hash и re hash
[*]The One и One, The
[*]Address и Adress
[*]Мама и Mama (русская и английская раскладка)
[list]
пунктуация, символы, возня с артиклями, опечатки, похожие буквы, диакритические знаки - строки уже не равны в прежнем смысле. Но! Как в эксперименте естm погрешность, так почему со строками мы не можем сказать, что строки равны с погрешностью? От опечаток в базах никуда не денешься, а поиск должен максимально эффективным.

Поэтому мы снова вспоминмаем формулу:
|a-b| < |ε|

Итак нам надо вычесть строки, найти у строки модуль и сравнить строки. Это в общем случае.
Сравнивать легче всего цифры. Так что надо превратить буквы в цифры...

Это можно сделать примерно двумя способами. Первый - превратить строку в цифру. Грубо говоря, вычислить некий хэш. Второй способ - это придумать вычитание, которое возвращает хэш.
В качестве первого способа (вспоминаем ASCII) можно придумать усредненный код символа в строке. Или модуль в векторном смысле. Правда оба эти способа скажут, что строки abcdef и fedcba равны. И много других сюрпризов. Нормального хэширования строк я так и не нашел. Все таки строки - это многомерные вектора (ср. с вещественными числами, которые можно считать одномерными векторами и с комплексными - двумерными векторами). Они еще к тому же и переменной размерности! Да даже и для одномерных не понятно как сравнить a и b и a и x.
Так что для строк надо придумать разницу. Операцию вычитания. А эта штука уже есть. И придумал её дядька Левенштейн. Есть еще другие способы вычитания строк (например Левенштей-Дамерау), но Левенштейн сидит во многих.
Итак, что есть разница строк по Левенштейну?
Минимальное количество операций вставки, замены и удаления символов, которые требуются, чтобы превратить строку 1 в строку 2.
Например: re-hash - rehash = 1, moloko - mlk = 3, moloko- mlooko = 2 и.т.д.
Часто Левенштейна дополняют Дамерау, в котором перестановка занимает одну операцию, а не две: moloko - mlooko = 1
И еще, что часто делают - это весовые коэффициэнты для операций. Например мы можем считать замену большим злом чем вставка и счтать её за две операции. Или за 1.5. Так же мы можем глянуть на клавиатуру и увидеть, что s и d ближе к друг другу чем s и p. В русском тексте мы также можем считать, что о часто заменяется на а. Присваеваем таким заменам меньшую стоимость и тогда молоко и малако будует еще ближе.

Ура-ура! Мы научились вычитать строки! Теперь осталось понять сколько ε нас утроит как погрешность и вперед в поиску в базе. Правда со стороками еще надо подумать какую функцию вычитания писать. Можно свои условия добавить. Например, чтобы разница у апельсин и яблоко и апльсин была равная 1 (поиск максимальной подстроки). Вобщем перед тем как вычитать строки нужно придумать лучшую функцию для своей задачи.

А раз мы научились вычитать строки, то сравнивать их и подавно.

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

А так это все используется в проверке орфографии, всяких поисковиках, утилитке diff/windiff и agrep...

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

Вобщем пришлось думать, как сравнить строки без умляутов. А еще и без регистра. А еще чтобы русская и английская a были равны?
Ну "думать" - это громко было сказано. Решение я знал. А вот реализовать...
Сначала простой пример. Как сравнить, что слово равно "the" без учета регистра? Неумный программист вспомнит комбинаторику и родит что-то вроде этого: s=="THE", s == "tHE", s == "THe" (кстати, не сравнивайте строки в C при помощи ==), .... Если надо сравнить две строки, то можно помереть.
Умный-же программист преобразует первую строку в нижний регистра, а потом обойдется одним сравнением: strtolower(s) == "the". То есть мы избавляемя от неоднозначностей в строках, а потом уже сравниваем их.
Значит мне надо превратить Ç в C, превратить лигатуры типа æ в ae, кирилицу превратить в транслит, убить регистр и еще убить все кроме цифр и букв (решил таким способом).

И вот когда я уже думал, что придется убить пару дней, на составление таблицы соответсвий я набрел на один перловый скрипт, а от него на сайт unicode.org где я узнал про декомпозицию... Оказывается для кучи символов - те которые с диакритическими знаками и для лигатур есть правили декомпозиции. Умляут можно отделить от буквы и хранить отдельным символом. И любой обработчик Юникода прицепит умляют куда ему надо. Так, кстати, можно создавать экзотические буквы. Которые вряд ли когда будут в Юникоде. Например вот такая странная буква: [Н̣̃]
И решил я тогда найти библиотечку для декомпозиции. Чтобы декомпозировать, а потом выбросить лишние символы. Но... библиотеку, чтобы легко подрубить к своему проекту я не нашел, а стандартная виндовозная требовала доп. библиотек К тому же по стандарту не все декомпозируется как надо для моих нужд.
Но! На сайте юникода в свободном доступе лежат таблицы декомпозиции. Осталось только загнать их в мою программу и добавить нужные мне правила. Например транслит кириллицы туда же. В итоге все решилось в виде статического массива из 60 тысяч строк, который занимает где-то 300 кило в памяти. Но зато поиск в нем макимально быстрый, ибо тут просто тупой доступ к памяти (а скорость мне была нужна - об этом позже). Выигрываешь в скорости - проигрываешь в памяти.
Дело осталось за малым. Уметь из строки в UTF-8 вытаскивать отдельные буквы (а они могуть быть 1-8 байтовыми!), получить из буквы код символа и вытащить из таблицы правильную замену. В итоге у меня получилась не замена, а конктруктировка новой строки из мелких кусков. Не-буквы-цифры я просто не включил таблицу и они спокойно исчезли.
Для UTF-8 быстро были найдены готовые реализации через Google Codesearch.

Итак. У меня была строка без лишних символов. (А еще я вырезал артикли - это не сложно). Есть Левенштейн. ε я взял как четверть от максимальной строки + 1.
И с этими данными процесс пошел. Поиск работал очень неплохо. Сложная часть была позади - если надо добавить что-то в таблицу декомпозиции или подправить сравнение строк, то там уже чисто правка кода и ничего сложного.
В итоге я взял мою базу в SQLite 3 и стал думать как теперь сделать поиск по базе... Оказалось все просто - SQLite 3 можно создать свою функцию и SQL движок будет её использовать. Причем функция пишется не на SQL, а на Perl/PHP/C - смотря где пишешь. Так что вся мощь языка в твоих руках.
Как обычно сначала я начал с Perl-а:

Загнал я в Perl Левенштейна и обрезалку лишних цифр. Определил пару функций для SQLite и родился вот такой запрос:
...WHERE DISTANCE(MYHASH(tbl_name), MYHASH('Молоко')) < 2...
Он отробатал грамотно. Но... медленно! Пару минут.
А все из за того, что в базе лежало 600 000 строк. Даже если на операцию уходит 1/1000 секунды, то имеем 10 минут на всю базу. А стандартный LIKE обходит всю базу за несколько секунд.
Пришлось садится за оптимизацию. Во-первых надо MYHASH('Молоко') считать не каждый раз в запросе, а всего один раз перед начало. А MYHASH(tbl_name) лучше закэшировать в базе. Сначала я это дело скэшировал в отдельной таблице, но JOIN между стотысячными таблицами тормозил тоже не хило, так что в итоге пришлось в исходной таблице делать доп. колонки для кэша хэшей. Написал отдельную программку для просмотра базы и создания хэшей. За минуту хэши были готовы. Правда если что-то менять, то надо руками пересоздать хэши. Но это не беда совсем.
Но даже после этого скорость меня не устроила.
Я понял, что придется писать на С
На С все написалось так же быстро. И вот C работал с удовлетворяющей меня скоростью. Стало понятно, что самое страшное позади. Пока остановимся тут, а потом, если будут мысли по оптимизации, то будем дописывать код. Еще Левенштейна доработал, чтобы отсекать некоторые строки на раннем этапе (например "a" и "gfkgkfgjkfjgf" можно сразу вернуть 0, а не ждать).
Но на Perl-е решать ситуацию тоже надо. Ибо на нем быстро пишутся мелкие скрипты и просто удобно. Задача встала, чтобы откомпиленную библиотеку подключить как модуль Perl-а. Благо, что интерфейс - Perl-XS для этого есть. И хелп толковый в комплекте. И в интернете.
Еще ситуация была в том, что я это все делал под Win32. А OpenSource/GNU как-то не очень дружит с Win32. Хотя у меня еще была mingWW, с которой у меня получалось собирать.
Но с Perl-ом оказалось все проще. Ибо у меня стоит не ручная сборка из исходников, а ActiveState Perl заточеный под винду и MSVC. Все утилиты из туториала работали как надо и я спокойно сделал из C-программки модуль для Perl-а ничего не меняя в своих исходниках, а только добавив обертку для Perl-а.
И произошло чудо! Модуль заробатл даже без пол-пинка и скорость заметно возрасла до хороших пределов.

А вот если бы я собирал Perl из исходников, то он был бы заточен под другой компилятор. Может и под MinGW, если им собрать.

PHP мне понадобился для веб-интерфейса к базе. C PHP было чуток сложнее. А точнее с документацией, в которой про модули к Win32 было нифига не сказано. Зато PHP тоже заточен по MSVC на Win32 системах. Сначала, по книжке, я создал болванку модуля. Добавил свой код, обертку и решил действовать дальше по книжку. Тут меня ждал облом ибо не хватало программок. Пришлось компилить PHP, что мне удалось только если отрубить пару библиотек. И даже после этого и с мучением через minGW нифига не вышло по книжке. В итоге откопал что-то в инете про Win32, удалил все кроме модуля и обертки. В итоге оно собралось! И спокойно заработало в PHP как модуль. Оказалось все намного проще.
Ну и написав текствый скрипт я убедился, что все работает.

Вот такая погоня за скоростью. Теперь можно это использовать в работе. Иногда добавляя что-нибудь в C-код. Еще неплохо бы написать скрипт, который компилит все три библиотеки сразу, чтобы не бегать по папкам и запускать.