Комментарии 29
По названию подумал, что вы ищете имена переменных с опечатками в исходном коде PostgreSQL…

На прошлой неделе по просьбе знакомого прикручивал ему quick&dirty-решение для нечёткого поиска имён в Mongo. Встроенных возможностей нечёткого поиска у неё нет, а разбираться с прикручиванием внешнего решения типа ElasticSearch к монге времени и большого желания не было. Остановился на индексации имён по Дейчу-Мокотоффу для первичного поиска, а затем фильтровал найденные решения на сервере по Джаро-Винклеру с заданным сходством в процентах. Но, что важно, размер базы и нагрузка были весьма маленькими, поэтому такое решение оправдывало себя.

Я смотрел алгоритм Дейча-Мокотоффа, но нашёл его реализацию только для английского алфавита. У вас были иностранные имена в латинице? Или вы русские имена транслитерируете?

В основном имена были иностранные и на латинице. Но для остальных я дополнительно проводил транслитерацию. Тут важно, что Дейч-Мокотофф оптимизирован в том числе для славянских и еврейских имён по сравнению с Soundex. Вообще пробы показали, что он как-то получше обобщает имена, чем другие алгоритмы. Сравнивал я их тут, но полноценного статистического анализа не проводил.

Я вначале тоже думал транслитерировать имена в индекс и дальше использовать того же Дейча-Мокотоффа или двойной Метафон. Но нашёл на хабре ту забавную реализацию русского Метафона и был приятно удивлён ее селективностью. Так что дополнительный оверхед не городил. А вот у вас интересный опыт был, может расскажете в статье и с подробностями?)

Не думаю, что стоит. Наколеночное решение, расово неверные технологии — раскритикуют и заминусуют. А основную идею я изложил.

Что-то не так с этой задачей. ФИО — не уникальный ключ. Может быть несколько разных людей с одинаковым именем. И один и тот же человек может писать своё имя по-разному в зависимости от настроения (Наталия, Наталья).

Должно быть ещё что-то. Дата рождения, номер паспорта, номер полиса, адрес. Возможно, есть смысл сначала искать прямой match по этим параметрам, а затем уже перебирать имена.

Плюс учитываем то, что женщины склонны менять фамилию после замужества. Это один и тот же пациент, но с другой фамилией начиная с определённой даты. А иногда такое и несколько раз происходит.

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

Это медицина, данные вводятся с полиса ОМС (обязательного медицинского страхования), так что никаких
И один и тот же человек может писать своё имя по-разному в зависимости от настроения (Наталия, Наталья).
А где качество поиска? Что толку в быстрых индексах, если они не находят опечатки?
Согласен, качество выдачи надо было добавить. Но на всех запросах, кроме варианта с триграммы + полнотекстовый поиск по «смернов дин онатол» успешно находился «Смирнов Денис Анатольевич». В озвученном варианте (триграмм и полнотекст) по лексеме «дин» нашлась «дина», но не «денис». Во всех остальных случая селективность просто потрясающая и вызывает желание перекреститься)
Выражаю сдержанный скептицизм. Если алгоритм объединяет таких Смирновых, то у него false positive должна быть запредельная. Для того и нужна матрица ошибок, чтобы это оценить.
Там помимо фамилии есть имя и отчество. А в реальном продукте ещё и куча других параметров. Но если предложите методику испытаний для оценки качества поиска, я прогоню. И, кстати, буду благодарен за такой алгоритм.
Если есть размеченная выборка, все просто, но в Fuzzy matching ее обычно нет. Поэтому ошибки оценивают приблизительно. Число попаданий и False positive можно оценить вручную — просматриваете найденные вашим алгоритмом пары (или группы) и на визуально оцениваете, тот Смирнов или не тот и т.д. Если выборка большая, то все результаты не просмотришь, считаете пока не надоест. С False Positive сложнее — нужно визуально искать ненайденные совпадения, например, отсортируете по фамилии, имени и отчеству и считаете, что ваш алгоритм пропустил. Наверняка у вас есть управляющие параметры (у меня, например — минимальная степень близости по модифицированному Левенштейну), их можно крутить и менять соотношение Precision/Recall в нужную сторону. Я обычно догоняю False Positive до 10-20%, а False Negative отпускаю подальше — процентов до 30-40%. Но это уже зависит от данных и от задачи
Можно ещё рассмотреть по настоящему сложный путь — прикрутить сбоку полнотекстовый поисковый движок типа Elasticsearch. Он за секунды перелопачивает миллиарды записей, умеет десятки вариаций fuzzy search, suggester (search-as-you-type) и многое многое другое.
Да, но в данном случае это было как из пушки по воробьям. Во-первых, лишняя сложность решения. Во-вторых, для транзакционных реализаций внешней индексации из PostgreSQL в ElasticSearch я нашёл только Zombodb. Но он умеет только pg 9.3,9.4,9.5 и es 1.7.1… остальные варианты сопряжения были сложнее и не оправданы на текущем объеме данных
Благодарю за статью! Полезно, когда даже не знаешь с какой стороны подступится.
Если у кого-то есть идеи, как можно оптимизировать функцию на Python по скорости, то отпишитесь в комментариях, я добавлю данные в тесты.

По моим замерам, на 10µs быстрее на одну итерацию
import re
from functools import reduce

# Правила замены гласных
VOWELS = {"(?:йо|ио|йе|ие)": "и", "[оыя]": "а", "[еёэ]": "и", "[ю]": "у"}
# Правила оглушения согласных
CONSONANTS = {"б": "п", "з": "с", "д": "т", "в": "ф"}
# Согласная должна быть оглушена, если за ней следует один из символов списка 
DEAFENING_CHARS = "бвгджзй"
# Удаляемые символы
REMOVABLE_CHARS = {ord("ъ"): None, ord("ь"): None}

def _canonicalize(s):
    return s.lower().strip()

def _remove_double_chars(s):
    return "".join(c for n, c in enumerate(s) if n == 0 or c != s[n - 1])

def _deafen_consonants(s):
    out = []
    for n, char in enumerate(s):
        if char in CONSONANTS and (
            n < len(s) - 1 and s[n + 1] in DEAFENING_CHARS
            or n == len(s) - 1
        ):
            out.append(CONSONANTS[char])
        else:
            out.append(char)
    return "".join(out)

def _replace_vowels(s):
    for pattern, replacement in VOWELS.items():
        s = re.sub(pattern, replacement, s)
    return s

def _remove_chars(s):
    return s.translate(REMOVABLE_CHARS)

return reduce(lambda x, modifier: modifier(x), (
    _canonicalize,
    _remove_chars,
    _replace_vowels,
    _deafen_consonants,
    _remove_double_chars,
), in_lexeme)

Отлично, время создания индекса уменьшилось на 40%, размер почти такой же (разница в 1 Мб — думаю, тут случайный фактор как расщеплялись странички при создании индекса), скорость поиска аналогичная.
В оригинальном коде была ошибка:

# Если бы в body была строка "тест", то после преобразований получилось бы "ест"
"".join((char for num, char in enumerate(self.body) if char != self.body[num - 1]))

Первый символ сравнивался с последним и если они совпадали, то он пропускался — возможно это повлияло на изменение размера индекса.
Посыпаю голову пеплом и признаю, что я не настоящий сварщик;)
Логика работы была в том, что если мы не нашли человека в системе, то его нужно создать (а дубли пациентов плодить нельзя).

Результаты анализа запросов:
Триграммы и GIST (7 rows)
Триграммы и GIN (15 rows)
Триграммы и полнотекстовый поиск (37 rows)
Metaphone и btree (12 rows)
Metaphone и триграммы (11 rows)


Мне кажется, что автор увлекся оптимизацией скорости запроса и потерял в качестве. Проверялись ли результаты без указания LIMIT?
Еще вопрос по FTS: в коде to_tsvector используется конфигурация 'simple'. Почему не 'russian'?

Чтобы просто разрезать на лексемы без модификаций — это более простой аналог регуляризация по пробелам. А russian может для ряда фамилий убрать окончания или увидеть в них стоп-слова

Автор не потерял в качестве, информация из первых рук. Во всех выборках возвращалось менее 10 результатов при лимите в 10.
Кстати, то количество строк для разных выборок, которе вы написали, не имеет отношения к результатам. Это количество строчек в выводе плана explain (analyze, buffers) — можете сами посчитать))

Посыпаю голову пеплом :(
Вариант транслитерации ФИО не рассматривался?

Рассматривался, пока не увидел алгоритм русского Метафона. Я его посмотрел и он показался мне вполне логичным в плане нивелирования ошибок, плюс его тестировали в бою. А транслитерация и последующая обработка фонетическими алгоритмами показалась мне чересчур сложной и потенциально дающей больше ошибок. Но я не тестировал.

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