пятница, 28 мая 2010 г.

As fuzzy as you can

В 1998 году я случайно нашел заметку про Soundex. Меня до глубины души поразила простота алгоритма и то, что его придумали ещё в начале 20-го века, когда и компьютеров-то не было. Захотелось как-то его применить.

И я как раз нашел работу в фирме, где не помешал бы нечеткий поиск. Мы занимались обучением по переписке. Особенность процесса состояла в том, что часто приходилось искать клиентов по имени и фамилии, а не по уникальному номеру. Опечатки и описки - это пол-беды. Главная проблема была в том, что один и тот же клиент мог иногда писать свое имя по-русски, а иногда по-украински. К сожалению, Soundex хорошо работал только с английским языком.

Но нечёткий поиск продолжал меня манить. В 1999 году я писал систему по обработке газетных объявлений и сделал простой полнотекстовый индекс: сгенерировал словарь популярных слов c указателямм на соответствующие объявления. В идеале нужно было находить объявления с похожим текстом: мошенники-бизнесмены давали бесплатные объявления под видом частных лиц. Но в те времена это казалось почти нереальным. Про Google тогда ещё никто не знал. Мы делали проще - отлавливали злодеев по телефонным номерам. Мобильных тогда почти не было, поэтому сменить номер было сложно.

Интересный проект у меня намечался в банке. Один большой и очень блатной клиент требовал, чтобы банк группировка входящие (или, как их принято называть "ответные") платежи по их предназначению. Имелось в виду не группировка по формальным признакам вроде даты, номера счета или суммы, а именно нечёткий анализ текста с назначением платежа. Я с радостью взялся за дело, но мой начальник передумал: хоть моя зарплата на тот момент была маленькая, но операционистки получали ещё меньше; не было смысла тратить несколько месяцев моего времени на создание сложного софта, если эту же работу легко и гораздо качественнее может делать человек. Поэтому в результате я просто сделал маленькую программку, в которой операционистка могла группировать платежи перед отправкой клиенту.

Кстати, прошло совсем немного времени, и клиент сказал: "Я передумал, шлите мне все платежи, а я сам разберусь". В общем, это логично. Это не работа банка - разбираться в чужих платежах и особенностях ведения клиентского бизнеса. Кстати, робкая операционистка мне ничего не сказала. И только через несколько лет я случайно увидел, что она по-прежнему каждый день вручную добавляет каждый платеж в группу "Все платежи". Узнав об этом, я тут же добавил кнопку "Добавить все" и сэкономил бедной женщине несколько сотен кликов в день :)

Вторая интересная задачка называлась "Дебиторы-Кредиторы". Допустим, банк перечислил деньги на покупку канцтоваров - возникла дебиторка. Потом канцтовары пришли на склад - дебиторка погасилась. Кредиторка - это наоборот. Например, сначала клиент заплатил за выдачу пропуска. И только через несколько дней мы выдаем пропуск, т.е. выполняем свои обязательства. Национальный банк это дело сильно контролировал, особенно дебиторскую задолженность. Потому что иначе банки могли бы давать скрытые кредиты. Заплатили Васе Пупкину миллион за строительство нового офиса, а он через год возвращает эти деньги и говорит: "Извините, не получилось построить". На самом деле он ничего не строил, а крутил этими деньгами, и проценты как бы не платил (конечно, при этом Вася щедро благодарит руководство банка).

Часто возникновение и погашение задолженности можно было сопоставить по сумме. Но даже в этом случае вопросы оставались, потому что иногда бывали совершенно разные задолженности, но на одну сумму. А ещё нередко бывало, что суммы не совпадали. Например, мы заплатили за строительство, но оно продолжается год; каждый месяц акт выполненных работ частично погашает дебиторскую задолженность. Или наоборот: целую неделю разные клиенты платят за выдачу им пропусков, а потом вся это кредиторская задолженность гасится одной проводкой.

Короче, накрутил я кучу бизнес-правил, но в результате всё это так и не заработало. Как и предыдущем случае, корень зла был в неправильной постановке задачи. На самом деле никакая нечёткая логика для "Дебиторов-Кредиторов" не нужна. А нужна система для управления хозяйственными операциями банка, которая и будет генерировать проводки. Всё должно начинаться с операций, а не с проводок.


И вот, наконец, мои "нечёткие мечты" сбываются. Большой проект, в основном связанный с нечетким поиском текста. Если всё получится, то с гордостью буду показывать друзьям одно текстовое поле с кнопкой "Поиск" и говорить: "Вот этим я занимался полгода". В принципе, у нас уже был похожий проект, и всё нормально работало, но... там была база с несколькими тысячами записей, а у меня будет несколько миллионов. Те алгоритмы, которые есть, использовать невозможно. Причем не только из-за проблем с производительностью. Природа данных меняется, и нужны совсем другие правила для определения релевантности.

А в функциональной спецификации было сказано просто: "Для этого проекта необходим нечёткий поиск - точно такой же, как сейчас". Но "точно такой же" сделать невозможно. Прошла куча кучи совещаний, где я рассказывал о преимуществах и недостатках Jaccard index, Damerau–Levenshtein distance, nGrams, NYSIIS, Double Metaphone, SQL Full-Text Search, Lucene и пр. Мы долго спорили, в концев у менеджеров опухли головы и они сказали: "Короче, это... сделай как-нибудь получше... be as fuzzy as you can" (будь как можно более нечётким).

Трудно сформулировать чёткие требования к нечёткому поиску. Когда я начинал проект, то думал, что главная проблема - производительность. Оказывается, основная сложность не в том, как это сделать, а в том, что же именно надо сделать. Пожалуй, это мой первый проект, где гораздо больше времени уходит на написание спецификации, а не на программирование. Сами по себе алгоритмы давно известны и реализованы; загвоздка в том, какие именно из них, и в какой последовательности применить.

Комментариев нет:

Ratings by outbrain