【Python応用】N-gramを用いた類似度算出プログラム

ここではN-gramを用いた任意の文字列同士の類似度を算出するプログラムについて解説しています。

N-gramとは

文字列の類似度を調べる方法の一つであり、「隣り合ったN文字」を意味しています。

具体的には以下のようなものがあります。

項目	内容	例
N=1 unigram	1文字を取り出すこと	「ブ」「ル」「ー」「ピ」「リ」「オ」「ド」
N=2 bigram	隣り合う文字を2文字で取り出すこと	「ブル」「ルー」「ーピ」「ピリ」「リオ」「オド」
N=3 trigram	隣り合う文字を3文字で取り出すこと	「ブルー」「ルーピ」「ーピリ」「ピリオ」「リオド」

N数は任意の数を指定できます。

特徴としては辞書を用いないのでプログラムが重くなりません。しかし、逆に辞書を用いないので分割位置がおかしくなり、ノイズになってしまう可能性があります。「ブルーピリオド」の例を見ても品詞で区切ることができていないことが分かると思います。

N-gramを用いたプログラム

#1---文字列の分割
def ngram(sent, num):
    res = []
    slen = len(sent) - num + 1
    for i in range(slen):
        c_s = sent[i:i+num]
        res.append(c_s)
    return res
#2---文字のカウント
def calc_ngram(sent_a, sent_b, num):
    a = ngram(sent_a, num)
    b = ngram(sent_b, num)
    r = []
    count = 0
    for i in a:
        for j in b:
            if i == j:
                count += 1
                r.append(i)
    return count / len(a), r
#3---文字列の指定
a = "ブルーピリオドは面白い"
b = "3月のライオンも面白い"
print("比較文字列1:",a,len(a))
print("比較文字列2:",b,len(b))
#4---unigramの探索
per_1, word1 = calc_ngram(a,b,1)
print("unigram:",per_1,word1)
#5---bigramの探索
per_2, word2 = calc_ngram(a,b,2)
print("bigram:", per_2, word2)
#6---trigramの探索
per_3, word3  = calc_ngram(a,b,3)
print("trigram:", per_3, word3)

上記がプログラムになります。

それでは解説していきます。

#1---文字列の分割
def ngram(sent, num):
    res = []
    slen = len(sent) - num + 1
    for i in range(slen):
        c_s = sent[i:i+num]
        res.append(c_s)
    return res

1の部分では、任意の文字列を指定した数で区切っています。それをリストで返しています。

#2---文字のカウント
def calc_ngram(sent_a, sent_b, num):
    a = ngram(sent_a, num)
    b = ngram(sent_b, num)
    r = []
    count = 0
    for i in a:
        for j in b:
            if i == j:
                count += 1
                r.append(i)
    return count / len(a), r

2の部分では1で区切った文字のリストでsent_a、sent_bで一致した文字をカウントして一致率を算出して返しています。同時に一致した文字列も返しています。

#3---文字列の指定
a = "ブルーピリオドは面白い"
b = "3月のライオンも面白い"
print("比較文字列1:",a,len(a))
print("比較文字列2:",b,len(b))

3の部分では任意の文字列を指定しています。print文では指定した文字列とその長さを出力しています。

#4---unigramの探索
per_1, word1 = calc_ngram(a,b,1)
print("unigram:",per_1,word1)

4の部分では1文字区切りにおける探索を指定しています。下のprint文は探索結果を出力しています。

#5---bigramの探索
per_2, word2 = calc_ngram(a,b,2)
print("bigram:", per_2, word2)

5の部分では2文字区切りにおける探索を指定しています。unigram同様にprintで結果を出力しています。

#6---trigramの探索
per_3, word3  = calc_ngram(a,b,3)
print("trigram:", per_3, word3)

6の部分では3文字区切りにおける探索を指定しています。unigram同様にprintで結果を出力しています。

結果

比較文字列1: ブルーピリオドは面白い 11
比較文字列2: 3月のライオンも面白い 11
unigram: 0.36363636363636365 ['オ', '面', '白', 'い']
bigram: 0.2 ['面白', '白い']
trigram: 0.1111111111111111 ['面白い']

結果は上記になります。類似度としては1文字区切りでの結果が1番高いです。

Mecabなどで品詞分けして調べてみるとより正確な解析になりそうですね。