PostgreSQL, триграммы и подобие

Концепция подобия триграмм основывается на разделении любого предложения на «триграммы» (последовательности из трех последовательных букв) и обработке результата как SET (то есть: порядок не имеет значения, и у вас нет повторяющихся значений). Перед рассмотрением предложения два пробела добавляются в начале и один в конце, а одиночные пробелы заменяются двойными.

Триграммы - это частный случай N-граммов..

Набор триграмм, соответствующий "Chateau blanc", находится путем нахождения всех последовательностей из трех букв, которые появляются на нем:

  chateau  blanc
---                 => '  c'
 ---                => ' ch'
  ---               => 'cha'
   ---              => 'hat'
    ---             => 'ate'
     ---            => 'tea'
      ---           => 'eau'
       ---          => 'au '
        ---         => 'u  '
         ---        => '  b'
          ---       => ' bl'
           ---      => 'bla'
            ---     => 'lan'
             ---    => 'anc'
              ---   => 'nc '

Сортировка их и исключение повторов даст вам:

'  b'
'  c'
' bl'
' ch'
'anc'
'ate'
'au '
'bla'
'cha'
'eau'
'hat'
'lan'
'nc '
'tea'

Это может быть вычислено PostgreSQL с помощью функции show_trgm:

SELECT show_trgm('Chateau blanc') AS A

A = [  b,  c, bl, ch,anc,ate,au ,bla,cha,eau,hat,lan,nc ,tea]

... в котором 14 триграмм. (Проверьте pg_trgm).

И набор триграмм, соответствующий "Chateau Cheval Blanc", таков:

SELECT show_trgm('Chateau Cheval Blanc') AS B 

B = [  b,  c, bl, ch,anc,ate,au ,bla,cha,che,eau,evl,hat,hev,la ,lan,nc ,tea,vla]

... который имеет 19 триграмм

Если вы посчитаете, сколько триграмм имеют оба общих набора, вы обнаружите, что у них есть следующие:

A intersect B = 
    [  b,  c, bl, ch,anc,ate,au ,bla,cha,eau,hat,lan,nc ,tea]

и всего у них есть:

A union B = 
    [  b,  c, bl, ch,anc,ate,au ,bla,cha,che,eau,evl,hat,hev,la ,lan,nc ,tea,vla]

То есть оба предложения имеют 14 общих триграмм, а всего 19 триграмм.
Сходство вычисляется как:

 similarity = 14 / 19

Вы можете проверить это с помощью:

SELECT 
    cast(14.0/19.0 as real) AS computed_result, 
    similarity('Chateau blanc', 'chateau cheval blanc') AS function_in_pg

и вы увидите, что получите: 0.736842

... в котором объясняется как вычисляется сходство, и почему вы получаете полученные значения.

ПРИМЕЧАНИЕ. Вы можете вычислить пересечение и объединение с помощью:

SELECT 
   array_agg(t) AS in_common
FROM
(
    SELECT unnest(show_trgm('Chateau blanc')) AS t 
    INTERSECT 
    SELECT unnest(show_trgm('chateau chevla blanc')) AS t
    ORDER BY t
) AS trigrams_in_common ;

SELECT 
   array_agg(t) AS in_total
FROM
(
    SELECT unnest(show_trgm('Chateau blanc')) AS t 
    UNION 
    SELECT unnest(show_trgm('chateau chevla blanc')) AS t
) AS trigrams_in_total ;

И это способ исследовать сходство разных пар предложений:

WITH p AS
(
    SELECT 
      'This is just a sentence I''ve invented'::text AS f1,
      'This is just a sentence I''ve also invented'::text AS f2
),
t1 AS
(
    SELECT unnest(show_trgm(f1)) FROM p
),
t2 AS
(
    SELECT unnest(show_trgm(f2)) FROM p
),
x AS
(
    SELECT
        (SELECT count(*) FROM 
            (SELECT * FROM t1 INTERSECT SELECT * FROM t2) AS s0)::integer AS same,
        (SELECT count(*) FROM 
            (SELECT * FROM t1 UNION     SELECT * FROM t2) AS s0)::integer AS total,
        similarity(f1, f2) AS sim_2
FROM
    p 
)
SELECT
    same, total, same::real/total::real AS sim_1, sim_2
FROM
    x ;

Вы можете проверить это на Rextester.

Алгоритм триграммы должен быть тем точнее, чем меньше разница в длине сравниваемых строк. Вы можете изменить алгоритм, чтобы компенсировать эффект разницы в длине.

Следующая примерная функция уменьшает сходство на 1% для разницы в 1 символ в длинах строк. Это означает, что предпочтение отдается строкам одинаковой (одинаковой) длины.

create or replace function corrected_similarity(str1 text, str2 text)
returns float4 language sql as $$
    select similarity(str1, str2)* (1- abs(length(str1)-length(str2))/100.0)::float4
$$;

select 
    winery, 
    similarity(winery, 'chateau chevla blanc') as similarity,
    corrected_similarity(winery, 'chateau chevla blanc') as corrected_similarity
from usr_wines 
where winery % 'chateau chevla blanc'  
order by corrected_similarity desc;

          winery          | similarity | corrected_similarity 
--------------------------+------------+----------------------
 Chateau ChevL Blanc      |       0.85 |               0.8415
 Chateau Cheval Blanc     |   0.727273 |             0.727273
 Chateau Cheval Blanc     |   0.727273 |             0.727273
 Chateau Cheval Blanc     |   0.727273 |             0.727273
 Chateau Blanc,           |   0.736842 |             0.692632
 Chateau Blanc            |   0.736842 |             0.685263
 Chateau Blanc            |   0.736842 |             0.685263
 Chateau Blanc            |   0.736842 |             0.685263
 Chateau Blanc            |   0.736842 |             0.685263
 Chateau Blanc            |   0.736842 |             0.685263
 Chateau Cheval Blanc (7) |   0.666667 |                 0.64
 Chateau Du Cheval Blanc  |       0.64 |               0.6208
 Chateau Du Cheval Blanc  |       0.64 |               0.6208
 Chateau Cheval Blanc Cbo |       0.64 |               0.6144
(14 rows)

Аналогичным образом вы можете исправить стандартное сходство, например, по количеству идентичных начальных символов (хотя функция будет немного сложнее).

Иногда хочется обратного ответа клина. Есть приложения, в которых большая разница в длине строк не должна приводить к столь значительному снижению оценок.

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

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

Формула сходства вместо этого начинается с

the number of common trigrams
-------------------------------------------
the number of trigrams in the shortest word    <-- key difference

и может подняться оттуда на основе хорошей стандартной оценки сходства.

CREATE OR REPLACE FUNCTION substring_similarity(string_a TEXT, string_b TEXT) RETURNS FLOAT4 AS $$
DECLARE
  a_trigrams TEXT[];
  b_trigrams TEXT[];
  a_tri_len INTEGER;
  b_tri_len INTEGER;
  common_trigrams TEXT[];
  max_common INTEGER;
BEGIN
  a_trigrams = SHOW_TRGM(string_a);
  b_trigrams = SHOW_TRGM(string_b);
  a_tri_len = ARRAY_LENGTH(a_trigrams, 1);
  b_tri_len = ARRAY_LENGTH(b_trigrams, 1);
  IF (NOT (a_tri_len > 0) OR NOT (b_tri_len > 0)) THEN
    IF (string_a = string_b) THEN
      RETURN 1;
    ELSE
      RETURN 0;
    END IF;
  END IF;
  common_trigrams := ARRAY(SELECT UNNEST(a_trigrams) INTERSECT SELECT UNNEST(b_trigrams));
  max_common = LEAST(a_tri_len, b_tri_len);
  RETURN COALESCE(ARRAY_LENGTH(common_trigrams, 1), 0)::FLOAT4 / max_common::FLOAT4;
END;
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION corrected_similarity(string_a TEXT, string_b TEXT) 
RETURNS FLOAT4 AS $$
DECLARE
  base_score FLOAT4;
BEGIN
  base_score := substring_similarity(string_a, string_b);
  -- a good standard similarity score can raise the base_score
  RETURN base_score + ((1.0 - base_score) * SIMILARITY(string_a, string_b));
END;
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION is_minimally_substring_similar(string_a TEXT, string_b TEXT) RETURNS BOOLEAN AS $$
BEGIN
  RETURN corrected_similarity(string_a, string_b) >= 0.5;
END;
$$ LANGUAGE plpgsql;

CREATE OPERATOR %%% (
  leftarg = TEXT,
  rightarg = TEXT,
  procedure = is_minimally_substring_similar,
  commutator = %%%
);

Теперь вы можете использовать это так же, как стандартный запрос на подобие:

SELECT * FROM table WHERE name %%% 'chateau'
ORDER BY corrected_similarity(name, 'chateau') DESC;

Представление

Производительность приемлема для области поиска в 100 тыс. Записей, но, вероятно, не будет хорошей для области поиска в миллионы. Для этого вы можете использовать модифицированную сборку модуль pg_trgm, код на github.