PostgreSQL, trigrammen en gelijkenis

Het concept van trigram-overeenkomst is afhankelijk van het feit dat elke zin is verdeeld in "trigrammen" (reeksen van drie opeenvolgende letters) en dat het resultaat wordt behandeld als een SET (d.w.z.:de volgorde doet er niet toe en u hebt geen herhaalde waarden). Voordat de zin wordt overwogen, worden aan het begin twee spaties toegevoegd en aan het einde één, en worden enkele spaties vervangen door dubbele.

Trigrammen zijn een speciaal geval van N-grams .

De trigramset die overeenkomt met "Chateau blanc" wordt gevonden door alle reeksen van drie letters te vinden die erop verschijnen:

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

Door ze te sorteren en herhalingen uit te schakelen krijg je:

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

Dit kan door PostgreSQL worden berekend door middel van de functie show_trgm :

SELECT show_trgm('Chateau blanc') AS A

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

... die 14 trigrammen heeft. (Controleer pg_trgm ).

En het trigram dat overeenkomt met "Chateau Cheval Blanc" is:

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]

... die 19 trigrammen heeft

Als je telt hoeveel trigrammen beide sets gemeen hebben, zie je dat ze de volgende hebben:

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

en degene die ze in totaal hebben zijn:

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

Dat wil zeggen, beide zinnen hebben 14 trigrammen gemeen, en 19 in totaal.
De overeenkomst wordt berekend als:

 similarity = 14 / 19

Je kunt het controleren met:

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

en je zult zien dat je het volgende krijgt:0.736842

... wat verklaart hoe gelijkenis wordt berekend, en waarom je krijgt de waarden die je krijgt.

OPMERKING:U kunt het snijpunt en de vereniging berekenen door middel van:

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 ;

En dit is een manier om de gelijkenis van verschillende paar zinnen te onderzoeken:

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 ;

Je kunt het controleren op Rextester