はじめに
文字列処理・テキスト処理とは、プログラミングを行うなかで、文字列・テキストに対する色々な操作のことを指します。それら処理をうまく使いこなすことで、文字列を自由に処理できるようになります。文字列処理の活用事例は、キーワード抽出、テキスト分類、テキストマイニングの前処理など、多岐に渡ります。 今回の「Rでの文字列処理」シリーズで扱う、文字列処理のライブラリ・関数群やプログラムコードは、R環境上で無料で提供されている、オープン・ソフトウェアを用います。
この記事では、主に、baseやstringr、stringdistとかのパッケージを扱い、Rでの文字列処理についていろいろと試してまとめてみました。主題としては、文字列距離を使って、近似的文字列をマッティングする方法を紹介します。
テキスト処理の関連記事
下準備について
######################## #シリーズ共通 ######################## #必要なパッケージの読み込み 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::amatch
とstringdist::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エンコーディングに基づく距離 |
詳細は、ここで確認できる。
とりあえず、いつくかの手法で近似的文字列マッティングを実行してみる。
ここでは、表形式で結果が出力される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距離で計算して、 小数点以下の数値結果が返ってくる方が何だか計算したっ感じになるのは私だけだろうか。
参考資料
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:ある文字列を別文字列に変換するのに必要な挿入、削除、置換の最小の重み付けされた数