PostgreSQL、trigrams and similarity

Question

MacでPostgreSQL 9.6.2をテストし、Ngramsで試してみてください。 wineryフィールドにGIN trigramインデックスがあるとします。

類似性（私はこれが推奨されていません知っている）の制限：私は2,3M行テーブル上のトライグラム検索を構築しています

SELECT set_limit(0.5); 

。

マイセレクトコード：

SELECT winery, similarity(winery, 'chateau chevla blanc') AS similarity 
FROM usr_wines 
WHERE status=1 AND winery % 'chateau chevla blanc' 
ORDER BY similarity DESC; 

マイ結果（私のMac上で329ミリ秒）：

Chateau ChevL Blanc 0,85 
Chateau Blanc 0,736842 
Chateau Blanc 0,736842 
Chateau Blanc 0,736842 
Chateau Blanc 0,736842 
Chateau Blanc, 0,736842 
Chateau Blanc 0,736842 
Chateau Cheval Blanc 0,727273 
Chateau Cheval Blanc 0,727273 
Chateau Cheval Blanc 0,727273 
Chateau Cheval Blanc (7) 0,666667 
Chateau Cheval Blanc Cbo 0,64 
Chateau Du Cheval Blanc 0,64 
Chateau Du Cheval Blanc 0,64 

まあ、私は "シャトー・ブラン" は類似性を持つことができる方法を理解していない>へこの場合シャトー・シュヴァル・ブラン "？私は2つの単語がまったく同じ "シャトー"と "ブラン"であることを理解していますが、他の単語 "cheval"はありません。

また、「Chateau ChevL Blanc」が最初に登場するのはなぜですか？手紙 "a"がありません！

私の目標は、ワイナリーの名前を間違えたとしても、すべての可能な重複を照合することです。私は何を取りこぼしたか ？

Answer 1

トリグラムの類似性の概念は、「トリグラム」（3つの連続した文字のシーケンス）に分割された文を持っており、その結果をSETとして扱うことに依存します（つまり、順序は関係ありません。繰り返し値）。文章を考慮する前に、最初に2つの空白が追加され、最後に1つの空白が追加され、1つの空白は2つ置きに置き換えられます。 Trigram構築

は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' 

これは、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を確認してください）。

との "シャトー・シュヴァル・ブラン" に対応するトライグラムセットは次のとおりです。

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] 

...

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

、彼らは合計で持っているものは次のとおりです：あなたは、あなたは彼らが次のようなものを持っていることを共通で両方のセットを見つけてきたどのように多くの卦数える場合は19の卦

を持っている

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

つまり、両方の文章に共通するのは14トリグラム、合計で19文です。
類似度は以下のように計算される。を説明している... 0.736842

：あなたがして、それを確認することができます

similarity = 14/19 

：

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

、あなたはあなたが得ることがわかりますhow類似度を計算し、なぜあなたはあなたが得る値を得る。

---

注：によって、交差点や労働組合を計算することができます

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

Answer 2

トリグラムアルゴリズムはより正確にする必要があります比較される文字列の長さの差は少なくなります。長さの違いの影響を補正するアルゴリズムを変更することができます。

以下の例示的な機能は、文字列長の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) 

、例えば、どのように多くの初期の文字が同じであるが（関数はもう少し複雑になると思いました）。