京橋のバイオインフォマティシャンの日常

南国のビーチパラソルの下で、Rプログラムを打ってる日常を求めて、、Daily Life of Bioinformatician in Kyobashi of Osaka

【Rでの文字列処理シリーズ(その4)】文字列の近似的文字列マッチング

はじめに

文字列処理・テキスト処理とは、プログラミングを行うなかで、文字列・テキストに対する色々な操作のことを指します。それら処理をうまく使いこなすことで、文字列を自由に処理できるようになります。文字列処理の活用事例は、キーワード抽出、テキスト分類、テキストマイニングの前処理など、多岐に渡ります。 今回の「Rでの文字列処理」シリーズで扱う、文字列処理のライブラリ・関数群やプログラムコードは、R環境上で無料で提供されている、オープン・ソフトウェアを用います。

この記事では、主に、baseやstringr、stringdistとかのパッケージを扱い、Rでの文字列処理についていろいろと試してまとめてみました。主題としては、文字列距離を使って、近似的文字列をマッティングする方法を紹介します。

テキスト処理の関連記事

skume.net

skume.net

skume.net

skume.net

skume.net

skume.net

下準備について

########################
#シリーズ共通
########################
#必要なパッケージの読み込み
require(readr)
require(stringr)
require(stringdist)

近似的文字列マッティング

agrep & agrepl 関数

agrep/agrepl関数は、近似的文字列マッティング(あいまい一致)を提供する。

これらの関数は、一般化レーベンシュタイン編集距離(generalized Levenshtein edit distance) *1 を用いて、文字列 x(第2引数)の各要素内で、pattern(第1引数)に近似的にマッチするものを検索する。

ここでは、T/Fで結果が出力される、agrepl関数を扱う。

#対象パターンの文字列
ex0 <- "abcd"

#検索対象
ex1 <- c("a", "ab", "abc", "abd", "abcd", "cdab", "edcba", "abcdefg")

#基本出力
base::agrepl(pattern=ex0, x=ex1, max.distance = 0.1)
#[1] FALSE FALSE  TRUE  TRUE  TRUE FALSE FALSE  TRUE

#域値を変えた出力結果
#max.distance = 0
ex1[base::agrepl(pattern=ex0, x=ex1, max.distance = 0)]
#[1] "abcd"    "abcdefg"

#max.distance = 0.1
ex1[base::agrepl(pattern=ex0, x=ex1, max.distance = 0.1)]
#[1] "abc"     "abd"     "abcd"    "abcdefg"

#max.distance = 0.3
ex1[base::agrepl(pattern=ex0, x=ex1, max.distance = 0.3)]
#[1] "ab"      "abc"     "abd"     "abcd"    "cdab"    "abcdefg"

adist 関数

adist関数は、文字ベクトル間の近似的な文字列距離を計算する。 これで出力される距離は、一般化Levenshtein(編集)距離である。

# Approximate String Distances
adist(ex0,  ex1)
#     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#[1,]    3    2    1    1    0    4    4    3

stringdist / stringdistmatrix関数で、文字列間の距離指標を計算する

stringdist::amatchstringdist::ainという近似文字列マッチングの関数もあるのだが、 どうも使い勝手が悪くて、stringdist/stringdistmatrix関数を使用する方が良さそうに思う。

現在、stringdistがサポートしている距離指標は、以下の通りである。

手法名 概要
osa 最適文字列アラインメント(制限付きダメラウ・レーベンシュタイン距離)
lv Levenshtein距離(Rネイティブの adist と同様)
dl Full Damerau-Levenshtein 距離
hamming ハミング距離(aとbの文字数が同じであること)
lcs 最長共通部分文字列の距離
qgram q-gram距離
cosine q-gramプロファイル間のコサイン距離
jaccard q-gramプロファイル間のJaccard距離
jw Jaro距離、あるいはJaro-Winkler 距離
soundex soundexエンコーディングに基づく距離

詳細は、ここで確認できる。

search.r-project.org

とりあえず、いつくかの手法で近似的文字列マッティングを実行してみる。

ここでは、表形式で結果が出力されるstringdistmatrix関数を扱う。 使い方は、stringdistとほぼ同じ。

#対象パターンの文字列
ex0 <- "abcd"

#検索対象
ex2 <- c("a", "ab", "abc", "abd", "cdab", "edcba", "abcdefg")

