PostgreSQL, trigram, dan kesamaan

Konsep kesamaan trigram bergantung pada pembagian kalimat menjadi "trigram" (urutan tiga huruf berturut-turut), dan memperlakukan hasilnya sebagai SET (yaitu:urutannya tidak masalah, dan Anda tidak memiliki nilai berulang). Sebelum kalimat dipertimbangkan, dua spasi kosong ditambahkan di awal, dan satu di akhir, dan spasi tunggal diganti dengan spasi ganda.

Trigram adalah kasus khusus dari N-gram .

Kumpulan trigram yang sesuai dengan "Chateau blanc" ditemukan dengan menemukan semua urutan tiga huruf yang muncul di atasnya:

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

Menyortirnya, dan melakukan pengulangan membuat Anda:

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

Ini dapat dihitung oleh PostgreSQL melalui fungsi show_trgm :

SELECT show_trgm('Chateau blanc') AS A

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

... yang memiliki 14 trigram. (Periksa pg_trgm ).

Dan set trigram yang sesuai dengan "Chateau Cheval Blanc" adalah:

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]

... yang memiliki 19 trigram

Jika Anda menghitung berapa banyak trigram yang memiliki kedua himpunan yang sama, Anda menemukan bahwa mereka memiliki yang berikut:

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

dan yang mereka miliki secara total adalah:

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

Artinya, kedua kalimat memiliki 14 trigram yang sama, dan total 19 trigram.
Kesamaan dihitung sebagai:

 similarity = 14 / 19

Anda dapat memeriksanya dengan:

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

dan Anda akan melihat bahwa Anda mendapatkan:0.736842

... yang menjelaskan bagaimana kesamaan dihitung, dan mengapa Anda mendapatkan nilai yang Anda dapatkan.

CATATAN:Anda dapat menghitung persimpangan dan gabungan dengan cara:

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 ;

Dan ini adalah cara untuk mengeksplorasi kesamaan pasangan kalimat yang berbeda:

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 ;

Anda dapat memeriksanya di Rextester