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

データ分析、コマンドライン、プログラミングについての技術資料・自己アップデート・悩み事などをまとめています。現在、DL勉強中。

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

Rでの文字列処理について、いろいろと試してまとめてみた。

このシリーズでは、主に、baseやstringr、stringdistとかのパッケージを扱う。

今回は、文字列距離を使って、近似的文字列をマッティングする方法を紹介する。

下準備について

########################
#シリーズ共通
########################
#必要なパッケージの読み込み
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:ある文字列を別文字列に変換するのに必要な挿入、削除、置換の最小の重み付けされた数