Обычно подобная задача решается двумя путями: с помощью нечеткого поиска или фонетическими алгоритмами. Будучи человеком ленивым и свято верящим, что все уже давно
- pg_trgm работает с триграммами, умеет поиск по подстроке и нечеткий поиск. В качестве индексов работает с gist и gin.
- fuzzystrmatch умеет считать расстояние Левенштейна между словами и три фонетических алгоритма: Soundex, Metaphone и Double Metaphone. Подводными камнями является, во-первых, то, что функция Левенштейна в данном модуле не позволяет создать индекс для произвольного поискового запроса. Во-вторых, все фонетические алгоритмы реализованы для латиницы.
В связи с этим, решение задачи я начал искать там, где светлее, а именно с модуля pg_trgm.
Триграммы
Для простоты модели рассмотрим таблицу info с идентификатором пациента, его фамилией, именем и отчеством. Так как мы хотим gist/gin индексы, то для начала нужно знать важный, но неприятный момент: один gist/gin индекс — одна колонка таблицы. Его нельзя создать, например, по конкатенации нескольких колонок. Поэтому ниже под катом будут созданы:
- расширение pg_trgm
- таблица пациентов, хранящая ФИО в виде jsonb (с проверками существования и заполнения ключей)
- иммутабельная функция для построения индекса триграмм, преобразующая ФИО из jsonb в text
create extension pg_trgm;
create table info (
patid integer, fullname jsonb,
constraint info_pk primary key (patid),
constraint fullname_exists check (
fullname ? 'lname'::text and
fullname ? 'fname'::text and
fullname ? 'sname'::text
),
constraint fullname_notnull check (
(fullname ->> 'lname'::text) is not null and
(fullname ->> 'fname'::text) is not null
)
);
create function fullname(in_fullname jsonb)
returns text
language plpgsql
immutable
as $$
begin
return regexp_replace(
lower(
trim(
coalesce(in_fullname->>'lname', '') || ' ' ||
coalesce(in_fullname->>'fname', '') || ' ' ||
coalesce(in_fullname->>'sname', '')
)
),
'ё',
'е',
'g'
);
exception
when others then raise exception '%', sqlerrm;
end;
$$;Вставляем в таблицу около 300 тыс. записей ФИО и приступаем.
Триграммы и GIST
Итак, первым проверяем gist индекс для нечеткого поиска по триграммам.
create index info_gist_idx on info
using gist (fullname(fullname) gist_trgm_ops);
CREATE INDEX
Time: 15054,102 ms
explain (analyze, buffers)
select patid, fullname(fullname) <-> 'смерно дени анато' as dist
from info order by dist limit 10;
Limit (cost=0.28..4.35 rows=10 width=8) (actual time=157.378..157.688 rows=10 loops=1)
Buffers: shared hit=5743
-> Index Scan using info_gist_idx on info (cost=0.28..126822.96 rows=312084 width=8) (actual time=157.371..157.655 rows=10 loops=1)
Order By: (fullname(fullname) <-> 'смерно дени анато'::text)
Buffers: shared hit=5743
Planning time: 0.225 ms
Execution time: 158.223 ms
(7 rows)
Индекс создавался 15 сек, размер 45 Мб, поиск по неполному имени с опечатками — 158 мс.
Триграммы и GIN
Далее рассмотрим gin индекс для нечеткого поиска по триграммам.
create index info_trgm_idx on info
using gin(fullname(fullname) gin_trgm_ops);
CREATE INDEX
Time: 10163,401 ms
explain (analyze, buffers)
select patid, similarity(fullname(fullname), 'смерно дени анато' ) as sml
from info where true
and fullname(fullname) % 'смерно дени анато'
order by sml desc limit 10;
Limit (cost=1180.22..1180.25 rows=10 width=8) (actual time=133.086..133.117 rows=8 loops=1)
Buffers: shared hit=5741
-> Sort (cost=1180.22..1181.00 rows=312 width=8) (actual time=133.080..133.090 rows=8 loops=1)
Sort Key: (similarity(fullname(fullname), 'смерно дени анато'::text)) DESC
Sort Method: quicksort Memory: 25kB
Buffers: shared hit=5741
-> Bitmap Heap Scan on info (cost=26.70..1173.48 rows=312 width=8) (actual time=132.828..133.048 rows=8 loops=1)
Recheck Cond: (fullname(fullname) % 'смерно дени анато'::text)
Heap Blocks: exact=7
Buffers: shared hit=5741
-> Bitmap Index Scan on info_gist_idx (cost=0.00..26.62 rows=312 width=0) (actual time=132.699..132.699 rows=8 loops=1)
Index Cond: (fullname(fullname) % 'смерно дени анато'::text)
Buffers: shared hit=5734
Planning time: 0.573 ms
Execution time: 133.225 ms
(15 rows)Создание индекса 10 сек, размер 18 Мб, поиск по неполному имени с опечатками — 133 мс.
Если честно, то результаты так себе — ведь у меня на ноутбуке стоит китайский ssd диск из славного города Шэньчжэня. Поэтому, попробуем ускорить процесс, совместив нечеткий и полнотекстовый поиск.
Триграммы и полнотекстовый поиск
Идея крайне простая — собрать из всех написаний фамилий, имен и отчеств отдельную таблицу-словарь. Вначале входную строку поиска мы разрежем на лексемы, каждую из лексем поищем в таблице-словаре через нечеткий поиск, выберем оттуда все возможные варианты написаний каждой лексемы, положим их в tsquery и сделаем полнотекстовый поиск по tsvector индексу таблицы info. Выгода от этого плана в том, что скорость нечеткого поиска по триграммам зависит от ширины строки и их количества в колонке с текстом. Очевидно, что словарь ФИО будет компактнее, чем оригинальная колонка в таблице info, а значит — поиск будет быстрее. Недостаток у метода лишь один — при добавлении каждого нового пациента придется обновлять словарь, если лексемы из ФИО в нем не встречались. Для проверки нам потребуется собрать из исходников rum индекс для построения tsvector индекса по ФИО в таблице info. Rum является модифицированной версией gin индекса, хранящем в листьях дополнительную информацию. В нашем случае воспользуемся классом операторов rum_tsvector_ops, который хранит позиционную информацию о лексеме в индексе. Поэтому, в отличие от gin, мы сможем использовать index-only запрос tsquery вида
(смернов|смирнов|чернов)<->(денис)<->(анатольевич) create extension rum;
create index info_rum_idx on info
using rum (
to_tsvector('simple'::regconfig, fullname(fullname)) rum_tsvector_ops
);
CREATE INDEX
Time: 7.545s (7 seconds)
create table patname (
lex text,
constraint patname_uniq_idx unique (lex)
);
create index patname_fuzzy_idx on patname using gin (lex gin_trgm_ops);
CREATE INDEX
Time: 0.596s
insert into patname (lex)
select word from ts_stat($$
select to_tsvector('simple', fullname(fullname)) from info
$$);
explain (analyze, buffers)
with fio as (
select lexeme as lex, positions[1] as pos
from unnest(to_tsvector('simple','смернов дин онатол'))
),
query as(
select to_tsquery('simple', string_agg(q.tq,'&')) as q from (
select f.pos, '('||string_agg(p.lex,'|')||')' as tq from fio as f
join patname as p on p.lex % f.lex
group by f.pos
) as q
)
select to_tsvector('simple'::regconfig, fullname(fullname))
<=> (select q from query) as rank, * from info
where to_tsvector('simple'::regconfig, fullname(fullname))
@@ (select q from query)
order by to_tsvector('simple'::regconfig, fullname(fullname))
<=> (select q from query);
Sort (cost=6453.71..6457.61 rows=1560 width=100) (actual time=68.201..68.202 rows=1 loops=1)
Sort Key: ((to_tsvector('simple'::regconfig, fullname(info.fullname)) <=> $3))
Sort Method: quicksort Memory: 25kB
Buffers: shared hit=536
CTE fio
-> Function Scan on unnest (cost=0.00..0.10 rows=10 width=34) (actual time=0.023..0.034 rows=3 loops=1)
CTE query
-> Aggregate (cost=1484.60..1484.86 rows=1 width=32) (actual time=11.829..11.830 rows=1 loops=1)
Buffers: shared hit=325
-> HashAggregate (cost=1484.30..1484.48 rows=10 width=34) (actual time=11.640..11.644 rows=2 loops=1)
Group Key: f.pos
Buffers: shared hit=325
-> Nested Loop (cost=16.58..1480.53 rows=755 width=19) (actual time=2.940..11.442 rows=62 loops=1)
Buffers: shared hit=325
-> CTE Scan on fio f (cost=0.00..0.20 rows=10 width=34) (actual time=0.028..0.053 rows=3 loops=1)
-> Bitmap Heap Scan on patname p (cost=16.58..147.28 rows=75 width=17) (actual time=1.905..3.717 rows=21 loops=3)
Recheck Cond: (lex % f.lex)
Rows Removed by Index Recheck: 321
Heap Blocks: exact=275
Buffers: shared hit=325
-> Bitmap Index Scan on patname_fuzzy_idx (cost=0.00..16.57 rows=75 width=0) (actual time=1.277..1.277 rows=342 loops=3)
Index Cond: (lex % f.lex)
Buffers: shared hit=50
InitPlan 3 (returns $3)
-> CTE Scan on query (cost=0.00..0.02 rows=1 width=32) (actual time=0.004..0.006 rows=1 loops=1)
InitPlan 4 (returns $4)
-> CTE Scan on query query_1 (cost=0.00..0.02 rows=1 width=32) (actual time=11.834..11.839 rows=1 loops=1)
Buffers: shared hit=325
-> Bitmap Heap Scan on info (cost=31.99..4885.97 rows=1560 width=100) (actual time=68.184..68.187 rows=1 loops=1)
Recheck Cond: (to_tsvector('simple'::regconfig, fullname(fullname)) @@ $4)
Heap Blocks: exact=1
Buffers: shared hit=536
-> Bitmap Index Scan on info_rum_idx (cost=0.00..31.60 rows=1560 width=0) (actual time=67.847..67.847 rows=1 loops=1)
Index Cond: (to_tsvector('simple'::regconfig, fullname(fullname)) @@ $4)
Buffers: shared hit=517
Planning time: 5.012 ms
Execution time: 68.583 ms
(37 rows)Итого, индекс полнотекстового поиска создавался 7 секунд (размер 13 Мб), индекс словаря лексем создался за 0,6 секунд (размер 5,8 Мб), поиск — 68 мс. Из недостатков — селективность хуже, чем у предыдущих вариантов.
Фонетические алгоритмы
Перепробовав варианты нечеткого поиска из модуля pg_trmg я решил посмотреть еще раз на fuzzystrmatch. Как проиндексировать функцию Левенштейна я не придумал, а вот фонетические алгоритмы меня крайне заинтересовали. Как говорилось выше, из коробки в PostgreSQL фонетические функции реализованы только для латиницы и заточены под английские имена. Поиск в интернете их русских реализаций привел меня на замечательную статью на Хабре, где описывался рабочий алгоритм Metaphone для русских имен (состоящих из русских букв). Печалило лишь одно — хоть он и был простым, но реализовывать эту логику на plpgsql было как-то совсем грустно, то ли дело на каком-нибудь Python… И тут я вспомнил, что plpython3u — является небезопасным (функции на нем могут получить доступ к файловой системе с правами процесса postgres), но отлично работающим языком в PostgreSQL. И грех бы им не воспользоваться. Поэтому, я написал две иммутабельные функции:
- phoneme на plpython3u, которая превращает лексему в фонему («смирнов» в «смирнаф») по алгоритму из статьи на Хабре
- metaphone на plpgsql, которая превращает уже не одну лексему в фонему, а целый текст в набор фонем. По факту, это просто обвязка над функцией phoneme.
Metaphone и btree
Далее попробуем создать обычный btree индекс по фукнции metaphone и оценим скорость.
create or replace function phoneme (in_lexeme text)
returns text
language plpython3u
immutable
as $$
import re
class Lexeme:
def __init__(self, body):
"""
:type body: str
"""
self.body = body.lower().strip()
# Правила замены гласных
self._vowels = {"(?:йо|ио|йе|ие)": "и", "[оыя]": "а", "[еёэ]": "и", "[ю]": "у"}
# Правила оглушения согласных
self._consonants = {"б": "п", "з": "с", "д": "т", "в": "ф"}
# Согласная должна быть оглушена, если за ней следует один из символов списка _deafening_chars
self._deafening_chars = ["б", "в", "г", "д", "ж", "з", "й"]
# Удаляемые символы
self._removable_chars = {"[ъь]": ""}
def _remove_double_chars(self):
return Lexeme("".join((char for num, char in enumerate(self.body) if char != self.body[num - 1])))
def _deafen_consonants(self):
modified_body = ""
for num, char in enumerate(self.body):
if char in self._consonants and (
num < len(self.body) - 1 and self.body[num + 1] in self._deafening_chars
or num == len(self.body) - 1
):
modified_body += self._consonants[char]
else:
modified_body += char
return Lexeme(modified_body)
@staticmethod
def _regexp_replace(text, char_dict):
modified_body = text
for item in char_dict:
modified_body = re.sub(item, char_dict[item], modified_body)
return Lexeme(modified_body)
def _replace_vowels(self):
return self._regexp_replace(self.body, self._vowels)
def _remove_chars(self):
return self._regexp_replace(self.body, self._removable_chars)
def metaphone(self):
return self._remove_chars()._replace_vowels()._deafen_consonants()._remove_double_chars().body
return Lexeme(in_lexeme).metaphone()
$$;
create or replace function metaphone (in_phonemes text)
returns text
language plpgsql
immutable
as $$
begin
return (
select string_agg(q.lex,' ') from (
select phoneme(lexeme) as lex from unnest(to_tsvector('simple', in_phonemes))
order by positions
) as q
);
exception when others then
raise '%', SQLERRM using errcode = SQLSTATE;
end;
$$;
create index info_metaphone_idx on info (
metaphone(fullname(fullname)) text_pattern_ops
);
CREATE INDEX
Time: 114.757s (a minute)
explain (analyze, buffers)
select patid, fullname from info
where metaphone(fullname(fullname)) like
regexp_replace(metaphone('смернов дин онатол'),'\s','%','g')||'%'
limit 10;
Limit (cost=76.03..1388.96 rows=10 width=96) (actual time=22.452..129.944 rows=3 loops=1)
Buffers: shared hit=239
-> Bitmap Heap Scan on info (cost=76.03..4146.10 rows=31 width=96)
(actual time=22.447..129.927 rows=3 loops=1)
Filter: (metaphone(fullname(fullname)) ~~ 'смирнаф%дин%анатал%'::text)
Rows Removed by Filter: 244
Heap Blocks: exact=234
Buffers: shared hit=239
-> Bitmap Index Scan on info_metaphone_idx (cost=0.00..76.02 rows=1560 width=0)
(actual time=0.061..0.061 rows=247 loops=1)
Index Cond: ((metaphone(fullname(fullname)) ~>=~ 'смирнаф'::text) AND
(metaphone(fullname(fullname)) ~<~ 'смирнах'::text))
Buffers: shared hit=5
Planning time: 1.012 ms
Execution time: 129.977 ms
(12 rows)
Time: 131,802 msИндекс создавался 114 сек, размер 22 Мб (кажется, я написал не самую оптимальную функцию на питоне по производительности), запрос 131 мс. Индекс срабатывает лишь по малой части подстроки, а дальше работает фильтр из-за "%". Плохо.
Metaphone и триграммы
Попробуем на базе созданной на plpython3u функции metaphone построить индекс триграмм. Но будем использовать его теперь не для нечеткого поиска, а для поиска подстроки.
create index info_metaphone_trgm_idx on info
using gin (metaphone(fullname(fullname)) gin_trgm_ops);
CREATE INDEX
Time: 124.713s (2 minutes)
explain (analyze, buffers)
select patid, fullname from info
where metaphone(fullname(fullname)) like
'%'||regexp_replace(metaphone('смернов дин онатол'),'\s','%','g')||'%' limit 10;
Limit (cost=92.24..134.98 rows=10 width=96) (actual time=9.562..10.638 rows=3 loops=1)
Buffers: shared hit=103
-> Bitmap Heap Scan on info (cost=92.24..224.74 rows=31 width=96) (actual time=9.554..10.617 rows=3 loops=1)
Recheck Cond: (metaphone(fullname(fullname)) ~~ '%смирнаф%дин%анатал%'::text)
Heap Blocks: exact=2
Buffers: shared hit=103
-> Bitmap Index Scan on info_metaphone_trgm_idx (cost=0.00..92.23 rows=31 width=0) (actual time=8.354..8.354 rows=3 loops=1)
Index Cond: (metaphone(fullname(fullname)) ~~ '%смирнаф%дин%анатал%'::text)
Buffers: shared hit=101
Planning time: 2.029 ms
Execution time: 10.726 ms
(11 rows)
Time: 14,480 msВремя создания индекса — 124 сек, размер 15 Мб (привет мои кривые руки и plpython3u), поиск — 14 мс.
Итоги
Подведем сводную таблицу различных вариантов поиска с опечатками
UPDATE: добавил реализацию Metaphone от movEAX.
| Тип поиска |
Время создания индекса |
Размер индекса |
Скорость поиска с опечатками |
Замечания |
| Триграммы 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 |
Так как в моем случае система будет ориентирована на чтение, а не на запись (максимум добавление пары пациентов в минуту), то мой вариант — Metaphone с триграммами. Если у кого-то есть идеи, как можно оптимизировать функцию на Python по скорости, то отпишитесь в комментариях, я добавлю данные в тесты.
Комментарии (29)
staticlab
28.10.2017 23:36На прошлой неделе по просьбе знакомого прикручивал ему quick&dirty-решение для нечёткого поиска имён в Mongo. Встроенных возможностей нечёткого поиска у неё нет, а разбираться с прикручиванием внешнего решения типа ElasticSearch к монге времени и большого желания не было. Остановился на индексации имён по Дейчу-Мокотоффу для первичного поиска, а затем фильтровал найденные решения на сервере по Джаро-Винклеру с заданным сходством в процентах. Но, что важно, размер базы и нагрузка были весьма маленькими, поэтому такое решение оправдывало себя.
darthunix Автор
29.10.2017 00:57Я смотрел алгоритм Дейча-Мокотоффа, но нашёл его реализацию только для английского алфавита. У вас были иностранные имена в латинице? Или вы русские имена транслитерируете?
staticlab
29.10.2017 01:05+1В основном имена были иностранные и на латинице. Но для остальных я дополнительно проводил транслитерацию. Тут важно, что Дейч-Мокотофф оптимизирован в том числе для славянских и еврейских имён по сравнению с Soundex. Вообще пробы показали, что он как-то получше обобщает имена, чем другие алгоритмы. Сравнивал я их тут, но полноценного статистического анализа не проводил.
darthunix Автор
29.10.2017 01:12Я вначале тоже думал транслитерировать имена в индекс и дальше использовать того же Дейча-Мокотоффа или двойной Метафон. Но нашёл на хабре ту забавную реализацию русского Метафона и был приятно удивлён ее селективностью. Так что дополнительный оверхед не городил. А вот у вас интересный опыт был, может расскажете в статье и с подробностями?)
staticlab
29.10.2017 01:17Не думаю, что стоит. Наколеночное решение, расово неверные технологии — раскритикуют и заминусуют. А основную идею я изложил.
wildraid
29.10.2017 00:28Что-то не так с этой задачей. ФИО — не уникальный ключ. Может быть несколько разных людей с одинаковым именем. И один и тот же человек может писать своё имя по-разному в зависимости от настроения (Наталия, Наталья).
Должно быть ещё что-то. Дата рождения, номер паспорта, номер полиса, адрес. Возможно, есть смысл сначала искать прямой match по этим параметрам, а затем уже перебирать имена.
Плюс учитываем то, что женщины склонны менять фамилию после замужества. Это один и тот же пациент, но с другой фамилией начиная с определённой даты. А иногда такое и несколько раз происходит.darthunix Автор
29.10.2017 00:38Это действительно упрощенная модель в статье. В реальности есть и дата рождения, и енп, снилс, паспорта, документы. Есть история изменений и архивный поиск по девичьей фамилии. Это я не тащил в статью, чтобы не загромождать запросы — история была именно про опечатки
VJean
29.10.2017 00:42Это медицина, данные вводятся с полиса ОМС (обязательного медицинского страхования), так что никаких
И один и тот же человек может писать своё имя по-разному в зависимости от настроения (Наталия, Наталья).
DmitryKogan
29.10.2017 00:39А где качество поиска? Что толку в быстрых индексах, если они не находят опечатки?
darthunix Автор
29.10.2017 00:44Согласен, качество выдачи надо было добавить. Но на всех запросах, кроме варианта с триграммы + полнотекстовый поиск по «смернов дин онатол» успешно находился «Смирнов Денис Анатольевич». В озвученном варианте (триграмм и полнотекст) по лексеме «дин» нашлась «дина», но не «денис». Во всех остальных случая селективность просто потрясающая и вызывает желание перекреститься)
DmitryKogan
29.10.2017 11:20Выражаю сдержанный скептицизм. Если алгоритм объединяет таких Смирновых, то у него false positive должна быть запредельная. Для того и нужна матрица ошибок, чтобы это оценить.
darthunix Автор
29.10.2017 12:33Там помимо фамилии есть имя и отчество. А в реальном продукте ещё и куча других параметров. Но если предложите методику испытаний для оценки качества поиска, я прогоню. И, кстати, буду благодарен за такой алгоритм.
DmitryKogan
29.10.2017 13:26Если есть размеченная выборка, все просто, но в Fuzzy matching ее обычно нет. Поэтому ошибки оценивают приблизительно. Число попаданий и False positive можно оценить вручную — просматриваете найденные вашим алгоритмом пары (или группы) и на визуально оцениваете, тот Смирнов или не тот и т.д. Если выборка большая, то все результаты не просмотришь, считаете пока не надоест. С False Positive сложнее — нужно визуально искать ненайденные совпадения, например, отсортируете по фамилии, имени и отчеству и считаете, что ваш алгоритм пропустил. Наверняка у вас есть управляющие параметры (у меня, например — минимальная степень близости по модифицированному Левенштейну), их можно крутить и менять соотношение Precision/Recall в нужную сторону. Я обычно догоняю False Positive до 10-20%, а False Negative отпускаю подальше — процентов до 30-40%. Но это уже зависит от данных и от задачи
sloniki
29.10.2017 00:39Можно ещё рассмотреть по настоящему сложный путь — прикрутить сбоку полнотекстовый поисковый движок типа Elasticsearch. Он за секунды перелопачивает миллиарды записей, умеет десятки вариаций fuzzy search, suggester (search-as-you-type) и многое многое другое.
darthunix Автор
29.10.2017 00:52Да, но в данном случае это было как из пушки по воробьям. Во-первых, лишняя сложность решения. Во-вторых, для транзакционных реализаций внешней индексации из PostgreSQL в ElasticSearch я нашёл только Zombodb. Но он умеет только pg 9.3,9.4,9.5 и es 1.7.1… остальные варианты сопряжения были сложнее и не оправданы на текущем объеме данных
movEAX
29.10.2017 02:11Если у кого-то есть идеи, как можно оптимизировать функцию на 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)darthunix Автор
29.10.2017 04:20Отлично, время создания индекса уменьшилось на 40%, размер почти такой же (разница в 1 Мб — думаю, тут случайный фактор как расщеплялись странички при создании индекса), скорость поиска аналогичная.
movEAX
29.10.2017 12:19+1В оригинальном коде была ошибка:
# Если бы в body была строка "тест", то после преобразований получилось бы "ест" "".join((char for num, char in enumerate(self.body) if char != self.body[num - 1]))
Первый символ сравнивался с последним и если они совпадали, то он пропускался — возможно это повлияло на изменение размера индекса.
VJean
29.10.2017 08:30-1Логика работы была в том, что если мы не нашли человека в системе, то его нужно создать (а дубли пациентов плодить нельзя).
Результаты анализа запросов:
Триграммы и GIST (7 rows)
Триграммы и GIN (15 rows)
Триграммы и полнотекстовый поиск (37 rows)
Metaphone и btree (12 rows)
Metaphone и триграммы (11 rows)
Мне кажется, что автор увлекся оптимизацией скорости запроса и потерял в качестве. Проверялись ли результаты без указания LIMIT?VJean
29.10.2017 08:44Еще вопрос по FTS: в коде to_tsvector используется конфигурация 'simple'. Почему не 'russian'?
darthunix Автор
29.10.2017 09:48Чтобы просто разрезать на лексемы без модификаций — это более простой аналог регуляризация по пробелам. А russian может для ряда фамилий убрать окончания или увидеть в них стоп-слова
darthunix Автор
29.10.2017 08:44Автор не потерял в качестве, информация из первых рук. Во всех выборках возвращалось менее 10 результатов при лимите в 10.
Кстати, то количество строк для разных выборок, которе вы написали, не имеет отношения к результатам. Это количество строчек в выводе плана explain (analyze, buffers) — можете сами посчитать))VJean
29.10.2017 08:53Посыпаю голову пеплом :(
Вариант транслитерации ФИО не рассматривался?darthunix Автор
29.10.2017 09:52Рассматривался, пока не увидел алгоритм русского Метафона. Я его посмотрел и он показался мне вполне логичным в плане нивелирования ошибок, плюс его тестировали в бою. А транслитерация и последующая обработка фонетическими алгоритмами показалась мне чересчур сложной и потенциально дающей больше ошибок. Но я не тестировал.
dreamzor
По названию подумал, что вы ищете имена переменных с опечатками в исходном коде PostgreSQL…