top | software | pinconv | dictionary | history | rss | about

Fuzzy matching

検索を行う際に、多少違っていてもいいから似たような文字列を探したいことがよくあります。翻訳をしていると、熟語や慣用句、著名人の言葉などをもじったフレーズに出くわすことがあるのですが、元の言葉が分からないと原文の意味がつかめず困ったことになります。電子辞書だって「一石三鳥」と入力したら「その言葉は収録されていませんが、『一石二鳥』という言葉によく似てます」と返してくれると非常に助かるはずです。

こういう「完全に同じではないけれど、似たようなパターン」を検索することを曖昧検索（Fuzzy matching / Approximate pattern matching など）と言います。実現する方法（アルゴリズム）は色々あるようですが、今回はthe Tcler's Wiki の Fuzzy string searchを参考に簡略版自前ツールを作ってみたいと思います。

上記のサイトの最後の方で Artur Trzewik 氏が trigram を使って曖昧検索を行っていますが、以下では bigram による検索を書いてみます。なお trigram は、対象となる文字列を3文字ごとに区切る方式を指し、bigram は対象となる文字列を2文字ごとに区切ることを指しています。このように文字列をN文字で区切ることをN-gram方式と呼びます。言葉では分かりにくいですが、たとえば「こんにちは」の bigram 文字列は以下のようになります*1。

こん　んに　にち　ちは

検索したい文字列とそれが含まれているかもしれない文字列（検索対象文字列）を、このような文字のブロックにそれぞれ分割し、両者に重複しているブロックがたくさんあれば、2つの文字列は似ている*2と判断することができます。以下、文字列を bigram にする関数と重複数を確認するための関数を書いてみます。

proc bigram1 {str} {
	set blist [list]
	set l [expr {[string length $str]-1}]
	for {set x 0} {$x<$l} {incr x} {
		lappend blist [string range $str $x [expr {$x+1}]]
	}
	#重複する要素は省く
	return [lsort -unique $blist]
}
proc fzmatch1 {list1 list2} {
	set sum [expr [llength $list1] + [llength $list2]]
	set union [lsort -unique [concat $list1 $list2]]
	#重複していたブロックの数÷検索語句の長さ=類似度
	set similarity [expr 100*($sum - [llength $union])/[llength $list1]]
	return $similarity
}
proc test1 {str1 str2 similarity} {
	set blist1 [bigram1 $str1]
	set blist2 [bigram1 $str2]
	if {[fzmatch $blist1 $blist2] >= $similarity} {
		return true
	}
	return false
}

関数 bigram1 は、文字列を先頭から順番に2文字ずつのブロックに切り出して、重複を省いたTclのリストにします。少しややこしいのが関数 fzmatch1 ですが、やっていることは単純です。

引数の list1 は検索文字列の bigram リスト、list2 は検索対象文字列の bigram リストで、まず最初に2つのリストの要素数の合計を算出します。次に2つの bigram リストを結合（concat）し、さらに結合したリストから「lsort -unique」を使って重複する要素を取り除きます*3。重複を取り除いた結合リストの要素数を求め、重複を取り除く前の要素数との引き算を行います。これによって、重複していた要素の数が求められます。最後に、要素重複数を検索文字列の bigram リストの要素数で割って類似度を求めています。

この2つの関数の呼び出し元（上の例ではtest1）では、まず2つの文字列のbigram リストを作成し、それを fzmatch に渡しています。fzmatch から返ってきた類似度が指定された類似度（similarity）よりも高ければ、2つの文字列は似ていると判断し、true を返します。

重複している数が多ければ多いほど似ていると判断するだけですので、str1とstr2の文字列長が違っていても（例えば str1 は単語だけど str2 は文という場合など）問題なく検索できます。ただ、上手く動いてはいますが、bigram のリストを何度も作るのは時間がかかりますし、そもそも検索対象文字列の bigram 作成は不要な気もしますので、もう少し改良してみます。

