Wikipediaを検索する形態素解析型の全文検索エンジンを実装します。検索文字列と各記事の類似度を計算して、類似度順に検索結果を表示することで全文検索を実現します。高速に検索するために索引と逆索引を実装していきます。
以前書いた【レコメンド】内容ベースと協調フィルタリングの長所と短所・実装方法まとめの続き記事です。全文検索を検索文字列に類似する記事をレコメンドする機能と考えると、形態素解析型の全文検索エンジンは内容ベースフィルタリングのレコメンドエンジンであると読み替えることが出来ます。
形態素解析型の全文検索エンジンの特性
全文検索を実現する方法は2つあります。形態素解析とN-Gramです。それぞれの特徴は次の通りです。
| 形態素解析 | N-gram | |
|---|---|---|
| インデクシング速度 | 遅い | 速い |
| インデックスサイズ | 小さい | 大きい |
| 検索ノイズ | 小さい | 多い |
| 検索漏れ | 多い | 少ない |
| 検索速度 | 速い | 遅い |
| 言語依存 | 辞書が必要 | 辞書が不要 |
※Wikipedia:全文検索から引用
判りにくい箇所のみ解説します。
検索漏れと言語依存で辞書が必要な点についてです。形態素解析型の全文検索は辞書に依存します。たとえば『東京スカイツリー』が辞書登録されていない形態素解析だと『東京』『スカイ』『ツリー』のように分割して認識してしまいます。結果として東京のクリスマスツリーといった意図しない検索結果が表示されます。前後の文脈を認識できない点が形態素解析型全文検索の弱点です。
完成品の検索結果
■ input1 体の抗酸化力や解毒力
output1 :
++++++++++++++++++++++
検索結果:体の抗酸化力や解毒力
++++++++++++++++++++++
- 1位:類似度:0.00787401574803
- 2-アダマンタノン
- 2位:類似度:0.00654878847413
- (R)-1-イソチオシアナト-4-(メチルスルフィニル)ブタン
- 3位:類似度:0.00507614213198
- 2-ヨードキシ安息香酸
- 4位:類似度:0.00465313028765
- トリブチルスズオキシド
- 5位:類似度:0.00440917107584
- アノキソマー
全文検索エンジンの仕様
日本語版Wikipediaの全てのページにアクセスして解析するデータ取得バッチと検索機能を開発します。
■ Wikipediaデータ取得バッチの動作フロー
1. Wikipediaの全タイトルを格納したファイル-jawiki-latest-all-titles-in-ns0.gzから記事のタイトルを取得
2. タイトルからWikipediaのURLを生成する。
3. URLにHTTP GETを実施してbody部分をメモリ上に展開する。
4. HTTP bodyの特徴ベクトルであるTF-IDFを計算する。(TF-IDFについては前回の記事を参照。)
5. 記事毎の索引と、特徴語毎の索引をRedisに生成する。
6. 1へ戻る。
■ 検索機能の動作フロー
1. 検索文字列の特徴ベクトルであるTF-IDFを計算する。
2. 特徴ベクトルを構成する特徴語毎に特徴語索引からデータを取得する。
3. 索引データから記事毎の類似度を計算して結果表示する。
■ 検索文字列の特徴ベクトルの出力例
input1 : 紅白歌合戦
output1 : [[u'紅白', 0.5], [u'歌合戦', 0.5]]
input2 : ニュートリノを除く質量のある粒子の中で最も軽い素粒子
output2 : [[u'ニュー', 0.16666666666666666], [u'トリノ', 0.16666666666666666], [u'粒子', 0.16666666666666666], [u'素粒子', 0.16666666666666666], [u'質量', 0.16666666666666666]]
■ 索引データから類似度計算例
検索文字列『紅白歌合戦』と各記事の類似度を計算してみます。(search.pyの実装読んだ方が速いかも)
index-data: 『紅白』で特徴語索引からデータ取得
| title | value |
|---|---|
| アニメ紅白歌合戦 | 0.0226161369193 |
| MAESTRO-T | 0.00769230769231 |
| エレキコミックと折原みかのガツガツホームラン | 0.00740740740741 |
index-data: 『歌合戦』で特徴語索引からデータ取得
| title | value |
|---|---|
| 1996年のテレビ_(日本) | 0.005555555555555556 |
| アニメ紅白歌合戦 | 0.00105263157895 |
| 2003年のテレビ_(日本) | 0.00100840336134 |
この場合の『アニメ紅白歌合戦』の類似度計算式は次の通りです。
0.5 * 0.0226161369193 + 0.5 * 0.00105263157895 = 0.011834384249125
ソースコード
github - text_serarch_prototype
install
install
easy_install lxml
pip install beautifulsoup4
pip install janome
pip install nltk
pip install redis
Wikipediaデータ取得バッチ
data_import.py
# -*- coding: utf-8 -*-
from __future__ import absolute_import, unicode_literals
import ssl
import time
from tx.storage import Storage
import requests
from tx.tfidf import TFIDF
# wikipedia 全タイトルリスト
DATA_PATH = './data/jawiki-latest-all-titles-in-ns0'
def create_index(title):
"""
WikipediaのページにHTTPアクセスして
文章の特徴ベクトルを抽出して、検索用の索引を生成する
"""
url = Storage.get_wikipedia_url(str(title))
print title, url
# WikipediaのページにHTTPアクセスして文章の特徴ベクトルを抽出
tfidf = TFIDF.gen_web(url)
# 検索用の索引を生成する
s.save_tfidf(title, tfidf)
return
print 'start'
# wikipedia全タイトルリストファイルからURLを生成
s = Storage()
f = open(DATA_PATH, 'r')
ct = 0
for title in f:
ct += 1
if ct < 0:
continue
try:
create_index(title)
except UnicodeDecodeError:
print "ERROR", title
except requests.exceptions.ConnectionError:
time.sleep(2)
except requests.exceptions.Timeout:
time.sleep(2)
except ssl.SSLError:
time.sleep(2)
storage.py
# -*- coding: utf-8 -*-
from __future__ import absolute_import, unicode_literals
import redis
import urllib
PREFIX = 'tx'
KEY_TITLE = '%s:TITLE:{}' % PREFIX
KEY_INDEX_TITLE = '%s:INDEX:{}' % PREFIX
KEY_R_INDEX_WORD = '%s:R_INDEX:{}' % PREFIX
class KeyMixin(object):
@classmethod
def get_key_title(cls, title):
title = urllib.quote_plus(title)
return KEY_TITLE.format(title)
@classmethod
def get_key_index(cls, title):
title = urllib.quote_plus(title)
return KEY_INDEX_TITLE.format(title)
@classmethod
def get_key_r_index(cls, word):
return KEY_R_INDEX_WORD.format(word)
class Storage(KeyMixin):
"""
タイトル毎のindexと特徴語毎のindexをredisに保存する
title ... Wikipediaのタイトル
word ... 特徴語
"""
_cli = None
timeout = 60 * 60 * 24 * 30
@classmethod
def get_wikipedia_url(cls, title):
"""
titleからwikipediaのURLを生成
"""
_base_url = "https://ja.wikipedia.org/wiki/{}"
url = _base_url.format(urllib.quote_plus(title))
return url[:-3]
@property
def client(self):
"""
:rtype : Redis
"""
if Storage._cli is None:
Storage._cli = redis.Redis(host='localhost', port=6379, db=2)
return Storage._cli
def save_tfidf(self, title, tfidf):
self.set_index(title, tfidf)
self.set_r_index(title, tfidf)
def set_index(self, title, tfidf):
"""
title毎のtfidf
titleをkeyとするZSETにtfidf値を上書き
"""
key = Storage.get_key_index(title)
self.client.delete(key)
for word, score in tfidf:
self.client.zadd(key, word, score)
def set_r_index(self, title, tfidf):
"""
文字毎の逆索引
特徴文字列(word)からtitleを逆引きできる。
"""
for word, score in tfidf:
key = Storage.get_key_r_index(word)
self.client.zadd(key, title, score)
def get_r_index(self, word):
"""
特徴語から記事を逆引きする。
"""
key = Storage.get_key_r_index(word)
return self.client.zrevrange(key, 0, 1000, withscores=True)
tfidf.py
# -*- coding: utf-8 -*-
from __future__ import absolute_import, unicode_literals
from collections import defaultdict
from math import sqrt
import re
import requests
from bs4 import BeautifulSoup
from janome.tokenizer import Tokenizer
import nltk
class TFIDF(object):
_t = None
@classmethod
def gen(cls, text, enable_one_char=False):
"""
Get TF-IDF
:param text: str
:rtype :list[list[str, float]]
"""
_text = cls.filter(text)
return cls.analysis(_text, enable_one_char=enable_one_char)
@classmethod
def gen_web(cls, url, enable_one_char=False):
"""
Get TF-IDF from url
:param url: str
:rtype: list[list[str, float]]
"""
# HTTP GET
response = requests.get(url, timeout=2)
# filter HTTP Tag
soup = BeautifulSoup(response.text, "lxml")
text = soup.title.name + soup.get_text()
return cls.gen(text, enable_one_char=enable_one_char)
@classmethod
def similarity(cls, tfidf1, tfidf2):
"""
Get TF-IDF and Cosine Similarity
cosθ = A・B/|A||B|
:param tfidf1: list[list[str, float]]
:param tfidf2: list[list[str, float]]
:rtype : float
"""
tfidf2_dict = {key: value for key, value in tfidf2}
ab = 0 # A・B
for key, value in tfidf1:
value2 = tfidf2_dict.get(key)
if value2:
ab += float(value * value2)
# |A| and |B|
a = sqrt(sum([v ** 2 for k, v in tfidf1]))
b = sqrt(sum([v ** 2 for k, v in tfidf2]))
return float(ab / (a * b))
@classmethod
def some_similarity(cls, base_url, data):
"""
:param base_url: str
:param data: list[lost[str, str]]
:rtype : list[lost[str, str, float]]
"""
base_tfidf = cls.gen_web(base_url)
return [[title, url, cls.similarity(base_tfidf, cls.gen_web(url))] for title, url in data]
@classmethod
def analysis(cls, text, enable_one_char):
"""
Calc TF-IDF
textを形態素解析して名詞の数を返却(Morphological Analysis)
:param text: str
:rtype : dict{str: int}
"""
result = defaultdict(int)
result2 = {}
count = 0
t = cls._get_tokenizer()
# 形態素解析
# f_in = lambda x, y: x.encode('utf-8') in y.encode('utf-8')
# f_in = lambda x, y: x.decode('shift-jis') in y.decode('shift-jis')
f_in = lambda x, y: x in y
for token in t.tokenize(text):
if not f_in('名詞', token.part_of_speech):
continue
count += 1
if f_in('非自立', token.part_of_speech):
continue
if f_in('接尾', token.part_of_speech):
continue
if f_in('数', token.part_of_speech):
continue
if not enable_one_char:
if len(token.surface) == 1:
continue
result[token.surface] += 1
result2[token.surface] = token
# TF-IDF計算
result3 = []
for key in result:
result3.append([key, result[key]])
result3.sort(key=lambda x: x[1], reverse=True)
result4 = []
for r in result3[:100]:
# print r[0], float(float(r[1])/float(count)), result2[r[0]]
result4.append([r[0], float(float(r[1])/float(count))])
return result4
@classmethod
def filter(cls, text):
"""
textをフィルターしてノイズを排除する
:param text: str
:rtype : str
"""
# アルファベットと半角英数と改行とタブを排除
text = re.sub(r'[a-zA-Z0-9¥"¥.¥,¥@]+', '', text)
text = re.sub(r'[!"“#$%&()\*\+\-\.,\/:;<=>?@\[\\\]^_`{|}~]', '', text)
text = re.sub(r'[\n|\r|\t|年|月|日]', '', text)
# 日本語以外の文字を排除(韓国語とか中国語とかヘブライ語とか)
jp_chartype_tokenizer = nltk.RegexpTokenizer(u'([ぁ-んー]+|[ァ-ンー]+|[\u4e00-\u9FFF]+|[ぁ-んァ-ンー\u4e00-\u9FFF]+)')
text = "".join(jp_chartype_tokenizer.tokenize(text))
return text
@classmethod
def _get_tokenizer(cls):
if TFIDF._t is not None:
return TFIDF._t
TFIDF._t = Tokenizer()
return TFIDF._t
■ data_import.pyの実行結果
検索機能のソースコード
search.py
# -*- coding: utf-8 -*-
from __future__ import absolute_import, unicode_literals
from collections import defaultdict
from tx.storage import Storage
from tx.tfidf import TFIDF
class Search(object):
@classmethod
def search(cls, v, count=5):
"""
vに関連するwikipediaページを検索する
"""
# vを形態素解析して特徴ベクトルを抽出
tfidf = TFIDF.gen(v)
s = Storage()
result = defaultdict(float)
for search_word, search_score in tfidf:
# 逆索引に問い合わせ実施
title_score_map = s.get_r_index(search_word)
for _title, _score in title_score_map:
# 類似度を計算して集計
result[_title] += search_score * _score
# 類似度scoreで降順ソート
search_result = [(k, result[k]) for k in result]
search_result = sorted(search_result, key=lambda x: x[1], reverse=True)
if len(search_result) >= count:
return search_result[:count]
return search_result
def printer(l, keyword):
print "++++++++++++++++++++++"
print "検索結果:{}".format(keyword)
print "++++++++++++++++++++++"
count = 1
for title, score in l:
print "- {}位:類似度:{}".format(str(count).encode("utf-8"), score)
print "-", title, Storage.get_wikipedia_url(title)
count += 1
def main():
v = "体の抗酸化力や解毒力"
printer(Search.search(v), v)
v = "地域型JPドメイン名"
printer(Search.search(v), v)
v = "アフリカ人 アイデンティティ 競争的資本主義体制 階級闘争"
printer(Search.search(v), v)
main()
実行結果
>>> python search.py
++++++++++++++++++++++
検索結果:体の抗酸化力や解毒力
++++++++++++++++++++++
- 1位:類似度:0.00787401574803
- 2-アダマンタノン
https://ja.wikipedia.org/wiki/2-%E3%82%A2%E3%83%80%E3%83%9E%E3%83%B3%E3%82%BF%E3%83%8E%E3%83%B3
- 2位:類似度:0.00654878847413
- (R)-1-イソチオシアナト-4-(メチルスルフィニル)ブタン
https://ja.wikipedia.org/wiki/%28R%29-1-%E3%82%A4%E3%82%BD%E3%83%81%E3%82%AA%E3%82%B7%E3%82%A2%E3%83%8A%E3%83%88-4-%28%E3%83%A1%E3%83%81%E3%83%AB%E3%82%B9%E3%83%AB%E3%83%95%E3%82%A3%E3%83%8B%E3%83%AB%29%E3%83%96%E3%82%BF%E3%83%B3
- 3位:類似度:0.00507614213198
- 2-ヨードキシ安息香酸
https://ja.wikipedia.org/wiki/2-%E3%83%A8%E3%83%BC%E3%83%89%E3%82%AD%E3%82%B7%E5%AE%89%E6%81%AF%E9%A6%99%E9%85%B8
- 4位:類似度:0.00465313028765
- トリブチルスズオキシド
https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%AA%E3%83%96%E3%83%81%E3%83%AB%E3%82%B9%E3%82%BA%E3%82%AA%E3%82%AD%E3%82%B7%E3%83%89
- 5位:類似度:0.00440917107584
- アノキソマー
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%8E%E3%82%AD%E3%82%BD%E3%83%9E%E3%83%BC
++++++++++++++++++++++
検索結果:地域型JPドメイン名
++++++++++++++++++++++
- 1位:類似度:0.0217041800643
- アビティビ・テミスカマング地域
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%93%E3%83%86%E3%82%A3%E3%83%93%E3%83%BB%E3%83%86%E3%83%9F%E3%82%B9%E3%82%AB%E3%83%9E%E3%83%B3%E3%82%B0%E5%9C%B0%E5%9F%9F
- 2位:類似度:0.0203389830508
- .jp
https://ja.wikipedia.org/wiki/.jp
- 3位:類似度:0.0203217612193
- .shimane.jp
https://ja.wikipedia.org/wiki/.shimane.jp
- 4位:類似度:0.0203217612193
- .okinawa.jp
https://ja.wikipedia.org/wiki/.okinawa.jp
- 5位:類似度:0.0203217612193
- .chiba.jp
https://ja.wikipedia.org/wiki/.chiba.jp
++++++++++++++++++++++
検索結果:アフリカ人 アイデンティティ 競争的資本主義体制 階級闘争
++++++++++++++++++++++
- 1位:類似度:0.017993795243
- アフリカ社会主義
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%95%E3%83%AA%E3%82%AB%E7%A4%BE%E4%BC%9A%E4%B8%BB%E7%BE%A9
- 2位:類似度:0.0109634551495
- アフリカ自由ネットワーク
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%95%E3%83%AA%E3%82%AB%E8%87%AA%E7%94%B1%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF
- 3位:類似度:0.00844594594595
- アフリカ開発のための新パートナーシップ
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%95%E3%83%AA%E3%82%AB%E9%96%8B%E7%99%BA%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E6%96%B0%E3%83%91%E3%83%BC%E3%83%88%E3%83%8A%E3%83%BC%E3%82%B7%E3%83%83%E3%83%97
- 4位:類似度:0.00833333333333
- アフリカ連合の旗
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%95%E3%83%AA%E3%82%AB%E9%80%A3%E5%90%88%E3%81%AE%E6%97%97
- 5位:類似度:0.008203125
- アフリカ中央銀行
https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%95%E3%83%AA%E3%82%AB%E4%B8%AD%E5%A4%AE%E9%8A%80%E8%A1%8C
Redisを操作するプログラムを綺麗に書けると気持ちいい。Wikipediaからの情報取得は、DBPediaを利用する方法もあるみたいです。