擬似自然言語検索？ わかち書き検索、あいまい検索の実装まとめ

概要

実際の自然言語検索は

(検索)πはいくら？ => (結果)3.1415...

(検索)answer to life the universe and everything => (結果)42

というものであるが、ここでいう自然言語検索というのは検索しようとする文字に対して検索対象となる文字列がどれほど合致しているかを調べるものである。正確には自然言語検索ではないので擬似自然言語検索、正確にはあいまい検索、わかち書き検索と呼ぶのがふさわしい。

課題と実装

例えば英数字の文字列や数字に対する検索や比較は安易であるが、一般的な日本語における比較で

問アと問イは簡単だ。

と

問ｱと問ｲは簡単だ。

は内容が同じでもFalseを返してしまうし、また表記の揺らぎとして

簡単だ、問アと問イは。

となった場合は意味は同じで文字に対して正規化を施したとしてもそのまま比較するのは難しい。実際の所は日本語形態素解析などのライブラリやAPIを施して適切な品詞を評価するわけだが、実際にMigemoやらYahooのAPIを使うのは億劫である。そこで普段慣れしたんでいるUnicodeライブラリと正規表現ライブラリを用いて簡易なあいまい検索を実装することにした。コードはpythonとする。Unicodeにおける正規化ではunicodedataにまんまnormalizeという関数がある。phpであればmb_convert_kanaあたりだろう。

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import sys
reload(sys)
sys.setdefaultencoding('utf-8')

import unicodedata

if __name__ == '__main__':
	subject = u"ｽｹｼﾞｭｰﾙが切迫していたので、１４時に貴社の記者が汽車で帰社した。"
	subject = unicodedata.normalize('NFKC', subject).lower()
	print subject

>>>スケジュールが切迫していたので、14時に貴社の記者が汽車で帰社した。

英文の大文字小文字に対する処理はどちらに統一するかは自由であると思う。この手の正規化で十分に半角全角大文字小文字に対するゆらぎ、はある程度解消するはずだ。次に正規表現による、わかち書きを行う。

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import sys
reload(sys)
sys.setdefaultencoding('utf-8')

import re
import unicodedata

if __name__ == '__main__':
	r = re.compile(ur'([一二三四五六七八九十]+|[丁-龠]+|[ぁ-ん][ぁ-んー〜゛゜]*|[ァ-ヶ][ァ-ヶー〜゛゜]*|[0-9a-z][0-9a-z_\-]*)', re.UNICODE)
	k = re.compile(ur'[一-龠]', re.UNICODE)
	subject = u"ｽｹｼﾞｭｰﾙが切迫していたので、１４時に貴社の記者が汽車で帰社した。"
	subject = unicodedata.normalize('NFKC', subject).lower()
	words = r.findall(subject)
	for x in words:
		print x,

>>>スケジュール が 切迫 していたので 14 時 に 貴社 の 記者 が 汽車 で 帰社 した

漢数字、漢字、ひらがな、カタカナ、数字にわかち書きによる分割をおこない単語に分割していく。この、わかち書きで分割された単語の部分一致によるあいまい検索がキモの部分である。以降はこのわかち書きされたデータを洗練していくだけである。

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import sys
reload(sys)
sys.setdefaultencoding('utf-8')

import re
import unicodedata

if __name__ == '__main__':
	r = re.compile(ur'([一二三四五六七八九十]+|[丁-龠]+|[ぁ-ん][ぁ-んー〜゛゜]*|[ァ-ヶ][ァ-ヶー〜゛゜]*|[0-9a-z][0-9a-z_\-]*)', re.UNICODE)
	k = re.compile(ur'[一-龠]', re.UNICODE)
	subject = u"ｽｹｼﾞｭｰﾙが切迫していたので、１４時に貴社の記者が汽車で帰社した。"
	subject = unicodedata.normalize('NFKC', subject).lower()
	words = r.findall(subject)
	words = [word for word in words if len(word) > 1 or k.search(word)]
	for x in words:
		print x,

>>>スケジュール 切迫 していたので 14 時 貴社 記者 汽車 帰社 した

上記で目立った処理では、漢字でない一文字の単語は削除する処理だがこれは一文字でも大きな意味をもつ漢字に対して助詞や記号によるゆらぎを抑えるためであるが、ひらがな一文字であるなら前の単語と結合するというアプローチでもいいかもしれない。

漢字でない一文字の単語は削除する場合

スケジュール 切迫 していたので 14 時 貴社 記者 汽車 帰社 した

ひらがな一文字の単語を削除せず前の単語に結合する場合。

スケジュールが 切迫 していたので 14 時に 貴社の 記者が 汽車で 帰社 した

処理が複雑になるが、多少の単語における重要度が上昇し検索精度がよくなるかもしれない。最後に実際の検索処理に入る。

#! /usr/bin/env python
# -*- coding: utf-8 -*-
import sys
reload(sys)
sys.setdefaultencoding('utf-8')

import re
import unicodedata

