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

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



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

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

    В связи с этим, решение задачи я начал искать там, где светлее, а именно с модуля pg_trgm.

    Триграммы


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

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

    Скучный SQL код
    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 индекс для нечеткого поиска по триграммам.

    Еще более скучный SQL код
    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 индекс для нечеткого поиска по триграммам.

    Думаете, передыдущие спойлеры с SQL были скучными?
    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 вида
    (смернов|смирнов|чернов)<->(денис)<->(анатольевич) 
    без обращения к таблице за дополнительной информацией о порядке лексемы в кортеже. Более того, рекомендацией для gin является физическое существование колонки tsvector, так как все найденные указатели на кортежи придется перепроверять в таблице. А если физически колонки tsvector нет (вы его построили функцией для индекса), то для каждого кортежа придется производить дополнительное вычисление tsvector. В общем, rum в данной истории будет куда производительнее.

    Эверест в мире скучного SQL
    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 1: добавил реализацию Metaphone от movEAX.
    UPDATE 2: добавил реализацию Metaphone на plpgsql от Ивана Милованова (telegram — milovanov)
    Метафон на plpgsql
    
    create or replace function phoneme (in_lexeme text)
    returns text
    language plpgsql
    immutable
    as $$
    declare
      res varchar(100) DEFAULT '';
    begin
      res := lower(in_lexeme);
      res := regexp_replace(res,'[ъь]','','g');
      res := regexp_replace(res,'(йо|ио|йе|ие)','и','g');
      res := regexp_replace(res,'[оыя]','а','g');
      res := regexp_replace(res,'[еёэ]','и','g');
      res := regexp_replace(res,'ю','у','g');
      res := regexp_replace(res,'б([псткбвгджзфхцчшщ]|$)','п\1','g');
      res := regexp_replace(res,'з([псткбвгджзфхцчшщ]|$)','с\1','g');
      res := regexp_replace(res,'д([псткбвгджзфхцчшщ]|$)','т\1','g');
      res := regexp_replace(res,'в([псткбвгджзфхцчшщ]|$)','ф\1','g');
      res := regexp_replace(res,'г([псткбвгджзфхцчшщ]|$)','к\1','g');  
      res := regexp_replace(res,'дс','ц','g');
      res := regexp_replace(res,'тс','ц','g');
      res := regexp_replace(res,'(.)\1','\1','g');
      return res;
    exception
      when others then raise exception '%', sqlerrm;
    end;
    $$;
    


    Тип поиска
    Время создания индекса
    Размер индекса
    Скорость поиска с опечатками
    Замечания
    Триграммы 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 и поиск осуществляется по выражению
    select metaphone('смирнов денис анатольевич') similar to mquery('Смернов дини онатольев');

    Функция mqery
    
    create or replace function mquery(in_fullname text)
    returns text
    language plpgsql
    immutable
    as $$
    declare
      res text;
    begin
      res := metaphone(in_fullname);
      res := regexp_replace(res, '(б|п)', '(б|п)', 'g');
      res := regexp_replace(res, '(з|с)', '(з|с)', 'g');
      res := regexp_replace(res, '(д|т)', '(д|т)', 'g');
      res := regexp_replace(res, '(в|ф)', '(в|ф)', 'g');
      res := regexp_replace(res, '(г|к)', '(г|к)', 'g');
      res := regexp_replace(res, '\s', '%', 'g');
      return '%'||res||'%';
    exception
      when others then raise exception '%', sqlerrm;
    end;
    $$;
    



    Так как в моем случае система будет ориентирована на чтение, а не на запись (максимум добавление пары пациентов в минуту), то мой вариант — Metaphone с триграммами. Если у кого-то есть идеи, как можно оптимизировать функцию на Python по скорости, то отпишитесь в комментариях, я добавлю данные в тесты.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 29

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

                        0

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

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

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

                          0
                          Спасибо за статью!

                          Only users with full accounts can post comments. Log in, please.