[B! ir] haya14busaのブックマーク

再現率・適合率 - petitviolet_blog

再現率・適合率前回のエントリの引用. Precision:適合率検索結果に適合しない文書が入ってない割合 Recall:再現率適合する全ての文書の内,どれだけ拾うことが出来たかの割合計算式は以下の表を用いて Relevant Nonrelevant Retrieved tp fp Not Retrieved fn tn Precision(P) = tp / (tp + fp) Recall(R) = tp / (tp + fn) となる. PとRはトレードオフの関係である. 検索結果として全ての文書を返せば,R→1となるがP→0となる. 条件を厳しくして適合文書をほんの少しだけ返せばPは大きくなるが,Rは小さくなる. 例を挙げてみる. 文書集合内の文書の数は10コ. 検索結果として10コの文書を返す. 正解となる文書(適合文書)は4コ. 適合文書の出現順序は以下の通り. ランキン

haya14busa 2016/02/16

IR

リンク

ハクビシンにもわかる全文検索 - Qiita

高速な全文検索アルゴリズムであるFM-indexについて解説する。理解しがたい点や間違っている点があれば是非コメントで指摘してほしい。概要 FM-indexはリニアな文字列に対して検索をするアルゴリズムで、主に簡潔データ構造とBWT(およびLF mapping)という二つのアイデアから成り立っている。BWTはBurrows-Wheeler変換のことで、文字列を特殊な並び順に変換するという可逆関数である。BWTされた文字列を簡潔データ構造固有の操作をすることで、クエリ文字列の長さに比例した短い時間で文字列を探し出すのがFM-indexだ。簡潔データ構造簡潔データ構造に関してはFM-indexで必要となる二つの関数だけ説明して、詳細は次の機会に譲るとする。さて、二つの関数はともに文字列のある位置より前の部分に含まれている文字の数を数え上げるというものでrank()とrankLessTha