Ищем имена с опечатками в PostgreSQL

Все началось с того, что мне нужно было разработать поиск пациентов для одной внутренней медицинской системы. Логика работы была в том, что если мы не нашли человека в системе, то его нужно создать (а дубли пациентов плодить нельзя). В связи с этим одной из подзадач стала реализация поиска людей с учетом опечаток в их именах. Ну а поскольку я люблю PostgreSQL (а когда в руках у тебя молоток, то все похоже на гвозди), не сложно угадать, на чем я решил реализовать поиск с опечатками…

Обычно подобная задача решается двумя путями: с помощью нечеткого поиска или фонетическими алгоритмами. Будучи человеком ленивым и свято верящим, что все уже давно украдено придумано до нас, я обратился к документации PostgreSQL. На текущий момент в PostgreSQL есть два модуля, которые могут помочь в поиске с опечатками: pg_trgm и fuzzystrmatch.

1. pg_trgm работает с триграммами, умеет поиск по подстроке и нечеткий поиск. В качестве индексов работает с gist и gin.
2. fuzzystrmatch умеет считать расстояние Левенштейна между словами и три фонетических алгоритма: Soundex, Metaphone и Double Metaphone. Подводными камнями является, во-первых, то, что функция Левенштейна в данном модуле не позволяет создать индекс для произвольного поискового запроса. Во-вторых, все фонетические алгоритмы реализованы для латиницы.

Для простоты модели рассмотрим таблицу info с идентификатором пациента, его фамилией, именем и отчеством. Так как мы хотим gist/gin индексы, то для начала нужно знать важный, но неприятный момент: один gist/gin индекс — одна колонка таблицы. Его нельзя создать, например, по конкатенации нескольких колонок. Поэтому ниже под катом будут созданы:

• расширение pg_trgm
• таблица пациентов, хранящая ФИО в виде jsonb (с проверками существования и заполнения ключей)
• иммутабельная функция для построения индекса триграмм, преобразующая ФИО из jsonb в text

Вставляем в таблицу около 300 тыс. записей ФИО и приступаем.

Итак, первым проверяем gist индекс для нечеткого поиска по триграммам.

Индекс создавался 15 сек, размер 45 Мб, поиск по неполному имени с опечатками — 158 мс.

Далее рассмотрим gin индекс для нечеткого поиска по триграммам.

Создание индекса 10 сек, размер 18 Мб, поиск по неполному имени с опечатками — 133 мс.

Если честно, то результаты так себе — ведь у меня на ноутбуке стоит китайский ssd диск из славного города Шэньчжэня. Поэтому, попробуем ускорить процесс, совместив нечеткий и полнотекстовый поиск.

Идея крайне простая — собрать из всех написаний фамилий, имен и отчеств отдельную таблицу-словарь. Вначале входную строку поиска мы разрежем на лексемы, каждую из лексем поищем в таблице-словаре через нечеткий поиск, выберем оттуда все возможные варианты написаний каждой лексемы, положим их в tsquery и сделаем полнотекстовый поиск по tsvector индексу таблицы info. Выгода от этого плана в том, что скорость нечеткого поиска по триграммам зависит от ширины строки и их количества в колонке с текстом. Очевидно, что словарь ФИО будет компактнее, чем оригинальная колонка в таблице info, а значит — поиск будет быстрее. Недостаток у метода лишь один — при добавлении каждого нового пациента придется обновлять словарь, если лексемы из ФИО в нем не встречались. Для проверки нам потребуется собрать из исходников rum индекс для построения tsvector индекса по ФИО в таблице info. Rum является модифицированной версией gin индекса, хранящем в листьях дополнительную информацию. В нашем случае воспользуемся классом операторов rum_tsvector_ops, который хранит позиционную информацию о лексеме в индексе. Поэтому, в отличие от gin, мы сможем использовать index-only запрос tsquery вида без обращения к таблице за дополнительной информацией о порядке лексемы в кортеже. Более того, рекомендацией для gin является физическое существование колонки tsvector, так как все найденные указатели на кортежи придется перепроверять в таблице. А если физически колонки tsvector нет (вы его построили функцией для индекса), то для каждого кортежа придется производить дополнительное вычисление tsvector. В общем, rum в данной истории будет куда производительнее.

Итого, индекс полнотекстового поиска создавался 7 секунд (размер 13 Мб), индекс словаря лексем создался за 0,6 секунд (размер 5,8 Мб), поиск — 68 мс. Из недостатков — селективность хуже, чем у предыдущих вариантов.

Перепробовав варианты нечеткого поиска из модуля pg_trmg я решил посмотреть еще раз на fuzzystrmatch. Как проиндексировать функцию Левенштейна я не придумал, а вот фонетические алгоритмы меня крайне заинтересовали. Как говорилось выше, из коробки в PostgreSQL фонетические функции реализованы только для латиницы и заточены под английские имена. Поиск в интернете их русских реализаций привел меня на замечательную статью на Хабре, где описывался рабочий алгоритм Metaphone для русских имен (состоящих из русских букв). Печалило лишь одно — хоть он и был простым, но реализовывать эту логику на plpgsql было как-то совсем грустно, то ли дело на каком-нибудь Python… И тут я вспомнил, что plpython3u — является небезопасным (функции на нем могут получить доступ к файловой системе с правами процесса postgres), но отлично работающим языком в PostgreSQL. И грех бы им не воспользоваться. Поэтому, я написал две иммутабельные функции:

• phoneme на plpython3u, которая превращает лексему в фонему («смирнов» в «смирнаф») по алгоритму из статьи на Хабре
• metaphone на plpgsql, которая превращает уже не одну лексему в фонему, а целый текст в набор фонем. По факту, это просто обвязка над функцией phoneme.

Индекс создавался 114 сек, размер 22 Мб (кажется, я написал не самую оптимальную функцию на питоне по производительности), запрос 131 мс. Индекс срабатывает лишь по малой части подстроки, а дальше работает фильтр из-за "%". Плохо.

Попробуем на базе созданной на plpython3u функции metaphone построить индекс триграмм. Но будем использовать его теперь не для нечеткого поиска, а для поиска подстроки.

Время создания индекса — 124 сек, размер 15 Мб (привет мои кривые руки и plpython3u), поиск — 14 мс.

Тип поиска Время создания индекса Размер индекса Скорость поиска с опечатками Замечания Триграммы gist 15 сек 45 Мб 158 мс Триграммы gin 10 сек 18 Мб 133 мс Триграммы и полнотекстовый поиск 7,6 сек 18,8 Мб 68 мс Хуже селективность, нужно поддерживать словарь лексем Metaphone btree 114 сек 22 Мб 131 мс Небезопасный язык plpython3u Metaphone триграммы 124 сек 15 Мб 14 мс Небезопасный язык plpython3u Реализация Metaphone триграмм от movEAX 77,8 сек 16 Мб 14 мс Небезопасный язык plpython3u Реализация Ивана Милованова на plpgsql 72,0 сек 16 Мб 14 мс UPDATE 3: когда в индексе содержится «смирнаф динис анаталивич», то буква «в» в отчестве не оглушается (так как после нее идет гласная). Если искать по подстроке metaphone('анатольев'), то буква «в» оказывается не за гласной, а на конце и оглушится. Чтобы обойти эту проблему ниже написана функция mquery и поиск осуществляется по выражению

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