- Notifications
You must be signed in to change notification settings - Fork1
GINK03/minimal-search-engine
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
GitHubのコードを参照してください[https://github.com/GINK03/minimal-search-engine:embed]
様々なサイトを巡回する必要があり、requestsが文字コードの推論を高確率で失敗するので、nkf をlinux環境で入れている必要があります。
$sudo apt install nkf$which nkf/usr/bin/nkf
Mecabも入れます
$ sudo apt install mecab libmecab-dev mecab-ipadic$ sudo apt install mecab-ipadic-utf8$ sudo apt install python-mecab$ pip3 install mecab-python3$ git clone --depth 1 https://github.com/neologd/mecab-ipadic-neologd.git$ ./bin/install-mecab-ipadic-neologd -n残りの依存をインストールします
$pip3 install -r requirements.txt基本的にGitHubのコードをUbuntu等のLinuxでAから順に実行してもらえば、再現できます。
クローラ（スクレイパー）はやろうと思えば無限に取得してしまうので、適当にSEEDを決めて、適当な時間で終了することを前提としていています。
A. クローリング
B. クローリングしたHTMLを, title, description, body, hrefsをパースしデータを整形する
C. IDF辞書の作成
D. TFIDFのデータを作成
F. 転置したurl, hrefの対応を作成(単純な被参照量の特徴量)
G. 非参照数のカウントと、PageRankのための学習データの作成
H. URLとtfidfのウェイトの転置インデックスを作成
I. hash化されたURLと実際のURLの対応表の作成
J. PageRankの学習
K. 検索のインターフェース
特定のドメインによらず、網羅的にクローリングしていきます。ブログサイトをシードとしてドメインを限定せずどこまでも深く潜っていきます。
多様なサイトをクロールするがとても重いので、自作した分散可能なKVSをバックエンドのDBと利用しています。SQLLiteなどだとファイルが壊れやすく、LevelDB等だとシングルアクセスしかできません。
Aで取得したデータは大きすぎるので、Bのプロセスで、tfidfでの検索の主な特徴量となる、"title", "description", "body"を取り出します。
また、そのページが参照している外部のURLをすべてパースします。
soup=BeautifulSoup(html,features='lxml')forscriptinsoup(['script','style']):script.decompose()title=soup.title.textdescription=soup.find('head').find('meta', {'name':'description'})ifdescriptionisNone:description=''else:description=description.get('content')body=soup.find('body').get_text()body=re.sub('\n',' ',body)body=re.sub(r'\s{1,}',' ',body)
BeautifulSoupでシンプルに処理することができる.
頻出する単語の重要度を下げるために、各単語がどの程度のドキュメントで参照されているかをカウントします。
B, Cのデータを利用して、TFIDFとして完成させますtitledescriptionbodyはそれぞれ重要度が異なっており、title :description :body =1 :1 :0.001
として処理しました。
# title desc weight = 1text=arow.title+arow.descriptiontext=sanitize(text)forterminm.parse(text).strip().split():ifterm_freq.get(term)isNone:term_freq[term]=0term_freq[term]+=1# title body = 0.001text=arow.bodytext=sanitize(text)forterminm.parse(text).strip().split():ifterm_freq.get(term)isNone:term_freq[term]=0term_freq[term]+=0.001# ここのweightを 0.001 のように小さい値を設定する
昔良くあった、URLのリンクを色んな所から与えるとSEOができるということを知っていたので、どの程度外部から被参照されているか知るため、このような処理を行います
Fで作成したデータをもとに、networkxというライブラリでPageRankのノードのウェイトを学習可能なので、学習用データを作成します
このようなデータセットが入力として望まれます(右のハッシュがリンク元、左のハッシュがリンク先)
d2a88da0ca550a8b 37a3d49657247e61d2a88da0ca550a8b 6552c5a8ff9b2470d2a88da0ca550a8b 3bf8e875fc951502d2a88da0ca550a8b 935b17a90f5fb6527996001a6e079a31 aabef32c9c8c4c13d2a88da0ca550a8b e710f0bdab0ac500d2a88da0ca550a8b a4bcfc4597f138c74cd5e7e2c81108be 7de6859b50d1eed2最もシンプルな単語のみでの検索に対応できるように、単語からURLをすぐ検索できるindexを作ります
出力が、単語（のハッシュ値）ごとにテキストファイルが作成されて、URLのハッシュ ,weight(tfidf) ,refnum(被参照数) のファイルが具体的な転置インデックスのファイルになります
0010c40c7ed2c240 0.000029752 4000ca0244339eb34 0.000029773 00017a9b7d83f5d24 0.000029763 000163826057db7c3 0.000029773 0URLはそのままメモリ上に持つとオーバーフローしてしまうので、sha256をつかって先頭の16文字だけを使った小さいhash値とみなすことで100万オーダーのドキュメントであってもある程度実用に耐えうる検索が可能になります。
Gで作成したデータを学習してURLにPageRankの値を学習します。
networkxを用いれば凄くシンプルなコードで学習する事ができます
import networkx as nximport jsonG = nx.read_edgelist('tmp/to_pagerank.txt', nodetype=str)# ノード数とエッジ数を出力print(nx.number_of_nodes(G))print(nx.number_of_edges(G))print('start calc pagerank')pagerank = nx.pagerank(G)print('finish calc pagerank')json.dump(pagerank, fp=open('tmp/pagerank.json', 'w'), indent=2)検索IFを提供
$python3 K001_search_query.py(ここで検索クエリを入力)
例
$python3 K001_search_query.pyふわふわ hurl weight refnum weight_norm url pagerank weight*refnum_score+pagerank9276 36b736bccbbb95f2 0.000049 1 1.000000 https://bookwalker.jp/dea270c399-d1c5-470e-98bd-af9ba8d8464a/ 0.000146 1.0096952783 108a6facdef1cf64 0.000037 0 0.758035 http://blog.livedoor.jp/usausa_life/archives/79482577.html 1.000000 0.99549832712 c3ed3d4afd05fc43 0.000045 1 0.931093 https://item.fril.jp/bc7ae485a59de01d6ad428ee19671dfa 0.000038 0.940083...
"雷ちゃん"等で検索すると、ほしい情報がおおよそちゃんと上に来るようにチューニングすることができました。
Pixivについては明示的にクローリング先に設定していないが、Aのクローラがどんどんとリンクをたどりインデックスを作成した結果で、自動で獲得したものです。
"洒落怖"など、他のクエリでも望んだ結果が帰ってきています。
手でいろいろ試してみて、良さそうなスコアはこのような感じなりました。（私が正解データです）
About
最小のサーチエンジン/PageRank/tf-idf
Topics
Resources
Uh oh!
There was an error while loading.Please reload this page.
Stars
Watchers
Forks
Releases
Packages0
Uh oh!
There was an error while loading.Please reload this page.