PostgreSQL、トリグラム、類似性

トリグラムの類似性の概念は、任意の文を「トリグラム」（3つの連続する文字のシーケンス）に分割し、結果をSETとして扱うことに依存しています（つまり、順序は重要ではなく、繰り返し値はありません）。文が検討される前に、最初に2つの空白スペースが追加され、最後に1つの空白スペースが追加され、1つのスペースが2つのスペースに置き換えられます。

トリグラム N-grams の特殊なケースです。。

「シャトーブラン」に対応するトリグラムセットは、そこに表示される3文字のすべてのシーケンスを見つけることによって見つかります。

  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'

これは、関数show_trgmを使用してPostgreSQLで計算できます。：

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 を確認してください。

そして、「シャトーシュヴァルブラン」に対応するトリグラムセットは次のとおりです。

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 で確認できます。