Tri Gramを使った正しい文章比較は

ネット上には文章の類似性を判定するための方法が色々出ています。
そのうちtri_gramを利用した方法は辞書などを必要としないのでまぁ便利です。 (ここの説明がわかりやすいです。)

最近それを利用して文章群と文章群の中から似た文章を選び出すという作業を行いました。 このときネットからプログラムを取り寄せたのですがどういうわけかみな違う値を出します。
いずれも問題があることがわかったので、高速化も兼ねて作ってしまいました。 githubに置いてあります
文章群と文章群の文章ごとの比較を行うときのためのちょっと手抜き高速化も仕込んであります。

プログラムの中を調べてみますと少しずつ違いがあります。(結果が違うんだから当然か)
原理を求めてさまよってわかったのは、(文章の)tri-gram の定義は明確なのですが、それを利用して 類似をを求める部分の説明・定義・原理について記述してあるものに行き当たりませんでした。
プログラムを眺めるといくつか懸念点がでてきます。

基本は 類似度 = 同じtrigramの数 / trigramの総数 なのですが

  1. 対称で無いものがある  「文章Aと文章Bの類似性を調べた場合も「文章Bと文章Aの類似性」も同じにならないとおかしいのに違うものがある
  2. 同じtri-gramが複数あると答えが違ってくる
結局次のことがわかりました。
  1. 分子の数え方と分母の数え方がまちまち。いずれにも問題がある。
  2. 分母の数え方で対称で無いものもある

類似度評価の考え方

例えば
  A→"AとBを比べても、BとAを比べても" と
  B→"BとAを比べても、AとBを較べても" という文章には次のtrigramがあります。
TriGramAとBとBをBを比を比べ比べて べてもても、も、B、BとBとA とAをAを比も、A、Aと Bを較を較べ較べて
回数A 1 1 1 2 2 2 1 1 1 1 1 1
B 1 1 1 1 2 1 1 1111 1 1 1

複数回出てくるtrigramがあることを考慮すると

  1. 分子:共通して存在するTriGramの数。重複する場合は重複した数(少ない方)
  2. 分母:全体のTriGramの数。ただし共通しているものはダブルカウントしない(多い方の数)
「整数の世界」的表現をすると 分子は最大公約数、分母は最小公倍数 となるのでは?

TriGramAとBとBをBを比を比べ比べて べてもても、も、B、BとBとA とAをAを比も、A、Aと Bを較を較べ較べて合計
回数分子 1 1 1 1 2 1 1 1 1 10
分母 1 1 1 2 2 2 111 1 1111 1 1 120

その考え方で作られていると思われるものは本methodの他に(2)(4)(6)が有りましたが、 各々少しずつ問題がありました。

  1. (2)(6)のrubyの2つは分子のカウントに Arrayの&演算を使っていますが、 これは重複する要素は取り除かれるため少なくなってしまいます。
     また分母のカウントに (Array+Array).uniq、もしくは  (Array|Array)を使っているため やはり重複している要素があると数が減ってしまいます。
  2. (4)のPHPは分子のカウントにarray_intersectを使っています。 これはrubyの & と違って重複を残すのですが、どういうわけか少ない方の数ではなく 多い方の数になってしまいます。
    またもとになるTrigramのとり方に間違いあが有りました。 文末の2文字、1文字もTriGramとして取り込んでいました。
  3. (5)のperlはどこに問題があるか読みきれませんでした。 perl4から5になる時にrubyに浮気したつけが今でてきました。
  4. (1)のrubyは 分子は自身と相手の同じtrigramの個数、分母は自身同士の同じtrigramの個数 をとっています。このため対称性がなくなりました。
    また個数を数える時に個数の積になってしまう数え方をしています。
  5. (3)はPHPのライブラリを使っているため中がわかりませんでした。 (PHPのソースまでは追いかけませんでした)
本方法(1)(2) (3)(4)(5)(6)
回数
AとB 1 1 1 1 1 1 1 1 11 1 1
とBを 1 1 1 1 1 1 1 1 11 1 1
Bを比 1 1 1 1 1
を比べ 2 1 1 2 2 4 1 1 21 1 1
比べて 2 1 1 2 2 4 1 1 21 1 1
べても 2 2 2 2 4 4 1 1 22 1 1
ても、 1 1 1 1 1 1 1 1 11 1 1
も、B 1 1 1 1 1
、Bと 1 1 1 1 1
BとA 1 1 1 1 1 1 1 1 11 1 1
とAを 1 1 1 1 1 1 1 1 11 1 1
Aを比 1 1 1 1 1 1 1 1 11 1 1
も、A 1 1 1 1 1
、Aと 1 1 1 1 1
Bを較 1 1 1 1 1
を較べ 1 1 1 1 1
較べて 1 1 1 1 1
べて 1 11 1
1 11 1
合計 10201421 917 1417 917
0.500.670.530.460.820.460.53

  1. (1) ruby http://freestyle.nvo.jp/archives/919 
  2. (2) ruby https://github.com/milk1000cc/trigram ruby
  3. (3) PHP similar_text
  4. (4) PHP http://www.pahoo.org/e-soul/webtech/php03/php03-06-01.shtm
  5. (5) Perl http://cpansearch.perl.org/src/TAREKA/String-Trigram-0.12/Trigram.pm
  6. (6) ruby http://www.mk-mode.com/octopress/2016/03/25/ruby-check-string-similarity-by-ngram/