![1分で作るpython製の検索エンジン
def?add_text(text:?str):
????with?open("db.txt",?"a")?as?f:
????????f.write(text?+?"n")
def?search(keyword:?str):
????with?open("db.txt",?"r")?as?f:
????????return?[l.strip()?for?l?in?f?if?keyword?in?l]
if?__name__?==?"__main__":
????texts?=?[
????????"Beautiful?is?better?than?ugly.",
????????"Explicit?is?better?than?implicit.",
????????"Simple?is?better?than?complex."
????]
????for?text?in?texts:
????????add_text(text)
????results?=?search("Simple")
????for?result?in?results:
????????print(result)](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-11-320.jpg)
![転置インデックスのインデックス単位
? レコード単位転置インデックス
? 単語と単語を含む文章(文章id)をリストして持つ
? i.g. Python: [1, 2, 3, 5, 7, 10]
? メリット: シンプルで実装しやすい。ディスク容量が少ない。
? デメリット: 機能性が乏しい
? 単語単位転置インデックス
? 単語と単語を含む文章(文章id)+ αの情報(i.g. 単語の出現位置)
? i.g. Python: [1:0, 2:1, 2:10, 7:1]
? メリット: 機能性が高い。例えばフレーズ検索ができる。
? デメリット: ディスク容量が多い。
? ※: 「情報検索の基礎」共立出版](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-15-320.jpg)
![転置インデックス
? pythonではdictionary
? keyが一致しなければ値は取得できない
? どういう単位でインデックスを作成するかが重要
転置インデックス
Python: [1, 2, 3, 5, 7, 10]
Python ?-> ○
python ?-> ?
Py ?-> ?
パイソン ?-> ?](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-16-320.jpg)
![Analyzer処理
Char ?lter
Tokenizer
Token ?lter
<h1>Simple is better than complex.</h1>
simple is better than complex
[ simple , is , better , than , complex ]
[ simple , is , better->good , than , complex ]
[ simple , good , than , complex ]
Text
Tokens
Analyzer](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-19-320.jpg)
![Char?lter
? 共通のインターフェイスを作成
? 正規表現でhtmlタグを除去
? アルファベットをlowercaseに変換
class?CharacterFilter:
????@classmethod
????def?filter(cls,?text:?str):
????????raise?NotImplementedError
class?HtmlStripFilter(CharacterFilter):
????@classmethod
????def?filter(cls,?text:?str):
????????html_pattern?=?re.compile(r"<[^>]*?>")
????????return?html_pattern.sub("",?text)
class?LowercaseFilter(CharacterFilter):
????@classmethod
????def?filter(cls,?text:?str):
????????return?text.lower()](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-27-320.jpg)
![Tokenizer
? 共通のインターフェイスを準備
? 形態素解析にはJanomeを使用
? 注意
? JanomeのTokenizerオブジェクトの
初期化はコストが高いため，インスタ
ンスを使い回す。(※)
from?janome.tokenizer?import?Tokenizer?
tokenizer?=?Tokenizer()
class?BaseTokenizer:
????@classmethod
????def?tokenize(cls,?text):
????????raise?NotImplementedError
class?JanomeTokenizer(BaseTokenizer):
????@classmethod
????def?tokenize(cls,?text):
????????return?(t?for?t?in?cls.tokenizer.tokeniz
e(text))
class?WhitespaceTokenizer(BaseTokenizer):
????@classmethod
????def?tokenize(cls,?text):
????????return?(t[0]?for?t?in?re.finditer(r"[^?
trn]+",?text))
※1: https://github.com/mocobeta/janome
※2: https://mocobeta.github.io/janome/#tokenizer](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-28-320.jpg)
![Token?lter
? POSFilter
? 特定の品詞を除外する
? janomeのtokenオブジェクトの
part_of_speechで判定
class?POSFilter(TokenFilter):
????"""
????日本語の助詞/記号を除くフィルター
????"""
????@classmethod
????def?filter(cls,?token):
????????"""
????????in:?janome?token
????????"""
????????stop_pos_list?=?("助詞",?"副詞",?"記号")
????????if?any([token.part_of_speech.startswith(pos)?for
?pos?in?stop_pos_list]):
????????????return?None
????????return?token](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-31-320.jpg)
![Analyzer
? Baseclass
? クラス変数で指定できるようにする
? tokenizer,
? char ?ler,
? token_?lter
? ?lterは複数指定するため配列
? 前から順番に処理していく
class?Analyzer:
????tokenizer?=?None
????char_filters?=?[]
????token_filters?=?[]
????@classmethod
????def?analyze(cls,?text:?str):
????????text?=?cls._char_filter(text)
????????tokens?=?cls.tokenizer.tokenize(text)
????????filtered_token?=?(cls._token_filter(token)?for?t
oken?in?tokens)
????????return?[parse_token(t)?for?t?in?filtered_token?i
f?t]
????@classmethod
????def?_char_filter(cls,?text):
????????for?char_filter?in?cls.char_filters:
????????????text?=?char_filter.filter(text)
????????return?text
????@classmethod
????def?_token_filter(cls,?token):
????????for?token_filter?in?cls.token_filters:
????????????token?=?token_filter.filter(token)
????????return?token](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-32-320.jpg)
![Analyzer
? 個別のAnalyzer
? 日本語用のJapaneseTokenizer
? 英語用のEnglishTokenizer
? かんたんに別のAnalyzerも作成可能
class?JapaneseAnalyzer(Analyzer):
????tokenizer?=?JanomeTokenizer
????char_filters?=?[HtmlStripFilter,?LowercaseFilter]
????token_filters?=?[StopWordFilter,?POSFilter, Stemmer]
class?EnglishAnalyzer(Analyzer):
????tokenizer?=?WhitespaceTokenizer
????char_filters?=?[HtmlStripFilter,?LowercaseFilter]
????token_filters?=?[StopWordFilter,?Stemmer]](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-33-320.jpg)
![Indexer
? 文章を受け取り転置インデックスを作成
? メモリ上に一時的な転置インデックス
(dictionay)で保持
? メモリ上に一定数の転置インデックスが
溜まったらストレージに保存
class?InvertedIndex:
????def?__init__(
????????self,?token_id:?int,?token:?str,?postings_list=[
],?docs_count=0
????)?->?None:
????????self.token_id?=?token_id
????????self.token?=?token
????????self.postings_list?=?[]
????????self.__hash_handle?=?{}
????????self.docs_count?=?0
def?add_document(doc:?str):
????"""
????ドキュメントをデータベースに追加し転置インデックスを構築する
????"""
????if?not?doc:
????????return
????#?#?文書IDと文章内容を基にミニ転置インデックス作成
????text_to_postings_lists(doc)
????#?#?#?一定数のドキュメントがミニ転置インデックスが溜まったら
マージ
????if?len(TEMP_INVERT_INDEX)?>=?LIMIT:
????????for?inverted_index?in?TEMP_INVERT_INDEX.values()
:
????????????save_index(inverted_index)](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-35-320.jpg)
![Indexer
? ポスティングリストの作成
? analyzerでtokenを作成
? スコア計算のため文書中のトークン総数をあ
らかじめ計算しておく
? 「単語単位転置インデックス」作成
? フレーズ検索をしないため
? ただし、スコア計算のためそのトークンが文
書中にいくつあるか計算してインデックスに
もっておく
? Python: [doc1:2, doc2:1]
def?text_to_postings_lists(text)?->?list:
????"""
????文章単位の転置リストを作る
????"""
????tokens?=?JapaneseAnalyzer.analyze(text)
????token_count?=?len(tokens)
????document_id?=?save_document(text,?token_count)
????cnt?=?Counter(tokens)
????for?token,?c?in?cnt.most_common():
????????token_to_posting_list(token,?document_id,?c)
def?token_to_posting_list(token:?str,?document_id:?int,?
token_count:?int):
????"""
????tokenからposting?listを作る
????"""
????token_id?=?get_token_id(token)
????index?=?TEMP_INVERT_INDEX.get(token_id)
????if?not?index:
????????index?=?InvertedIndex(token_id,?token)
????posting?=?"{}:
{}".format(str(document_id),?str(token_count))
????index.add_posting(posting)
????TEMP_INVERT_INDEX[token_id]?=?index](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-36-320.jpg)
![Indexer作成イメージ
? document
? doc1:「私は私です。」
? doc2:「私とpython。」
? Token
? token1: 私
? token2: python
? トークン数
? doc1: 2
? doc2: 2
? ポスティングリスト
? Python: [2:1]
? 私: [1:2, 2:1]](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-37-320.jpg)
![Searcher
? queryを受け取って
? クエリのパース(Parser / Analyzer)
? 結果のdoc_idを取得(Merger)
? 文章をストレージから取得(Fetcher)
? スコア順に並び替える(Sorter)
def?search_by_query(query):
????if?not?query:
????????return?[]
????#?parse
????parsed_query?=?tokenize(query)
????parsed_query?=?analyzed_query(parsed_query)
????rpn_tokens?=?parse_rpn(parsed_query)
????#?merge
????doc_ids,?query_postings?=?merge(rpn_tokens)
????print(doc_ids,?query_postings)
????#?fetch
????docs?=?[fetch_doc(doc_id)?for?doc_id?in?doc_ids]
????#?sort
????sorted_docs?=?sort(docs,?query_postings)
????return?[_parse_doc(doc)?for?doc,?_?in?sorted_docs]](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-47-320.jpg)
![Parser
import?re
REGEX_PATTERN?=?r"s*(d+|w+|.)"
SPLITTER?=?re.compile(REGEX_PATTERN)
LEFT?=?True
RIGHT?=?False
OPERATER?=?{"AND":?(3,?LEFT),?"OR":?(2,?LEFT),?"NOT":?(1
,?RIGHT)}
def?tokenize(text):
????return?SPLITTER.findall(text)
def?parse_rpn(tokens:?list):
???#?アルゴリズムの実装
? アルゴリズムを実装
? 中置記法を後置記法にするだけなので実装
するのは文字列と演算子,括弧のみ
? 正規表現でスペースと括弧で分割
? i.g. [ A , AND , ( , B , OR , C , ) ]
? 利用するオペレーターと、その優先度、
結合方法を指定
? 優先度:
? NOT > OR > AND
? 結合
? AND, OR: 左結合
? NOT: 右結合
? 「A AND (B OR C)」
? ?→?['A', 'B', 'C', 'OR', 'AND']](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-52-320.jpg)
![Analyzer
? 転置インデックス作成時に辞書に使っ
たtokenで検索する必要がある
? Index時に使ったAnalyzerをそのまま使っ
てもOK
? JapaneseTokenizerとEnglishTokenizer
に対応する
? 検索時には英単語で検索
? Whitespace tokenizerは考慮しない
? 今回は分割されたトークンをOR検索
として扱う
? 「機械学習 AND python」
? →「機械 OR 学習 AND python」
? 逆ポーランド記法変換前にAnalyzeす
る
def?analyzed_query(parsed_query):
????return_val?=?[]
????for?q?in?parsed_query:
????????if?q?in?OPRS:
????????????return_val.append(q)
????????else:
????????????analyzed_q?=?JapaneseAnalyzer.analyze(q)
????????????if?analyzed_q:
????????????????tmp?=?"?OR?".join(analyzed_q)
????????????????return_val?+=?tmp.split("?")
????return?return_val](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-54-320.jpg)
![逆ポーランド記法評価
? 作成した逆ポーランド記法を評価していく
? 手順
? 「3 4 + 1 2 - *」:(3 + 4) * (1-2)の場合
1. (被演算子の場合) 演算子(３)をスタックに積む. stack: [３]
2. (被演算子の場合) 演算子(４)をスタックに積む: stack: [３, ４]
3. (演算子の場合) トップ２つをスタックから取り出す: stack[]
4. 計算(３＋４)してスタックに積む: stack: [７]
5. (被演算子の場合) 演算子(１)をスタックに積む. stack: [７,１]
6. (被演算子の場合) 演算子(２)をスタックに積む: stack: [７,１,２]
7. (演算子の場合) トップ２つをスタックから取り出す: stack[７]
8. 計算(１- ２)してスタックに積む: stack: [７, -１]
9. (演算子の場合) トップ２つをスタックから取り出す: stack[]
10. 計算(７ * -１)してスタックに積む: stack: [-７]](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-56-320.jpg)
![Merge
? 逆ポーランド記法評価手順通りに実装
? tokenが被演算子=トークンの場合に
ポスティングリストを取得後stockに
追加
? tokenが演算子の場合は、stockから
top２つを取り出してmerge後stock
に追加
? ポスティングリストはスコア計算よう
にdictionaryで管理
def?merge(tokens:?list):
????target_posting?=?{}
????stack?=?[]
????for?token?in?tokens:
????????if?token?not?in?OPRS:
????????????token_id?=?get_token_id(token)
????????????postings_list?=?fetch_postings_list(token_id
)
????????????#?score計算用に保持
????????????target_posting[token]?=?postings_list
????????????#?doc_idのみをstackに追加
????????????doc_ids?=?set([p[0]?for?p?in?postings_list])
????????????stack.append(doc_ids)
????????#?tokenがoperaterだった場合
????????else:
????????????if?not?stack:
????????????????raise
????????????if?len(stack)?==?1:
????????????????#?NOTのみ許容
????????????????if?token?==?"NOT":
????????????????????#?NOTの処理
????????????????????return?not_doc_ids,?{}
????????????????else:
????????????????????raise
????????????doc_ids1?=?stack.pop()
????????????doc_ids2?=?stack.pop()
????????????stack.append(merge_posting(token,?doc_ids1,?
doc_ids2))](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-58-320.jpg)
![Sorter
? スコア計算に使う値はほぼインデック
ス時に集計しているものを使う
? 1文書中の検索トークン数(t)
? postingで保持
? 1: 2
? 1文書中のトークン数(T)
? Documents保存時に一緒に保存
? doc.token_count
? 検索トークン(t)を含む文書数(D)
? tのポスティングリストの長さ
? 全文書数(A)
? Documents tableのカウント
def?sort(doc_ids,?query_postings):
????docs?=?[]
????all_docs?=?count_all_docs()
????for?doc_id?in?doc_ids:
????????doc?=?fetch_doc(doc_id)
????????doc_tfidf?=?0
????????for?token,?postings_list?in?query_postings.items
():
????????????idf?=?math.log10(all_docs?/?len(postings_lis
t))?+?1
????????????posting?=?[p?for?p?in?postings_list?if?p[0]?
==?doc.id]
????????????if?posting:
????????????????tf?=?round(posting[0]
[1]?/?doc.token_count,?2)
????????????else:
????????????????tf?=?0
????????????token_tfidf?=?tf?*?idf
????????????doc_tfidf?+=?token_tfidf
????????docs.append((doc,?doc_tfidf))
????return?sorted(docs,?key=lambda?x:?x[1],?reverse=True
)](https://image.slidesharecdn.com/fulltextsearchfirststep-190917045217/85/self-made-Fulltext-search-first_step-65-320.jpg)
self made Fulltext search first_step
- 2. 自己紹介 加藤 遼(Ryo Kato) @_ryook サーバーサイド/API / 検索 python(Django)/Elasticsearch
- 5. この発表について ? 入門 自作検索エンジン ? 検索エンジンを自作することに入門した話 ? 誰しも一度は検索エンジンを作りたいと思うはず ? 初めて検索エンジンを作るときの知見を一方的に共有するトーク
- 6. 対象 ? 全文検索のことを知らない / なんとなく知っている人 ? 検索に興味がある人 ? 検索エンジンを作ってみたい人
- 7. 話さないこと ? Elasticsearch / Solrといった全文検索エンジンを使った検索アプリケーション の話?pythonで使うtips ? 知りたい人はPyConJP2018の発表(※1)見てください or 検索技術勉強会へ ? もしくは是非空き時間に話しましょう ? クローリング / スクレイピングについて ? 気になる人は、本を読む or @shinyorkさん(※2) @vaaaaanquishさん(※3)のブログを見て ください ? ※1: https://slideship.com/users/@iktakahiro/presentations/2018/09/DRJxjKfBFEGSRcvYjCA88f/ ? ※2: https://shinyorke.hatenablog.com/entry/kowakunai-crawl-and-scraping ? ※3: https://vaaaaaanquish.hatenablog.com/entry/2017/06/25/202924
- 8. 目次 ? 全文検索について ? シンプルな検索エンジンを作る ? さらなる改善について ? まとめ
- 9. 全文検索について 全文検索とは？ ? 検索の対象が「テキストからなる文章の全部の文」である場合に、その文章に対 して検索を行うこと (※) 検索エンジンとは？ ? 文章の集合から、単語や質問などからなる情報要求に適合する文章を見つける(検 索する)ためのシステムやソフトウェアの総称 (※) ※ 「検索エンジン自作入門」技術評論社
- 10. 1分で作るpython製の検索エンジン ? 機能 ? テキストの追加ができる ? キーワード検索ができる
- 12. 全文検索について Grep型(※1) ? 線形走査を行う ? 現在のコンピューターでは、シェークスピア全集(約100万語)規模の文章に対 しての単純なクエリに対してはこれで充分という説もある(※2) 牽引(インデックス)型(※1) ? あらかじめ検索対象となる文書群を走査して牽引データを作っておく ベクトル型 ? 特徴ベクトルを作成してベクトル間の距離を計算 ※1: https://ja.wikipedia.org/wiki/%E5%85%A8%E6%96%87%E6%A4%9C%E7%B4%A2 ※2:「情報検索の基礎」共立出版
- 13. 牽引(インデックス)型 ? あらかじめ検索対象の文書を走査して、牽引データを準備しておく方法 ? 牽引ファイルを作成することをインデクシング、生成されるデータをインデック スという ? 牽引の作り方は様々あるが、一般的なのは転置インデックス ? 多くの全文検索エンジンで採用されている ? イメージは本の後ろについている牽引 ? キーワードとページ
- 14. 転置インデックス(逆インデックス) ? 単語とそれが含まれている文章のマッピングを保持するインデックス型のデータ 構造(※) ? 辞書とポスティングで構成される Python Elasticsearch 1, 2, 3, 5, 7, 10 1, 2, 10, 12, 15 辞書 ポスティング ポスティングリスト ポスティング v ? ※: wikipedia ? ※図: 「情報検索の基礎」共立出版 v 転置インデックス
- 15. 転置インデックスのインデックス単位 ? レコード単位転置インデックス ? 単語と単語を含む文章(文章id)をリストして持つ ? i.g. Python: [1, 2, 3, 5, 7, 10] ? メリット: シンプルで実装しやすい。ディスク容量が少ない。 ? デメリット: 機能性が乏しい ? 単語単位転置インデックス ? 単語と単語を含む文章(文章id)+ αの情報(i.g. 単語の出現位置) ? i.g. Python: [1:0, 2:1, 2:10, 7:1] ? メリット: 機能性が高い。例えばフレーズ検索ができる。 ? デメリット: ディスク容量が多い。 ? ※: 「情報検索の基礎」共立出版
- 16. 転置インデックス ? pythonではdictionary ? keyが一致しなければ値は取得できない ? どういう単位でインデックスを作成するかが重要 転置インデックス Python: [1, 2, 3, 5, 7, 10] Python ?-> ○ python ?-> ? Py ?-> ? パイソン ?-> ?
- 17. インデックスの抽出手法 ? 単語分割(トークナイズ) ? White space ? 形態素解析(日本語) ? N-gram ? シグネチャ ? 接尾辞配列 ? etc
- 18. インデックス生成 ? インデックスの生成時にはトークナイズだけでなくテキストに処理を加える必要 もある ? どういう検索エンジンにするか依存する ? i.g. HTMLを検索するエンジン ? googleのようにコンテンツのみを対象にする場合 ? HTMLタグは不要?→??HTMLタグを除去する ? Githubのようにコードを対象にする場合 ? HTMLタグは必要
- 19. Analyzer処理 Char ?lter Tokenizer Token ?lter <h1>Simple is better than complex.</h1> simple is better than complex [ simple , is , better , than , complex ] [ simple , is , better->good , than , complex ] [ simple , good , than , complex ] Text Tokens Analyzer
- 23. シンプルな検索エンジンを作る ? 要件 ? pyconjp 2019のトークを検索できる ? Titleと詳細 ? 論理検索(and or not)に対応 ? 結果はスコア(TFIDF)順に返す ? フレーズ検索は対応しない ? 複数フィールドの検索は対応しない ? ドキュメントの更新はしない ? 途中でドキュメントの追加をしない
- 24. シンプルな検索エンジンを作る Analyzer Indexer Storage Parser Analyzer Searcher(fetch / merge) Sorter Document Query Results 全体像
- 25. シンプルな検索エンジンを作る Analyzer Indexer Storage Parser Analyzer Searcher(fetch / merge) Sorter Document Query Results
- 26. Analyzer実装 ? 英語と日本語それぞれのAnalyzerを作成 ? 共通 ? htmlタグ除外 ? ストップワード除外 ? アルファベットはすべて小文字に変換 ? steaming処理 ? i.g. dogs → dog ? 日本語 ? 形態素解析分割 ? 助詞?副詞?記号除外 ? 英語 ? White space分割 ? 助詞等はストップワードで対応
- 27. Char?lter ? 共通のインターフェイスを作成 ? 正規表現でhtmlタグを除去 ? アルファベットをlowercaseに変換 class?CharacterFilter: ????@classmethod ????def?filter(cls,?text:?str): ????????raise?NotImplementedError class?HtmlStripFilter(CharacterFilter): ????@classmethod ????def?filter(cls,?text:?str): ????????html_pattern?=?re.compile(r"<[^>]*?>") ????????return?html_pattern.sub("",?text) class?LowercaseFilter(CharacterFilter): ????@classmethod ????def?filter(cls,?text:?str): ????????return?text.lower()
- 28. Tokenizer ? 共通のインターフェイスを準備 ? 形態素解析にはJanomeを使用 ? 注意 ? JanomeのTokenizerオブジェクトの 初期化はコストが高いため，インスタ ンスを使い回す。(※) from?janome.tokenizer?import?Tokenizer? tokenizer?=?Tokenizer() class?BaseTokenizer: ????@classmethod ????def?tokenize(cls,?text): ????????raise?NotImplementedError class?JanomeTokenizer(BaseTokenizer): ????@classmethod ????def?tokenize(cls,?text): ????????return?(t?for?t?in?cls.tokenizer.tokeniz e(text)) class?WhitespaceTokenizer(BaseTokenizer): ????@classmethod ????def?tokenize(cls,?text): ????????return?(t[0]?for?t?in?re.finditer(r"[^? trn]+",?text)) ※1: https://github.com/mocobeta/janome ※2: https://mocobeta.github.io/janome/#tokenizer
- 30. Token?lter ? Steming処理 ? 単語の語幹を取り出す処理 ? i.g. 「dogs」→「dog」 ? nltk.stem パッケージを利用(※) from?nltk.stem.porter?import?PorterStemmer ps?=?PorterStemmer() class?Stemmer(TokenFilter): ????@classmethod ????def?filter(cls,?token:?str): ????????if?token: ????????????return?ps.stem(token) ※http://www.nltk.org/api/nltk.stem.html
- 31. Token?lter ? POSFilter ? 特定の品詞を除外する ? janomeのtokenオブジェクトの part_of_speechで判定 class?POSFilter(TokenFilter): ????""" ????日本語の助詞/記号を除くフィルター ????""" ????@classmethod ????def?filter(cls,?token): ????????""" ????????in:?janome?token ????????""" ????????stop_pos_list?=?("助詞",?"副詞",?"記号") ????????if?any([token.part_of_speech.startswith(pos)?for ?pos?in?stop_pos_list]): ????????????return?None ????????return?token
- 32. Analyzer ? Baseclass ? クラス変数で指定できるようにする ? tokenizer, ? char ?ler, ? token_?lter ? ?lterは複数指定するため配列 ? 前から順番に処理していく class?Analyzer: ????tokenizer?=?None ????char_filters?=?[] ????token_filters?=?[] ????@classmethod ????def?analyze(cls,?text:?str): ????????text?=?cls._char_filter(text) ????????tokens?=?cls.tokenizer.tokenize(text) ????????filtered_token?=?(cls._token_filter(token)?for?t oken?in?tokens) ????????return?[parse_token(t)?for?t?in?filtered_token?i f?t] ????@classmethod ????def?_char_filter(cls,?text): ????????for?char_filter?in?cls.char_filters: ????????????text?=?char_filter.filter(text) ????????return?text ????@classmethod ????def?_token_filter(cls,?token): ????????for?token_filter?in?cls.token_filters: ????????????token?=?token_filter.filter(token) ????????return?token
- 33. Analyzer ? 個別のAnalyzer ? 日本語用のJapaneseTokenizer ? 英語用のEnglishTokenizer ? かんたんに別のAnalyzerも作成可能 class?JapaneseAnalyzer(Analyzer): ????tokenizer?=?JanomeTokenizer ????char_filters?=?[HtmlStripFilter,?LowercaseFilter] ????token_filters?=?[StopWordFilter,?POSFilter, Stemmer] class?EnglishAnalyzer(Analyzer): ????tokenizer?=?WhitespaceTokenizer ????char_filters?=?[HtmlStripFilter,?LowercaseFilter] ????token_filters?=?[StopWordFilter,?Stemmer]
- 34. シンプルな検索エンジンを作る Analyzer Indexer Storage Parser Analyzer Searcher(fetch / merge) Sorter Document Query Results
- 35. Indexer ? 文章を受け取り転置インデックスを作成 ? メモリ上に一時的な転置インデックス (dictionay)で保持 ? メモリ上に一定数の転置インデックスが 溜まったらストレージに保存 class?InvertedIndex: ????def?__init__( ????????self,?token_id:?int,?token:?str,?postings_list=[ ],?docs_count=0 ????)?->?None: ????????self.token_id?=?token_id ????????self.token?=?token ????????self.postings_list?=?[] ????????self.__hash_handle?=?{} ????????self.docs_count?=?0 def?add_document(doc:?str): ????""" ????ドキュメントをデータベースに追加し転置インデックスを構築する ????""" ????if?not?doc: ????????return ????#?#?文書IDと文章内容を基にミニ転置インデックス作成 ????text_to_postings_lists(doc) ????#?#?#?一定数のドキュメントがミニ転置インデックスが溜まったら マージ ????if?len(TEMP_INVERT_INDEX)?>=?LIMIT: ????????for?inverted_index?in?TEMP_INVERT_INDEX.values() : ????????????save_index(inverted_index)
- 36. Indexer ? ポスティングリストの作成 ? analyzerでtokenを作成 ? スコア計算のため文書中のトークン総数をあ らかじめ計算しておく ? 「単語単位転置インデックス」作成 ? フレーズ検索をしないため ? ただし、スコア計算のためそのトークンが文 書中にいくつあるか計算してインデックスに もっておく ? Python: [doc1:2, doc2:1] def?text_to_postings_lists(text)?->?list: ????""" ????文章単位の転置リストを作る ????""" ????tokens?=?JapaneseAnalyzer.analyze(text) ????token_count?=?len(tokens) ????document_id?=?save_document(text,?token_count) ????cnt?=?Counter(tokens) ????for?token,?c?in?cnt.most_common(): ????????token_to_posting_list(token,?document_id,?c) def?token_to_posting_list(token:?str,?document_id:?int,? token_count:?int): ????""" ????tokenからposting?listを作る ????""" ????token_id?=?get_token_id(token) ????index?=?TEMP_INVERT_INDEX.get(token_id) ????if?not?index: ????????index?=?InvertedIndex(token_id,?token) ????posting?=?"{}: {}".format(str(document_id),?str(token_count)) ????index.add_posting(posting) ????TEMP_INVERT_INDEX[token_id]?=?index
- 37. Indexer作成イメージ ? document ? doc1:「私は私です。」 ? doc2:「私とpython。」 ? Token ? token1: 私 ? token2: python ? トークン数 ? doc1: 2 ? doc2: 2 ? ポスティングリスト ? Python: [2:1] ? 私: [1:2, 2:1]
- 40. ポスティングリストはid順にソートする ? 検索の効率的に行うため ? 今回の実装では触れない ? i.g. スキップポインター(※) ? 今回はupdateしないのでappendするだけでOK ※: 「情報検索の基礎」共立出版
- 41. メモリとストレージの転置インデックス ? 全文検索エンジンで性能のボトルネックの多くをストレージのi/oが占める ? メモリ使用量と速度のトレードオフ ? メモリ上においておくほうが性能はいいがメモリ使用率が上がる ? ストレージに頻繁にアクセスするようにすればメモリ使用率は下がるが遅くな る ※: 「情報検索の基礎」共立出版 ※ 「検索エンジン自作入門」技術評論社
- 42. シンプルな検索エンジンを作る Analyzer Indexer Storage Parser Analyzer Searcher(fetch / merge) Sorter Document Query Results
- 43. Storage ? 今回sqlite3 & sqlalchemyを使用 ? なんでもいい ? NoSQLを使うと楽 ? 今回は極力pythonだけ済むようにするためsqliteを採用 ? より効率を求めるなら自分で実装する必要がある
- 44. Storage ? データベーススキーマ ? Documets tableにテキストを保存 ? 検索対象のフィールドのテキストをtext フィールドで保持しておく class?Documents(Base): ????__tablename__?=?"documents" ????id?=?Column(Integer,?primary_key=True) ????text?=?Column(String) ????token_count?=?Column(Integer) ????date?=?Column(String) ????time?=?Column(String) ????room?=?Column(String) ????title?=?Column(String) ????abstract?=?Column(String) ????speaker?=?Column(String) ????self_intro?=?Column(String) ????detail?=?Column(String) ????session_type?=?Column(String) class?Tokens(Base): ????__tablename__?=?"tokens" ????id?=?Column(Integer,?primary_key=True) ????token?=?Column(String) class?InvertedIndexDB(Base): ????__tablename__?=?"index" ????id?=?Column(Integer,?primary_key=True) ????token?=?Column(String) ????postings_list?=?Column(String) ????docs_count?=?Column(Integer) ????token_count?=?Column(Integer)
- 45. Storage ? データベース処理などのutils関数を実装 ? トークンの追加?取得 ? ドキュメントの追加?取得 ? 転置インデックスの追加?更新?取得 def?add_token(token:?str)?->?int: ????SESSION?=?get_session() ????token?=?Tokens(token=token) ????SESSION.add(token) ????SESSION.commit() ????token_id?=?token.id ????SESSION.close() ????return?token_id def?fetch_doc(doc_id): ????SESSION?=?get_session() ????doc?=?SESSION.query(Documents).filter(Documents.id?= =?doc_id).first() ????SESSION.close() ????if?doc: ????????return?doc ????else: ????????return?None
- 46. シンプルな検索エンジンを作る Analyzer Indexer Storage Parser Analyzer merge / fetch Sorter Document Query Results
- 47. Searcher ? queryを受け取って ? クエリのパース(Parser / Analyzer) ? 結果のdoc_idを取得(Merger) ? 文章をストレージから取得(Fetcher) ? スコア順に並び替える(Sorter) def?search_by_query(query): ????if?not?query: ????????return?[] ????#?parse ????parsed_query?=?tokenize(query) ????parsed_query?=?analyzed_query(parsed_query) ????rpn_tokens?=?parse_rpn(parsed_query) ????#?merge ????doc_ids,?query_postings?=?merge(rpn_tokens) ????print(doc_ids,?query_postings) ????#?fetch ????docs?=?[fetch_doc(doc_id)?for?doc_id?in?doc_ids] ????#?sort ????sorted_docs?=?sort(docs,?query_postings) ????return?[_parse_doc(doc)?for?doc,?_?in?sorted_docs]
- 48. シンプルな検索エンジンを作る Analyzer Indexer Storage Parser Analyzer Searcher(fetch / merge) Sorter Document Query Results
- 49. Parser ? ユーザーの入力クエリをパースする ? AND, OR, NOTなどの論理検索に使うオペレーターや演算子を使う場合に必要 ? 論理検索しないなら不要 ? 今回は逆ポーランド記法に変換
- 50. 逆ポーランド記法(後置記法) ? 演算子を被演算子の後ろに置く記法 (※) ? i.g. ? 「3 + 4」→「3 4 +」 ? 「(3 + 4) * (1 - 2)」→ 「3 4 + 1 2 - *」 ? 「python AND 検索」→ 「python 検索 AND」 ? メリット ? 式の評価(計算)がシンプルになる ? 先頭から評価するだけで済む ? ※: wikipedia: https://ja.wikipedia.org/wiki/ %E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6 %B3%95
- 51. 操車場アルゴリズム詳細 ? 逆ポーランド記法への変換は操車場アルゴリズムを利用 ? アルゴリズムの詳細はwikipediaの操車場アルゴリズムのページを参照 ? ※: wikipedia: https://ja.wikipedia.org/wiki/ %E6%93%8D%E8%BB%8A%E5%A0%B4%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E 3%82%BA%E3%83%A0
- 52. Parser import?re REGEX_PATTERN?=?r"s*(d+|w+|.)" SPLITTER?=?re.compile(REGEX_PATTERN) LEFT?=?True RIGHT?=?False OPERATER?=?{"AND":?(3,?LEFT),?"OR":?(2,?LEFT),?"NOT":?(1 ,?RIGHT)} def?tokenize(text): ????return?SPLITTER.findall(text) def?parse_rpn(tokens:?list): ???#?アルゴリズムの実装 ? アルゴリズムを実装 ? 中置記法を後置記法にするだけなので実装 するのは文字列と演算子,括弧のみ ? 正規表現でスペースと括弧で分割 ? i.g. [ A , AND , ( , B , OR , C , ) ] ? 利用するオペレーターと、その優先度、 結合方法を指定 ? 優先度: ? NOT > OR > AND ? 結合 ? AND, OR: 左結合 ? NOT: 右結合 ? 「A AND (B OR C)」 ? ?→?['A', 'B', 'C', 'OR', 'AND']
- 53. シンプルな検索エンジンを作る Analyzer Indexer Storage Parser Analyzer Searcher(fetch / merge) Sorter Document Query Results
- 54. Analyzer ? 転置インデックス作成時に辞書に使っ たtokenで検索する必要がある ? Index時に使ったAnalyzerをそのまま使っ てもOK ? JapaneseTokenizerとEnglishTokenizer に対応する ? 検索時には英単語で検索 ? Whitespace tokenizerは考慮しない ? 今回は分割されたトークンをOR検索 として扱う ? 「機械学習 AND python」 ? →「機械 OR 学習 AND python」 ? 逆ポーランド記法変換前にAnalyzeす る def?analyzed_query(parsed_query): ????return_val?=?[] ????for?q?in?parsed_query: ????????if?q?in?OPRS: ????????????return_val.append(q) ????????else: ????????????analyzed_q?=?JapaneseAnalyzer.analyze(q) ????????????if?analyzed_q: ????????????????tmp?=?"?OR?".join(analyzed_q) ????????????????return_val?+=?tmp.split("?") ????return?return_val
- 55. Merge Analyzer Indexer Storage Parser Analyzer Searcher(fetch / merge) Sorter Document Query Results
- 56. 逆ポーランド記法評価 ? 作成した逆ポーランド記法を評価していく ? 手順 ? 「3 4 + 1 2 - *」:(3 + 4) * (1-2)の場合 1. (被演算子の場合) 演算子(３)をスタックに積む. stack: [３] 2. (被演算子の場合) 演算子(４)をスタックに積む: stack: [３, ４] 3. (演算子の場合) トップ２つをスタックから取り出す: stack[] 4. 計算(３＋４)してスタックに積む: stack: [７] 5. (被演算子の場合) 演算子(１)をスタックに積む. stack: [７,１] 6. (被演算子の場合) 演算子(２)をスタックに積む: stack: [７,１,２] 7. (演算子の場合) トップ２つをスタックから取り出す: stack[７] 8. 計算(１- ２)してスタックに積む: stack: [７, -１] 9. (演算子の場合) トップ２つをスタックから取り出す: stack[] 10. 計算(７ * -１)してスタックに積む: stack: [-７]
- 57. 逆ポーランド記法評価 ? Merge = 逆ポーランド記法の評価 ? 逆ポーランド記法の評価は３パターン ? 「スタックに積む」、「スタックから取り出す」、「計算する」 ? 計算は２つの被演算子の評価ですむ ? ２つのトークンのポスティングリストをマージする ? スタックには、トークンから取得したポスティングリストを追加する
- 58. Merge ? 逆ポーランド記法評価手順通りに実装 ? tokenが被演算子=トークンの場合に ポスティングリストを取得後stockに 追加 ? tokenが演算子の場合は、stockから top２つを取り出してmerge後stock に追加 ? ポスティングリストはスコア計算よう にdictionaryで管理 def?merge(tokens:?list): ????target_posting?=?{} ????stack?=?[] ????for?token?in?tokens: ????????if?token?not?in?OPRS: ????????????token_id?=?get_token_id(token) ????????????postings_list?=?fetch_postings_list(token_id ) ????????????#?score計算用に保持 ????????????target_posting[token]?=?postings_list ????????????#?doc_idのみをstackに追加 ????????????doc_ids?=?set([p[0]?for?p?in?postings_list]) ????????????stack.append(doc_ids) ????????#?tokenがoperaterだった場合 ????????else: ????????????if?not?stack: ????????????????raise ????????????if?len(stack)?==?1: ????????????????#?NOTのみ許容 ????????????????if?token?==?"NOT": ????????????????????#?NOTの処理 ????????????????????return?not_doc_ids,?{} ????????????????else: ????????????????????raise ????????????doc_ids1?=?stack.pop() ????????????doc_ids2?=?stack.pop() ????????????stack.append(merge_posting(token,?doc_ids1,? doc_ids2))
- 59. Merge ? 「NOT hoge」の対応 ? 被演算子２つの評価以外の評価方法をNOT のみ許可 ? tokenが演算子の場合にstackのサイズと tokenの中身で判定 #?「NOT?hoge」対応 if?len(stack)?==?1: ????#?NOTのみ許容 ????if?token?==?"NOT": ????????#?NOTの処理 ????????doc_ids?=?stack.pop() ????????not_doc_ids?=?fetch_not_docs_id(doc_ids) ????????return?not_doc_ids,?{} ????else: ????????raise
- 60. Merge ? オペレーターをユーザーが記述しない 場合の対応 ? 「python 機械学習」 ? →「python OR 機械学習」? ? →「python AND 機械学習」? ? 今回はORを採用 ? オペレーターを記述しない = 被演算子 と評価の数が合わない ? 最後まで評価してもstackが２つ以上ある ? 全てのトークンを実装したあとにstack が1になるまでOR mergeを繰り返す for?token?in?tokens: ????#?評価処理 while?len(stack)?!=?1: ????doc_ids1?=?stack.pop() ????doc_ids2?=?stack.pop() ????stack.append(merge_posting("OR",?doc_ids1,?doc_ids2) )
- 61. Merge Analyzer Indexer Storage Parser Analyzer Searcher(fetch / merge) Sorter Document Query Results
- 62. シンプルな検索エンジンを作る Analyzer Indexer Storage Parser Analyzer Searcher(fetch / merge) Sorter Document Query Results
- 63. スコアリング ? TFIDF ? TF: term frequency () ? 文書中の単語の割合 ? 単語(t) / 文章中の単語数(T) ? iDF: invert document frequency ? 全文書中のその単語を含む文章の割合 ? log(その単語を含む文書数(D)/全文書数(A)) ? 文章中によく出てきて、他の文章にでてこないものほどスコアが高い
- 64. スコアリング ? 検索においてのIDF? ? 1キーワードだけで検索すると全文文書のIDFは同じ ? TFだけでよさそう ? ただし、AND, ORで検索したときに意味が変わってくる。 ? 複数のクエリに対する文書郡の比較のための重み付けと考える ? 「A AND B」で検索したときの文書αのTFIDF値 ? 文書αのTFIDF値 = クエリAのTFIDF + クエリBのTFIDF
- 65. Sorter ? スコア計算に使う値はほぼインデック ス時に集計しているものを使う ? 1文書中の検索トークン数(t) ? postingで保持 ? 1: 2 ? 1文書中のトークン数(T) ? Documents保存時に一緒に保存 ? doc.token_count ? 検索トークン(t)を含む文書数(D) ? tのポスティングリストの長さ ? 全文書数(A) ? Documents tableのカウント def?sort(doc_ids,?query_postings): ????docs?=?[] ????all_docs?=?count_all_docs() ????for?doc_id?in?doc_ids: ????????doc?=?fetch_doc(doc_id) ????????doc_tfidf?=?0 ????????for?token,?postings_list?in?query_postings.items (): ????????????idf?=?math.log10(all_docs?/?len(postings_lis t))?+?1 ????????????posting?=?[p?for?p?in?postings_list?if?p[0]? ==?doc.id] ????????????if?posting: ????????????????tf?=?round(posting[0] [1]?/?doc.token_count,?2) ????????????else: ????????????????tf?=?0 ????????????token_tfidf?=?tf?*?idf ????????????doc_tfidf?+=?token_tfidf ????????docs.append((doc,?doc_tfidf)) ????return?sorted(docs,?key=lambda?x:?x[1],?reverse=True )
- 66. デプロイTips ? メモリを多めにする ? 性能があがる ? Janomeがpipのビルド時に500MB 600MB程度メモリが必要(※) ? herokuは厳しい ? free?hobyは? ? Standardもおそらく? ? EC2 t2.microも? ? EC2 t2.smallは○ ? ※ https://mocobeta.github.io/janome/
- 67. DEMO DBのコード DEMO
- 68. 改善点 ? インデクシング?検索の速度改善 ? ポスティングリストの圧縮 ? 効率のいいアルゴリズムとデータ構造を使う ? 動的なインデックスの作成 ? クエリ拡張 ? フレーズ検索 ? 複数フィールド対応 ? 演算子の拡張 ? ストレージ部分(ファイルシステム)実装 ? ベクトル検索 ? 分散化 ? etc
- 69. 改善のための参考資料 ? 書籍 ? 「検索エンジン自作入門」技術評論社 ? 「情報検索の基礎」共立出版 ? 「高速文字列解析の世界」岩波書店 ? 「DeepLearning for Search」MANNING ? OSS ? 「Whoosh」 ? https://bitbucket.org/mchaput/whoosh/src/default/docs/ source/intro.rst ? 「Elasticsearch」 ? https://github.com/elastic/elasticsearch ? 「Apache Lucene」 ? http://lucene.apache.org/core/documentation.html
- 70. まとめ ? 検索エンジンの仕組みの説明から基本的な検索エンジンの実装まで説明した ? 単純に見える検索エンジンも実装すると色々考えることがある ? 勉強?趣味において車輪再発明は有意義 ? 検索エンジンを作るのは楽しい ? みんなで「ぼくのかんがえたさいきょうの検索エンジン」を作りましょう