google/codesearch: Fast, indexed regexp search over large file treesYou signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert
Regular Expression Matching with a Trigram Index or How Google Code Search Worked
Regular Expression Matching with a Trigram Index or How Google Code Search Worked Russ Cox rsc@swtch.com January 2012 Introduction In the summer of 2006, I was lucky enough to be an intern at Google. At the time, Google had an internal tool called gsearch that acted as if it ran grep over all the files in the Google source tree and printed the results. Of course, that implementation would be fairl
HorspoolのアルゴリズムとSunday's Quick Search - 似非学問的な手記
BM法についての記事を書いたとたんに、 「最速の文字列検索アルゴリズムってなんだ？」 と思って調べまくった次第です（；＾ω＾）。この無駄な凝り性はプラスにもマイナスにも働きそうで怖い。 そしたらBM法の亜種がいくつか研究されてるみたいですね。 んで、この亜種についての一般的な話を。 （あ、BM法の記事：http://d.hatena.ne.jp/g940425/20100522/1274520718 を見てない人はわかりにくいかもです（；´・ω・`）） Boyer-Mooreのアルゴリズムの要は、「テキストのどの文字で不一致が起こったか」によって一気に先へ先へとジャンプしていくところだったわけだ。 上のテキストから下のパターンを検索するとき、 BM法では、パターンの後ろから見ていって、 初めて不一致となったこの位置に パターン中の同じ文字を合わせることでパターンの位置を何文字か（例では二文
Efficient substring searching
There are many times when programmers need to search for a substring, for example when parsing text. This is commonly referred to as searching for a needle (substring) in a haystack (the string to search in). The most straightforward way to do this is by using search functions that your language provides: C: strchr()/memchr(), strstr()/memmem() C++: string::find() Ruby: String#index or regular exp
ボイヤー-ムーア文字列検索アルゴリズム - Wikipedia
テキスト T = "ANPANMAN" に対して k = 3 から k = 8 までパターン P = "PAN" を配置した様子。この場合、k = 5 の位置で一致する。 文字列 S に対する操作を以下のように表す： S[i]： 文字列 S の i 番目の文字 S[i..j]： 文字列 S の i から j 番目までの部分文字列（i 文字目、j 文字目をそれぞれ含む） 文字列 S に含まれる文字の個数を文字列の長さと定義する。また、文字列 S の先頭を含む部分文字列をプレフィックス、末尾を含む部分文字列をサフィックスと定義する。 len(S)：S の長さ S[1..i], 1 ≤ i ≤ len(S)：S のプレフィックス S[i..len(S)], 1 ≤ i ≤ len(S)：S のサフィックス 検索文字列をパターンと呼び、P で表す。被検索文字列をテキストと呼び、T で表す。また T
Sign in - Google Accounts
Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode
Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
essential information that every serious programmer needs to know about algorithms and data structures Online content. This booksite contains tens of thousands of files, fully coordinated with our textbook and also useful as a stand-alone resource. It consists of the following elements: Excerpts. A condensed version of the text narrative, for reference while online. Lectures. Curated studio-produc
再現率・適合率 - 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コ. 適合文書の出現順序は以下の通り. ランキン
検索結果の「再現率」と「適合率」 - 大人になってからの再学習
■キーワード： 検索、システム、再現率、適合率、評価、recall、precision 動物の写真データ群から、検索システムを使って犬の写真を全て選び出したい。 どちらの検索システムが優れていると言えるだろうか。 システムA： 検索結果として50件ヒットした。すべてが犬の写真で誤りは1つもなかった。でも、データ群の中には取りこぼした犬の写真が70件あった。 システムB： 検索結果として200件ヒットした。そのうち、80件は誤りだったけど、データ群の中の犬の写真はすべて拾い出した。取りこぼしは0件だった。 どちらが優れているかは、その検索の目的によって異なる。 システムAは適合率 precision が高い。（適合率 1.0、再現率 0.41） システムBは再現率 recall が高い。（適合率 0.6、再現率 1.0） と評価される。 適合率と再現率の意味が直観的にわかるように、図を作って
charles leifer | Using SQLite Full-Text Search with Python
Using SQLite Full-Text Search with Python May 12, 2014 19:12 / peewee python search sqlite / 0 comments In this post I will show how to use SQLite full-text search with Python (and a lot of help from peewee ORM). We will see how to index content for searching, how to perform searches, and how to order search results using two ranking algorithms. Last week I migrated my site from Postgresql to SQLi
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
capm-network.com - このウェブサイトは販売用です！ - capm network リソースおよび情報
cpython/Objects/stringlib/fastsearch.h at main · python/cpython
GitHub - alexseitsinger/text-tools: Various tools for manipulating text
サービス終了のお知らせ
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Text/Matching-Boyer-Moore2.html
String Search Algorithms for Large Texts | Baeldung
Boyer–Moore–Horspool algorithm - Wikipedia
Algorithm of the Week: Boyer-Moore String Searching - DZone
https://johannburkard.de/software/stringsearch/
はてなブックマーク全文検索の精度改善