n-gram での文字列の類似度

n-gram を使って文字列の類似度を計算する方法のメモ。

n-gram を使って 0（類似していない） ～ 1（類似している） の類似度を計算します。

n-gram

n-gram は n 文字の連続する文字列で、abcd という文字列の場合には以下のようになります。

• 1-gram (unigram): a, b, c, d
• 2-gram (bigram): ab, bc, cd
• 3-gram (trigram): abc, bcd
• ...

n-gram を使った文字列の類似度

ここでは n-gram の頻度を使って、２つの文字列の類似度を以下のように計算します。

類似度 ＝ sum({文字列1の n-gram の出現頻度} × {文字列2の n-gram の出現頻度})
　　　　　÷ (sqrt(sum({文字列1 の n-gram の出現頻度}^2)) × sqrt(sum({文字列2 の n-gram の出現頻度}^2))

以降で、以下の文字列1、文字列2、文字列3 について類似度を計算してみます。

• 文字列1: abcd
• 文字列2: bcde
• 文字列3: dcba

unigramでの類似度計算例

文字列1-3 の unigram はそれぞれ以下のようになります。

• 文字列1: a, b, c, d
• 文字列2: b, c, d, e
• 文字列3: d, c, b, a

文字列1 と文字列2 の unigram での類似度は以下のようになります。

類似度　＝　(a:1×0 + b:1×1 + c:1×1 + d:1×1 + e:0×1)
　　　　　　÷　(sqrt(a:1^2 + b:1^2 + c:1^2 + d:1^2) × sqrt(b:1^2 + c:1^2 + d:1^2 + e:1^2))
　　　　＝　3 ÷ (sqrt(4) × sqrt(4))
　　　　＝　3/4

一方、文字列1 と文字列3 の unigram での類似度は以下のようになります。

類似度　＝　(a:1×1 + b:1×1 + c:1×1 + d:1×1)
　　　　　　÷　(sqrt(a:1^2 + b:1^2 + c:1^2 + d:1^2) × sqrt(a:1^2 + b:1^2 + c:1^2 + d:1^2))
　　　　＝　4 ÷ (sqrt(4) × sqrt(4))
　　　　＝　4/4　＝　1

unigram の場合は、文字列の並び順が類似度に反映されないため、文字列1と文字列3の類似度が1になります。

bigram での類似度計算例

次に bigram での類似度を計算してみます。

文字列1-3 の bigram はそれぞれ以下のようになります。

• 文字列1: ab, bc, cd
• 文字列2: bc, cd, de
• 文字列3: dc, cb, ba

文字列1 と文字列2 の bigram での類似度は以下のようになります。

類似度　＝　(ab:1×0 + bc:1×1 + cd:1×1 + de:0×1)
　　　　　　÷　(sqrt(ab:1^2 + bc:1^2 + cd:1^2) × sqrt(bc:1^2 + cd:1^2 + de:1^2))
　　　　＝　2 ÷ (sqrt(3) × sqrt(3))
　　　　＝　2/3

一方、文字列1 と文字列2 の bigram での類似度は以下のようになります。

類似度　＝　(ab:1×0 + bc:1×0 + cd:1×0 + dc:0×1 + cb:0×1 + ba:0×1)
　　　　　　÷　(sqrt(ab:1^2 + bc:1^2 + cd:1^2) × sqrt(dc:1^2 + cb:1^2 + ba:1^2))
　　　　＝　0 ÷ (sqrt(3) × sqrt(3))
　　　　＝　0/3　＝　0

bigram だと文字の並び順が類似度に反映されるため、並び順がずれていると類似度が低くなります。

n-gram での文字列の類似度計算プログラムの例

このプログラムでは文字列の先頭、末尾を考慮するため、文字列の先頭、末尾に n-1 文字の \t を追加して類似度計算を行います。

#
# NgramMatcher
#

import math

class NgramMatcher:
    BOS = '\t'
    EOS = '\t'


    @classmethod
    def ngrams(cls, n, str):
        ngrams = {}
        str = (cls.BOS * (n-1)) + str + (cls.EOS * (n-1))

        for i in range(0, len(str)-(n-1)):
            ng = str[i:i+n]
            cnt = ngrams.get(ng, 0)
            ngrams[ng] = cnt + 1

        return ngrams


    @classmethod
    def length(cls, ngrams):
        len2 = 0
        for ng in ngrams.keys():
            cnt = ngrams[ng]
            len2 += cnt * cnt

        len1 = math.sqrt(len2)
        return len1


    @classmethod
    def similarity(cls, n, str1, str2):
        ngs1 = cls.ngrams(n, str1)
        ngs2 = cls.ngrams(n, str2)

        print(ngs1)
        print(ngs2)

        sum = 0
        for ng1 in ngs1.keys():
            cnt1 = ngs1[ng1]
            cnt2 = ngs2.get(ng1, 0)
            sum += cnt1 * cnt2

        len1 = cls.length(ngs1)
        len2 = cls.length(ngs2)
        sim = sum / (len1 * len2)
        return sim

上記のプログラムを使って類似度を計算してみます。

$ python
>>> from ngram_matcher import NgramMatcher

>>> NgramMatcher.similarity(1, 'abcd', 'bcde')
{'a': 1, 'b': 1, 'c': 1, 'd': 1}
{'b': 1, 'c': 1, 'd': 1, 'e': 1}
0.75

>>> NgramMatcher.similarity(1, 'abcd', 'dcba')
{'a': 1, 'b': 1, 'c': 1, 'd': 1}
{'c': 1, 'd': 1, 'b': 1, 'a': 1}
1.0

>>> NgramMatcher.similarity(1, 'abab', 'baba')
{'a': 2, 'b': 2}
{'b': 2, 'a': 2}
0.9999999999999998

>>> NgramMatcher.similarity(2, 'abcd', 'bcda')
{'\ta': 1, 'ab': 1, 'bc': 1, 'cd': 1, 'd\t': 1}
{'\tb': 1, 'bc': 1, 'cd': 1, 'da': 1, 'a\t': 1}
0.3999999999999999

>>> NgramMatcher.similarity(2, 'abcd', 'dcba')
{'\ta': 1, 'ab': 1, 'bc': 1, 'cd': 1, 'd\t': 1}
{'\td': 1, 'dc': 1, 'cb': 1, 'ba': 1, 'a\t': 1}
0.0

>>> NgramMatcher.similarity(2, 'abab', 'baba')
{'\ta': 1, 'ab': 2, 'ba': 1, 'b\t': 1}
{'\tb': 1, 'ba': 2, 'ab': 1, 'a\t': 1}
0.5714285714285714

>>> NgramMatcher.similarity(2, 'abab', 'babab')
{'\ta': 1, 'ab': 2, 'ba': 1, 'b\t': 1}
{'\tb': 1, 'ba': 2, 'ab': 2, 'b\t': 1}
0.8366600265340756