#曖昧検索用の配列 fz を作成（グローバル変数）
set fz(\ufeff) "";#dummy
proc bigram2 {str} {
	global fz
	array unset fz
	set l [expr {[string length $str]-1}]
	set i 0
	for {set x 0} {$x<$l} {incr x} {
		set block [string range $str $x [expr {$x+1}]]
		if {![info exists fz($block)]} {
			set fz($block) 1
		}
		incr i
	}
	#文字列比較で使用する配列の要素数を返す
	return [expr $i+1]
}
proc fzmatch2 {str len} {
	global fz
	set l [expr {[string length $str]-1}]
	set i 0
	for {set x 0} {$x<$l} {incr x} {
		set chunk [string range $str $x [expr {$x+1}]]
		if {[info exists fz($chunk)]} {
			incr i
		}
	}
	set similarity [expr (100*$i)/$len]
	return $similarity
}
proc test2 {str1 str2 similarity} {
	#大域変数 fz にbigram化したstr1を保存
	set len [bigram2 $str1]
	if {[fzmatch2 $str2 $len] >= $similarity} {
		return true
	}
	return false
}

改良した点はいくつかありますが、1つめは str1、str2 両方の bigram を求めるのではなく、検索文字列 str1 の bigram だけを求め、その bigram をキーとする配列 fz を作成している点です。2つめは、実際の検索処理でリストの結合や並び替えを行わず、str2 を2文字ずつ切り出しながら、その2文字を key とする配列 fz が存在するかどうかだけを確認するかたちに変更している点です。存在していれば、カウンタ用の変数に1が加えられ、この数が多ければ多いほど、2つの文字列の類似度が高いということになります。

この2つの変更によって、str2 の bigram を作成する時間が節約できる上、リストをこねくり回す必要がなくなり、単純な2文字ごとの文字列比較で曖昧検索ができるようになります。また、検索対象文字列のどの部分がマッチしたのかが分かりますので、手を加えればマッチした部分のハイライト表示なども可能です（fzmatch1ではリストの並び替えをしているためできません）。

デモツール

上記2つの曖昧検索関数を使って、テキストファイルに対して指定した文字列の曖昧検索を行うツールを作ってみました。以下からダウンロードできますので、良かったら試してみてください。解凍後のフォルダ内に作成される fuzzy.exe がツールの本体で、テキスト入力欄に検索したい文章などを入力し、検索対象のファイルを「選択」してから「実行」ボタンを押すと曖昧検索を実行します。文字コードはシフトJIS、EUC-JP、UTF-8に対応していて、類似度は下部のスピンボックスで10～100% まで指定することができます。検索結果はテキストファイルに出力され、テキストファイルに関連づけているソフトで出力ファイルが開かれます。

「曖昧検索の方式」については、リスト生成方式が上述の fzmatch1 で、配列生成方式が fzmatch2 です。検索対象ファイルが大きければ大きいほど、配列生成方式の方が多少速くなると思います。なお、処理に要した時間は画面下部に表示されます。

ダウンロード：fuzzy.lzh（ソース同梱）

注：このツールでは読み込んだテキストファイルを改行と句点などの記号で区切り、できる限り1文ごとに検索文字列との比較を行います。

既知の問題点

上記2つの曖昧検索は、検索文字列の各bigramが検索対象文字列に含まれている数を目安に類似度を判断しているため、短い言葉を検索してもあまり威力を発揮しません。処理を単純化するために、重なっている部分が多ければ似ていると判断させているので、語順なども考慮されません。また、文字列の比較しか行っていないため、「征夷大将軍」をもじった「誠意大将軍」などの音の類似度を判断することも当然できません。人間ならこの2つも似ていると判断できるんですけどね。

応用

曖昧検索を使うと翻訳メモリを作成することができます。自分が過去に翻訳したテキスト（原文と訳文）を保存しておけば、「そういえばこれに似た文章を前にも訳したな」という時に、たとえうろ覚えでも適当なテキストを入力して検索すれば、それに似た文章を探してくることが可能です。今回は簡単な検索ツールを作りましたが、次は翻訳メモリにも挑戦してみたいと思っています。

2006-10-30 15:45:25
permalink | Tcl/Tk

←パワーポイントからテキストを抽出 | top | Poorman's Translation Memory→

Post a Comment