#Optimal string aligment (osa)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="osa", nthread=2, useNames="strings")
#     a ab abc abd cdab edcba abcdefg
#abcd 3  2   1   1    4     4       3

#Levenshtein distance
stringdist::stringdistmatrix(a=ex0, b=ex2, method="lv", nthread=2, useNames="strings")
#     a ab abc abd cdab edcba abcdefg
#abcd 3  2   1   1    4     4       3

#Full Damerau-Levenshtein distance
stringdist::stringdistmatrix(a=ex0, b=ex2, method="dl", nthread=2, useNames="strings")
#     a ab abc abd cdab edcba abcdefg
#abcd 3  2   1   1    4     4       3

#Longest common substring distance
stringdist::stringdistmatrix(a=ex0, b=ex2, method="lcs", nthread=2, useNames="strings")
#     a ab abc abd cdab edcba abcdefg
#abcd 3  2   1   1    4     7       3

#q-gram distance (q=1)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="qgram", nthread=2, q=1, useNames="strings")
#     a ab abc abd cdab edcba abcdefg
#abcd 3  2   1   1    0     1       3

#q-gram distance (q=2)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="qgram", nthread=2, q=2, useNames="strings")
#     a ab abc abd cdab edcba abcdefg
#abcd 3  2   1   3    2     7       3

#q-gram distance (q=3)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="qgram", nthread=2, q=3, useNames="strings")
#     a ab abc abd cdab edcba abcdefg
#abcd 2  2   1   3    4     5       3

#cosine distance between q-gram profiles (q=1)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="cosine", nthread=2, q=1, useNames="strings")
#       a        ab       abc       abd cdab     edcba   abcdefg
#abcd 0.5 0.2928932 0.1339746 0.1339746    0 0.1055728 0.2440711

#cosine distance between q-gram profiles (q=2)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="cosine", nthread=2, q=2, useNames="strings")
#       a        ab       abc       abd      cdab edcba   abcdefg
#abcd NaN 0.4226497 0.1835034 0.5917517 0.3333333     1 0.2928932

#cosine distance between q-gram profiles (q=3)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="cosine", nthread=2, q=3, useNames="strings")
#       a  ab       abc abd cdab edcba   abcdefg
#abcd NaN NaN 0.2928932   1    1     1 0.3675445

#Jaccard distance between q-gram profiles (q=1)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="cosine", nthread=2, q=1, useNames="strings")
#       a        ab       abc       abd cdab     edcba   abcdefg
#abcd 0.5 0.2928932 0.1339746 0.1339746    0 0.1055728 0.2440711

#Jaccard distance between q-gram profiles (q=2)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="cosine", nthread=2, q=2, useNames="strings")
#       a        ab       abc       abd      cdab edcba   abcdefg
#abcd NaN 0.4226497 0.1835034 0.5917517 0.3333333     1 0.2928932

#Jaccard distance between q-gram profiles (q=3)
stringdist::stringdistmatrix(a=ex0, b=ex2, method="cosine", nthread=2, q=3, useNames="strings")
#       a  ab       abc abd cdab edcba   abcdefg
#abcd NaN NaN 0.2928932   1    1     1 0.3675445

#Jaro-Winkler distance
stringdist::stringdistmatrix(a=ex0, b=ex2, method="jw", nthread=2, useNames="strings")
#        a        ab        abc        abd cdab     edcba   abcdefg
#abcd 0.25 0.1666667 0.08333333 0.08333333    1 0.5166667 0.1428571

#  Distance based on soundex encoding
stringdist::stringdistmatrix(a=ex0, b=ex2, method="soundex", nthread=2, useNames="strings")
#     a ab abc abd cdab edcba abcdefg
#abcd 1  1   1   1    1     1       0

あとがき

どうも、osaとかlvとかの整数値の結果よりも、 cosine類似度かJaccard距離、Jaro-Winkler距離で計算して、 小数点以下の数値結果が返ってくる方が何だか計算したっ感じになるのは私だけだろうか。

参考資料

www.karada-good.net

www.okadajp.org

http://finzi.psych.upenn.edu/library/stringdist/html/amatch.htmlfinzi.psych.upenn.edu

https://journal.r-project.org/archive/2014-1/loo.pdfjournal.r-project.org

*1:ある文字列を別文字列に変換するのに必要な挿入、削除、置換の最小の重み付けされた数