読者です 読者をやめる 読者になる 読者になる

文字列の類似度を測る

 今回は、文字列距離 (string distance)*1 を求める方法を紹介します。以下の例では、stringdistパッケージを用います。*2 このパッケージのstringdist関数を使うと、様々な文字列距離を求めることができます。

# パッケージの読み込み
library(stringdist)
# optimal string alignment
stringdist("corpus", "corpora", method = "osa")
# Damerau-Levenshtein distance (multiple editing of substrings allowed)
stringdist("corpus", "corpora", method = "dl")
# Levenshtein distance
stringdist("corpus", "corpora", method = "lv")
# Longest common substring distance
stringdist("corpus", "corpora", method = "lcs")
# q-gram distance
stringdist("corpus", "corpora", method = "qgram")
# cosine distance between q-gram profiles
stringdist("corpus", "corpora", method = "cosine")
# Jaccard distance between q-gram profiles
stringdist("corpus", "corpora", method = "jaccard")
# Jaro, or Jaro-Winker distance
stringdist("corpus", "corpora", method = "jw")
# Distance based on soundex encoding
stringdist("corpus", "corpora", method = "soundex")

 上記のスクリプトを実行すると、以下のような結果が出力されます。

# optimal string alignment
[1] 3
# Damerau-Levenshtein distance (multiple editing of substrings allowed)
[1] 3
# Levenshtein distance
[1] 3
# Longest common substring distance
[1] 5
# q-gram distance
[1] 5
# cosine distance between q-gram profiles
[1] 0.2614511
# Jaccard distance between q-gram profiles
[1] 0.4285714
# Jaro, or Jaro-Winker distance
[1] 0.2539683
# Distance based on soundex encoding
[1] 1

 また、qgrams関数を使うと、複数の文字列を対象として、任意の長さの文字連鎖を集計することができます。*3

# 比較する文字列
x <- "Hush a Bye Baby"
y <- "Hush thee, my babby"
z <- "Dance Little Baby"
# q-gramの集計
# 引数qで集計する文字連鎖の長さを指定
(qgram.mat <- qgrams(A = x, B = y, C = z, q = 2))

 上記のスクリプトを実行すると、以下のような結果が出力されます。

  Hu us ye y  sh th tt tl h  he my nc it le a  e  ee e, ab by ce ba bb an Li
A  1  1  1  0  1  0  0  0  1  0  0  0  0  0  1  1  0  0  1  1  0  0  0  0  0
B  1  1  0  1  1  1  0  0  1  1  1  0  0  0  0  0  1  1  1  1  0  1  1  0  0
C  0  0  0  0  0  0  1  1  0  0  0  1  1  1  0  2  0  0  1  1  1  0  0  1  1
   a By Da Ba  t ,   m  b  B  L
A  1  1  0  1  0  0  0  0  2  0
B  0  0  0  0  1  1  1  1  0  0
C  0  0  1  1  0  0  0  0  1  1

 そして、集計したq-gramを変数とする文字列のクラスタリングを行うこともできます。

# q-gramによる文字列のクラスタリング
plot(hclust(dist(qgram.mat)), hang = -1)

 上記のスクリプトを実行すると、以下のような図が出力されます。

f:id:langstat:20141006171005p:plain

*1:編集距離 (edit distance) と言われることもあります。

*2:かつては、MiscPsychoというパッケージもありました。

*3:ここで言う「文字」には、記号や空白も含まれます。