Нечеткий поиск (fuzzy search) в реляционных базах данных

    Для поиска нужной информации на веб-сайтах и в мобильных приложениях часто используется поиск по словам или фразам, которые пользователь свободно вводит с клавиатуры (а не выбирает например из списка). Естественно, что пользователь может допускать ошибки и опечатки. В этом случае полнотекстовый поиск, полнотекстовые индексы, которые реализованы в большинстве баз данных не дают ожидаемого результата и практически бесполезны. Такой функционал все чаще реализуют на основе elasticsearch.

    Решения с использованием elasticsearch имеют один существенный недостаток — очень большая вероятность рассогласования основной базы данных, например PostgreSQL, MySQL, mongodb и elasticsearch, в которой хранятся индексы для поиска.

    Идеальным вариантом было бы наличие «моста», который бы брал на себя функцию согласования данных, в том случае когда база для поискового движка окажется недоступной во время обновления основной базы данных. Но я не нашел пока реализации такого моста. Например в одном из проектов связки mongodb и lucene говорится как раз об этой проблеме.
    On a normal shutdown of a LuMongo node, all segments committed and are distributed to existing nodes. This allows for rolling shutdowns of the nodes to update them. On unexpected shutdown the segments will fail to the existing nodes without committing. These indexes could require rollback or repair. Currently this is not handled automatically but it will be in future releases using Lucene's built in index repair. Since the documents are stored in MongoDB and not in the index, another possible solution could be fetching the documents for a corrupted segment and reindexing them. MongoDB also provides seamless failover through replication. MongoDB's replication is data center aware backups across datacenters are possible.
    Как же решается на практике эта проблема? Да никак. Если данные не очень большие то база просто переиндексируется по таймеру. Если база большая и часто переиндексировать ее невозможно — то все остается как есть, несогласованным, просто выявить это рассогласование немного сложнее.

    Надеюсь что устойчивые «мосты», которые будут устойчиво обновлять индексы в elasticsearch или lucene рано или поздно появятся. Сейчас же есть необходимость найти рабочее решение.

    Один из вариантов — это использовать единую базу для хранения данных и для поиска. По поводу использования в качестве такой единой базы elasticsearch, практически во всех обсуждениях на форумах был консенсус, что такое решение не подходит. Поэтому я начал искать базу данных в которой можно было бы создавать полнотекстовые индексы, поддерживающие нечеткий поиск. Поскольку основной движок для таких индексов, lucene, разработан на java, круг баз данных, в которых я искал такую возможность был явно очерчен.

    Как оказалось, есть как минимум два решения, которые используют библиотеку lucene и находятся на уровне приложений poduction ready: это orientdb и h2.

    В orientdb работать с нечетким полнотекстовым поиском очень просто:

    create class russian
    create property russian.message string
    create index russian.message on russian(message)
      fulltext engine lucene metadata {
        "analyzer": "org.apache.lucene.analysis.ru.RussianAnalyzer"
      }
    select * from russian where message lucene 'Харбахрб~0.5' limit 2
    

    В h2 немного сложнее т.к. индекс это отдельная таблица с которой нужно основную таблицу связать. Но немного сложнее это не означает сложно.

    CREATE ALIAS IF NOT EXISTS FTL_INIT FOR 
    "org.h2.fulltext.FullTextLucene.init";
    CALL FTL_INIT();
    DROP TABLE IF EXISTS TEST;
    CREATE TABLE TEST(ID INT PRIMARY KEY, FIRST_NAME VARCHAR, 
    LAST_NAME VARCHAR);
    CALL FTL_CREATE_INDEX('PUBLIC', 'TEST', NULL);
    INSERT INTO TEST VALUES(1, 'John', 'Wayne');
    INSERT INTO TEST VALUES(2, 'Elton', 'John');
    SELECT * FROM FTL_SEARCH_DATA('John', 0, 0);
    SELECT * FROM FTL_SEARCH_DATA('LAST_NAME:John', 0, 0);
    


    UPD.01.01.2021
    Уже после публикации нечеткий поиск начала поддерживать база данных ArangoDB. К сожалению, документация по этому функционалу не очень подробная. Поэтому делаю заметки того, что успел «нарыть».

    Сначала нужно создать анализатор с требуемыми параметрами поиска. Например такой (в arangosh):
    require('@arangodb/analyzers').save('fuzzy_search_bigram','ngram',{"min": 2,"max": 2,"preserveOriginal": false},["position", "frequency", "norm"] );
    


    Далее, в создаем view — это сделать можно в веб-интерфейсе ArangoDB.

    У созданного view будет пустой объект links, в котором будут храниться ссылки на индексируемые таблицы и поля. Добавим в это объект ссылку на индексируемую коллекцию:

    "links" : {
        "<collection_name>" : { 
          "includeAllFields": true,
             "fields" : { 
                 "title" :            { "analyzers" : [ "fuzzy_search_bigram"] },
                 "description" : { "analyzers" : [ "fuzzy_search_bigram"] }
             }
        }
    }
    


    И запрашиваем данные из созданного view:

    FOR d IN v_imdb 
      SEARCH NGRAM_MATCH(
        d.description, 
        'rodo Same goo to Moardoor', 
        0.6, 
        'fuzzy_search_bigram'
        )
      LET score = BM25(d)
      SORT score DESC
      RETURN { 
        Title:d.title, 
        Description:d.description, 
        Score:score 
      }
    


    Вторым способом реализации нечетного поиска ArangoDB может быть интеграция с elasticsearch. В отличие от интеграции с другими базами данных, которые не обеспечивают согласованность данных, в случае если на пути данных от базы в elasticsearch возникает сбой, с ArangoDB можно построить отказоустойчивую систему, так как в ArangoDB есть возможность запросить все изменения от любой точки времени в прошлом до текущего момента времени.

    Полезные ссылки
    1. colab.research.google.com/github/joerg84/ArangoDBUniversity/blob/master/FuzzySearch.ipynb#scrollTo=b9_f99xRfvcZ
    2. www.arangodb.com/2020/07/deep-and-fuzzy-dive-into-search

    apapacy@gmail.com
    22 апреля 2018 года

    Комментарии 6

      0
      Lucene не lucine…
        0
        Решал на практике двумя способами:
        — коммитом SQL транзакции только после успешной обработки запроса
        — второй отдельной транзакцией, подтверждающий переиндексацию.
          0

          Elasticsearch — это, можно сказать, порт Lucene. Т.е. имеет все те недостатки, что и Lucene. Потому его и не используют как master database.
          Вы в заголовке статьи пишете о fuzzy search, а в самой статье говорите о fulltext-search, являющимся частным случаем первого. Это разные вещи. Пример fuzzy search в Elasticserach — Minimum Should Match. По крайней мере, так я это понимаю :)


          Что касается, Вашего вопроса, порт пишется под задачу, не надо искать готового решения. Если Вы не понимаете как это должно работать, лучше не делать…
          А так, посмотрите CQRS, Event Sourcing, и лучше, если бы модель для поиска была отлична от первоначальной доменной модели Вашего приложения, в частности, имела бы ограниченное количество полей и индексов. И не забывайте, что вставка/обновление в Lucene и, как следствие в ElasticSearch, чрезвычайно сложная операция ;)

            0
            В статье как раз дается два примера применения библиотеки lucene для нечеткого поиска:

            select * from russian where message lucene 'Харбахрб~0.5' limit 2
            


            Пример для h2 я взял напрямую из документации. Для нечеткого поиска там будут тот же синтаксис

            SELECT * FROM FTL_SEARCH_DATA('Jonh~0.7', 0, 0);
            


            Согласен, что вставка и обновление в ElasticSearch чрезвычайно сложная операция (за это ее многие и любят). И отсуствие отказоустойчивых «мостов» это наша реальность. (Хотя почти все разработчики таких «мостов» включают эту опцию в «дорожную карту»). Но хотелоь бы иметь попроще и из коробки.

            Включение индекса типа lucene в реляционную базу данных может решить вопрос с поиском для сайтов малого и среднего уровня по объему и посещаемости. (а еще и сэкономить деньги на сервер т.к. для ElasticSearch минимальные требования по памяти 16Гб а лучше 32, что на порядок дороже необходимого для среднего сайта 4Гб).
              +1

              Повторюсь, не ищите простое решение для непростой задачи! Для малого сайта 4Гб Вам хватит, не сомневайтесь!


              Что касается, стека МастерДБ + Эластик, то я бы посоветовал акцептить данные в приложении (админке) при их добавлении/изменении/удалении через Event Sourcing. Т.е. определяете метод Accept[Insert/Update/Remove]<TModel>(TModel model), который и добавит/изменит/удалит Вашу доменную модель должным образом в индекс эластика со всеми нужными связями. Только этот метод должен быть реализован таким образом, чтобы никакое состояние индекса или мастерДБ не влияло на его результат — результат должен быть всегда одинаков.


              Пример:
              Добавляем, меняем товары, производителей и категории интернет-магазина.
              Делаем два метода:
              1) AcceptInsert<Product>(Product product): В результате, в индекс добавляется товар с проверкой по полю SourceId (Id в Вашей МастерДБ). У товара производитель (производителей мы редактировать не можем, только добавлять) копируется во вложенный документ, а категория ищется уже в индексе по SourceId.
              2) AcceptInsert<Category>(Category category): В результате, в индекс добавляется категория с проверкой по полю SourceId.


              После сохранения товара в админке, вызываем метод AcceptInsert<Product>. Либо делаем шедулер, который обновляет индекс каждые n-минут, работая с исходными документами по некоторому фильтру.

                +1

                Кстати, у раннего эластика был плагин, который просто сливал с монги или другой бд данные в себя. И не зря это выпилили ;)

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

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