Реализация нечеткого поиска



    Если ваш веб проект так или иначе будет связан с поиском и предоставлением пользователям некоторых данных, то перед вами наверняка встанет задача реализации строки поиска. При этом, если в проекте по какой-либо причине не удастся использовать технологии умных сервисов как Google или Яндекс, то поиск частично или полностью придется реализовать самостоятельно. Одной из подзадач наверняка будет реализация нечеткого поиска, ведь пользователи часто ошибаются и иногда не знают точных терминов, названий или имен.

    В данной статье описывается возможная реализация нечеткого поиска, которая была применена для поиска на сайте edatuda.ru.

    Задача
    В рамках создания сервиса нашего по поиску ресторанов, кафе и баров возникла задача по реализации строки поиска, в которой пользователи могли бы указывать названия интересующих их заведений.
    Задача ставилась следующим образом:
    1. Результаты поиска должны выводиться в процессе набора в выпадающем списке.
    2. Поиск должен учитывать возможные ошибки и опечатки пользователей (например mcdonalds так и хочется набрать как macdonalds).
    3. Для каждого заведения должна быть возможность задавать множество синонимов (например mcdonalds => макдак).

    Визуальное представление пунктов 1-3:



    Таким образом, получив фразу запроса, скорее всего обрезанную, нужно выбрать из заранее собранного словаря наиболее близкие по написанию записи. По сути задача сводилась к исправлению опечаток, которое умеют выполнять современные поисковые системы. Одни из распространенных методов ее решения:
    1. Метод, основанный на построении n-граммного индекса.
      Неплохой, простой и быстрый метод.
    2. Метод, основанный на расстоянии редактирования.
      Наверно, один из самых точных методов, который не учитывает контекст.
    3. Объединение п.1 и п.2.
      Для ускорения поиска на больших словарях имеет смысл сначала выбрать группу слов на основании n-граммного индекса с последующим применением п.2 (см. работу Цобеля и Дарта “Finding approximate matches in large lexicons”)

    На хабре была хорошая статья, посвященная нечеткому поиску в тексте и словаре. В ней хорошо описаны п.1 и п. 2., в частности расстояния Левенштейна и Дамерау-Левенштейна с симпатичными картинками. Поэтому в данной статье подробного описания этих методов приводиться не будет.

    Реализация поиска
    В нашем случае словарь не такой большой (как например у поисковиков), порядка нескольких тысяч записей, поэтому мы решили использовать метод на основании расстояния редактирования без построения n-граммного индекса.
    Обычные алгоритмы вычисления расстояния редактирования хорошо оценивают близость строк, но не используют никакой информации о символах (кроме их равенства или неравенства), такой как расстояние между клавишами соответствующих символам на клавиатуре или близость по звучанию.
    Учет расстояния между клавишами может быть полезен так как при быстром наборе большое число ошибок происходит из-за промахов, при этом вероятность, что пользователь случайно нажал на соседнюю клавишу выше чем на более удаленную.
    Учет фонетических правил тоже важен. Например, в случае с иностранными именами и названиями, пользователи часто не знают точного написания слов, но помнят их звучание.
    В работе Цобеля и Дарта “Phonetic string matching: lessons from information retrieval” описывается метод сравнения строк объединяющий вычисление расстояния редактирования с набором фонетических правил (фраза “фонетические правила” не совсем корректна). Авторы выделили несколько фонетических групп, состоящих из символов, таких, чтобы “стоимость” замены символов одной группы при вычислении расстояния редактирования была ниже чем “стоимость“ замены символов не принадлежащих одной группе. Мы использовали эту идею.
    В качестве базового алгоритма мы взяли алгоритм Вагнера-Фишера адаптированный для нахождения расстояния Дамерау-Левенштейна с несколькими модификациями:
    1. В базовом алгоритме “стоимость” всех операций равна 1. Мы задали, что “стоимость” операций вставки и удаления — 2, операции обмена — 1, а операции замены одного символа другим вычисляется следующим образом: если клавиши, соответствующие сравниваемым символам, расположены рядом на клавиатуре или сравниваемые символы принадлежат одной фонетической группе, то “стоимость” замены — 1, иначе 2.
    2. В качестве результата возвращается префиксное расстояние, т.е. минимальное расстояние между словом запроса и всеми префиксами слова из словаря. Это нужно, т.к. слова запроса, которые мы будем сравнивать со словарными формами, как правило, будут обрезаны. Т.е. мы можем сравнивать введенное пользователем “макд” со словарным “макдональдс” и получить большое расстояние (7 операций вставки), хотя “макдональдс” в данном случае очень точно соответствует запросу.

    Фонетические группы мы взяли из упомянутой выше работы, с небольшими изменениями:


    В исходной работе группы составлялись на основании звучания оригинальных английских слов, поэтому нет гарантии, что они будут показывать хороший результат на транслитерированном русском тексте. Мы сделали небольшие изменения (например убрали ‘p’ из оригинальной группы “fpv”) на основании собственных наблюдений.

    Полученная реализация на c++:
    {{{
    class EditDistance
    {
    public:
        int DamerauLevenshtein(const std::string& user_str,
                        const std::string& dict_str)
        {
            size_t user_sz = user_str.size();
            size_t dict_sz = dict_str.size();
            for (size_t i = 0; i <= user_sz; ++i) {
                trace_[i][0] = i << 1;
            }
            for (size_t j = 1; j <= dict_sz; ++j) {
                trace_[0][j] = j << 1;
            }
            for (size_t j = 1; j <= dict_sz; ++j)
            {
                for (size_t i = 1; i <= user_sz; ++i)
                {
                    // Учтем вставки, удаления и замены
                    int rcost = ReplaceCost(user_str[i - 1], dict_str[j - 1]);
                    int dist0 = trace_[i - 1][j] + 2;
                    int dist1 = trace_[i][j - 1] + 2;
                    int dist2 = trace_[i - 1][j - 1] + rcost;
                    trace_[i][j] = std::min(dist0, std::min(dist1, dist2));
                    // Учтем обмен
                    if (i > 1 && j > 1 &&
                        user_str[i - 1] == dict_str[j - 2] &&
                        user_str[i - 2] == dict_str[j - 1])
                    {
                        trace_[i][j] = std::min(trace_[i][j],
                                            trace_[i - 2][j - 2] + 1);
                    }
                }
            }
            // Возьмем минимальное
            // префиксное расстояние
            int min_dist = trace_[user_sz][0];
            for (size_t i = 1; i <= dict_sz; ++i)
            {
                if (trace_[user_sz][i] < min_dist)
                    min_dist = trace_[user_sz][i];
            }
            return min_dist;
        }
     
    private:
        const static size_t kMaxStrLength = 255;
        int trace_[kMaxStrLength + 1][kMaxStrLength + 1];
    private:
        int ReplaceCost(unsigned char first, unsigned char second);
    }
    }}}
    


    Учтем, что в коротких словах пользователи, как правило, делают не такие грубые ошибки, как в длинных. Для этого сделаем порог максимально допустимого расстояния между словами пропорциональным длине слова запроса.
    {{{
    const double kMaxDistGrad = 1 / 3.0;
    ...
    uint32_t dist = distance_.DamerauLevenshtein(word, dict_form);
    if (dist <= (word.size() * kMaxDistGrad)) {
        // ok
    }
    }}}
    


    Индекс
    Пусть исходные записи по заведениям имеют вид:
    <мета данные: id,...><название заведения><синонимичные формы названия>
    Тогда индекс можно представить следующим образом:

    • places — мета данные по заведениям, которые являются результатом поиска.
    • places_index — названия и их синонимичные формы, ссылающиеся на конкретные заведения; по сути это просто массив ссылок на places.
    • words_index — слова, выделенные из всех форм; это что-то вроде инвертированного индекса вида: <слово><places_index0, places_index1,...>; в случае небольшого словаря его можно организовать в виде массива массивов.

      Во время поиска нужно будет пройти по всему массиву words_index для каждого слова запроса пользователя. Если словарь слишком большой, то, предположив, что ошибки в первой букве довольно редкие, можно ограничиться формами, начинающимися на ту же букву, что и слово запроса.

      Боремся за полноту
      Для увеличения полноты найденных заведений мы применили еще пару идей.
      1. При наборе, пользователи часто забывают переключить раскладку клавиатуры, (часто можно увидеть запросы вида: “ghfqv”, “vfrljy”,..). Поэтому возникла идея в случае, если при обычном поиске не было найдено ни одного заведения, производить такой же поиск с запросом, сформированным из символов противоположной раскладки базового запроса.
      2. Многие заведения не имеют русских названий, но пользователи привыкли набирать их кириллицей. Для таких заведений как McDonalds, Starbucks и др. кириллические формы названий, очевидно, можно занести в словарь как синонимы. Но для некоторых, как например GQ Bar, не целесообразно порождать синонимы типа “GQ бар”, и при этом необходимо, чтобы заведение соответствовало запросу “бар”. Поэтому для кириллических запросов в дополнение к обычному формируется дополнительный транслитерированный запрос.

      {{{
      // Ищем базовую форму фразы
      FindPhrase(base_phrase, &suggested);
      // И ее транслитерированную форму
      // если она отличается от базовой.
      std::string trs_phrase = Transliterate(base_phrase);
      if (trs_phrase != base_phrase)
         FindPhrase(trs_phrase, &suggested);
      // Если не получилось ничего найти
      // попробуем найти фразу из символов
      // противоположной раскладки
      if (suggested.empty())
      {
         std::string invert_phrase = InvertForm(base_phrase);
         FindPhrase(invert_phrase, &suggested);
      }
      }}}
      


      Общая реализация
      Вся логика индексирования и поиска реализовывалась в c++ демоне. Данные о заведениях периодически перечитываются из базы, индекс при этом полностью перестраивается. Общение с фронт-энд скриптами осуществляется по HTTP через GET запросы, результаты передаются в теле ответа в json формате. Получилась следующая схема:



      В результате при ~2.5 тыс. уникальных слов время поиска в среднем составило ~8 мс.

      Ссылки
      1. Сайт проекта. edatuda.ru
      2. Расстояние Левенштейна. ru.wikipedia.org/wiki/Расстояние_Левенштейна
      3. Расстояние Дамерау-Левенштейна. en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
      4. Работа Цобеля и Дарта. “Finding approximate matches in large lexicons”. citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.3856&rep=rep1&type=pdf
      5. Работа Цобеля и Дарта. “Phonetic string matching: lessons from information retrieval” citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.18.2138&rep=rep1&type=pdf
    Поделиться публикацией
    Комментарии 22
      +4
      К сожалению до любого ближайшего заведения 640 километров :)
        +2
        «Макдоналдс (729.2 км — 141 час и 38 мин. пешком)»

        Понимаю, что пока в Киеве нет заведений, но может не пугать людей жутким временем ходьбы (если время >N минут то не показывать время вообще) :)
          0
          Мда) 4184.1 км — 812 час и 45 мин. пешком
          Долго идти придется
            0
            При том, правда, что в Киеве «Макдональдсов» — куча.
              0
              Может они там какие-то неправильные? Ну там картопля вместо картошки и т.п.
          –8
          адаптивный поиск для школоты?
            +1
            Почему сразу для школоты? Например, если я ищу «Шоколадница» и набрал вместо первой «о» букву «л» (промазал не глядя на клавиатуре), то я не против, чтобы поиск поправил это на нужный вариант, а не заставлял удалять все или выбирать нужную букву курсором.

            А Вы? ;)
              0
              тут совсем немного юмора, просто это первая мысль по примeнению, а так спасибо, очень интересная статья.
            0
            Спасибо, интересная статья.

            Можете уточнить:
            1. какие фонетические группы у Вас получились для кириллицы?
            2. Не совсем понятно как у вас расширяется (а еще интереснее как изначально создавался) словарь (places и places-index)
              +1
              Базовый словарь places и places-index формируется на основании описаний заведений которые забиваются руками.
              places хранит данные которые мы возвращаем в качестве результатов, по сути мы по нему не ищем.
              places-index формируется на основании кириллическоего и/или английского названия заведения + набора синонимов.

              Каждую фразу (вариант названия) перед загрузкой в индекс мы пытаемся расширить так:
              1. Если фраза содержит '-' (например му-му), то создадим два варианта — без '-' и с заменой на пробел.
              2. Если фраза содержала русские символы то дополнительно создадим тринслитерированный вариант

              например для му-му получим:
              му-му => { муму, му му, mumu, mu mu }

              Для кириллицы мы объединили только (а, о, у) и (е, и)
              +13
              image
              Сапожник без сапог?
                +2
                image
                Сапожник без сапог?
                  +5
                  Прошу прощения, второй раз вышел случайно…
                    +1
                    Уже пасхалку закопали)
                    +1
                    — мк.дональдс
                    — ничего не нашли :(

                    Собственно тупую транслитерацию он не понял
                      0
                      Приведете пример с транслитерацией? мы посмотрим
                        +1
                        я думаю это и была транслитерация английской надписи русским алфавитом :)
                        Mc.Donalds
                      +1
                      image
                        0
                        Как-то не очень ясно, зачем было расписывать вещи вроде i << 1, которые любой компилятор сделает сам, если не замечена важнейшая особенность расстояния Левенштейна — достаточно хранить всего две, в данном случае, строки матрицы. Это даст выигрыш и по скорости и по памяти. Плюс код не потокобезопасен.

                        Да и если вы используете soundex, то какой смысл вообще в редакционном расстоянии?
                        Даже если есть реальная необходимость его использования, то сначала достаточно поискать точное вхождение soundex кода хеш-поиском, например, а потом если не повезет — уже подбирать варианты.

                        Это я все к чему. 8 миллисекунд на запрос к базе из 2.5к слов — это пугающий результат. Масштабируемость у вас линейная и всего 312к слов дадут секунду на запрос. К слову, за десятки миллисекунд мы отыскивали нечетким поиском подходящую ДНК секвенцию в базе на десятки гигабайт.
                          0
                          Да, конечно, соглашусь «i << 1» это перебор, это скорее привычка так писать.
                          И про две строки матрицы — тоже хороша идея, мы не делали токого рада оптимизаций, потому что пока производительность нас устраивает.

                          > Плюс код не потокобезопасен.
                          Зачем использовать этот объект в нескольких потоках? Вы сэкономите совсем немного памяти и получите расходы на синхронизацию.

                          > Да и если вы используете soundex, то…
                          Мы совсем его не используем.

                          > 8 миллисекунд на запрос к базе из 2.5к слов — это пугающий результат. Масштабируемость у вас линейная и всего 312к слов дадут секунду на запрос.
                          Да, вы правы, но в нашем случае словарь не будет линейно расти с ростом числа заведений в базе и врядли достигнет такого размера.
                          Если уж словарь большой сперва можно воспользоваться n-граммным индексом.
                          Ну и конечно в коде много мест которые можно пооптимизировать, наподобии двух строк матрицы про которые вы написали )

                          А каким индексом вы пользовались при поиске по базе ДНК? У вас все влезало в память или кешировали часть данных?
                          0
                          Погуглите еще на тему daitch-mokotoff кода. Он применим и для русского языка.
                            0
                            По сути предлагаемого подхода сказать нечего. А вот по поводу самого сайта — интересная, красивая реализация. Мы нечто подобное делали тут (тогда еще не было геолокации на уровне браузера, поэтому мы определяли местоположение с помощью стартапа Wi2Geo). Только вот в проекте InTheCity была целая редколегия которая обзванивала все заведения и составляла их TTX в итоге получалось нечто вроде: inthecity.ru/#/places/restaurants/YAkitoriya_Arbatskaya

                            У Вас я обнаружил вместо TTX краткое описание (пример: edatuda.ru/#!chain/yakitoriya):
                            Демократичный и непретенциозный суши-бар
                            Якитория — один из ветеранов среди многочисленных московских суши-баров. Уже более десяти лет она не теряет своей популярности. И неудивительно, ведь соотношение цена-качество в Якитории порадует всех.

                            Честно говоря зная Якиторию я с таким описанием не могу согласиться. Демократичным (по крайней мере по ценам) его не назовешь средний чек не ниже чем в том же Тануки или Нияме. Но и «непретенциозным» тоже никак назвать нельзя потому что внутреннее обстановка там одна из самых удачных среди суши баров (чего только аквариумы с рыбой которую периодически вылавливают и уносят на кухню) стоят и очки которые выдают для просмотра 3D меню.

                            Может стоит дать пользователям предлагать свои описания заведениям? А так же было бы не плохо дать возможность задавать пользовательские: теги, рейтинги и отзывы не фейсбуке, а в ваш движок что бы потом можно было выводить как на афишах/меню.ру.

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое