Комментарии 29
По названию подумал, что вы ищете имена переменных с опечатками в исходном коде PostgreSQL…
НЛО прилетело и опубликовало эту надпись здесь
Я смотрел алгоритм Дейча-Мокотоффа, но нашёл его реализацию только для английского алфавита. У вас были иностранные имена в латинице? Или вы русские имена транслитерируете?
НЛО прилетело и опубликовало эту надпись здесь
Я вначале тоже думал транслитерировать имена в индекс и дальше использовать того же Дейча-Мокотоффа или двойной Метафон. Но нашёл на хабре ту забавную реализацию русского Метафона и был приятно удивлён ее селективностью. Так что дополнительный оверхед не городил. А вот у вас интересный опыт был, может расскажете в статье и с подробностями?)
Что-то не так с этой задачей. ФИО — не уникальный ключ. Может быть несколько разных людей с одинаковым именем. И один и тот же человек может писать своё имя по-разному в зависимости от настроения (Наталия, Наталья).
Должно быть ещё что-то. Дата рождения, номер паспорта, номер полиса, адрес. Возможно, есть смысл сначала искать прямой match по этим параметрам, а затем уже перебирать имена.
Плюс учитываем то, что женщины склонны менять фамилию после замужества. Это один и тот же пациент, но с другой фамилией начиная с определённой даты. А иногда такое и несколько раз происходит.
Должно быть ещё что-то. Дата рождения, номер паспорта, номер полиса, адрес. Возможно, есть смысл сначала искать прямой 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?
Автор не потерял в качестве, информация из первых рук. Во всех выборках возвращалось менее 10 результатов при лимите в 10.
Кстати, то количество строк для разных выборок, которе вы написали, не имеет отношения к результатам. Это количество строчек в выводе плана explain (analyze, buffers) — можете сами посчитать))
Посыпаю голову пеплом :(
Вариант транслитерации ФИО не рассматривался?
Вариант транслитерации ФИО не рассматривался?
Рассматривался, пока не увидел алгоритм русского Метафона. Я его посмотрел и он показался мне вполне логичным в плане нивелирования ошибок, плюс его тестировали в бою. А транслитерация и последующая обработка фонетическими алгоритмами показалась мне чересчур сложной и потенциально дающей больше ошибок. Но я не тестировал.
Спасибо за статью!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Ищем имена с опечатками в PostgreSQL