haystack = [
	ur'ｽｹｼﾞｭｰﾙが切迫していたので、１４時に貴社の記者が汽車で帰社した。',
	ur'スケジュールの切迫により、１４時に御社の記者が汽車で帰社した。',
	ur'庭には二羽鶏がいる。',
	ur'予定通り、１４時に貴社の記者が汽車で帰社した。',
	ur'予定通り、１４時に貴社の記者が電車で帰社した。',
]

def build(subject, type):
	r = re.compile(ur'([一二三四五六七八九十]+|[丁-龠]+|[ぁ-ん][ぁ-んー〜゛゜]*|[ァ-ヶ][ァ-ヶー〜゛゜]*|[0-9a-z][0-9a-z_\-]*)', re.UNICODE)
	k = re.compile(ur'[一-龠]', re.UNICODE)
	h = re.compile(ur'[ぁ-んー〜]', re.UNICODE)
	subject = unicodedata.normalize('NFKC', subject).lower()
	words = r.findall(subject)


	if type:
		result = [word for word in words if len(word) > 1 or k.search(word)]
	else:
		result = []
		for i, w in enumerate(words):
			if len(w) > 1 or k.search(w):
				result.append(w)
			elif i > 0 and (len(w) == 1 and h.search(w)):
				result.append(result.pop() + w)

	return result

def search(subject, database):
	# 簡易高速版 しかし配列順序が保持されない。
	# result = [(list(set(d) & set(subject)),i) for i, d in enumerate(database)]

	# 真面目に処理版
	result = []
	for i, d in enumerate(database):
		hit = []
		for s in subject:
			if s in d:
				hit.append(s)
		if hit:
			result.append((hit, i))
	return result

if __name__ == '__main__':
	print u'＊漢字でない一文字の単語は削除する方法'
	subject = build(ur"ｽｹｼﾞｭｰﾙが切迫していたので、１４時に貴社の記者が汽車で帰社した。", True)
	database = [build(v, True) for v in haystack]
	result = search(subject, database)
	for r in result:
			print haystack[r[1]]
			print ur'A', '->', ((len(r''.join(r[0]))*1.0) / (len(r''.join(subject))*1.0)) * 100.0, ur'%'
			print ur'B', '->', (len(r[0])*1.0) / (len(subject)*1.0) * 100.0, ur'%'
	
	print u'\n'
	
	print u'＊ひらがな一文字の単語を削除せず前の単語に結合する方法'
	subject = build(ur"ｽｹｼﾞｭｰﾙが切迫していたので、１４時に貴社の記者が汽車で帰社した。", False)
	database = [build(v, False) for v in haystack]
	result = search(subject, database)
	for r in result:
			print haystack[r[1]]
			print ur'A', '->', ((len(r''.join(r[0]))*1.0) / (len(r''.join(subject))*1.0)) * 100.0, ur'%'
			print ur'B', '->', (len(r[0])*1.0) / (len(subject)*1.0) * 100.0, ur'%'

>>>
＊漢字でない一文字の単語は削除する方法
ｽｹｼﾞｭｰﾙが切迫していたので、１４時に貴社の記者が汽車で帰社した。
A -> 100.0 %
B -> 100.0 %
スケジュールの切迫により、１４時に御社の記者が汽車で帰社した。
A -> 70.3703703704 %
B -> 80.0 %
予定通り、１４時に貴社の記者が汽車で帰社した。
A -> 48.1481481481 %
B -> 70.0 %
予定通り、１４時に貴社の記者が電車で帰社した。
A -> 40.7407407407 %
B -> 60.0 %


＊ひらがな一文字の単語を削除せず前の単語に結合する方法
ｽｹｼﾞｭｰﾙが切迫していたので、１４時に貴社の記者が汽車で帰社した。
A -> 100.0 %
B -> 100.0 %
スケジュールの切迫により、１４時に御社の記者が汽車で帰社した。
A -> 50.0 %
B -> 70.0 %
予定通り、１４時に貴社の記者が汽車で帰社した。
A -> 53.125 %
B -> 70.0 %
予定通り、１４時に貴社の記者が電車で帰社した。
A -> 43.75 %
B -> 60.0 %

Aはヒット単語数の文字数による整合性、Bにはヒット単語数の整合性である。漢字でない一文字の単語を削除する場合の比較ではヒット単語数による整合性のほうが妥当性があるのだが、ひらがな一文字の単語を削除せず前の単語に結合する場合には文字数の多さが重要性の高さに関連しているのか、ヒット単語数による文字数による整合性のほうが良い結果が出るようであるのが興味深い。また助詞による表記のゆれによるヒット率の低下がケースによっては極端に見られる。大体において整合性が50%を超える場合は十分に関連性が高いと見えるだろう。今回は配列からinによる条件式を用いたが、SQLにおけるINでも同様の扱いが可能であると思う。setを用いた簡易処理版はpythonにおけるset型は配列順序が保持されず単語出現順位によるマッチングが利用できなくるという点が残念だ。

以上が日本語によるわかち書き検索、あいまい検索を用いた検索システムであるが、Unicodeだろうが、正規表現だろうが、日本語処理は難しく奥が深い。