Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
PerlのRegexp::TrieをRubyに移植した - Islands in the byte stream
GitHub - gfx/ruby-regexp_trie: Optimized Regexp builder with Trie (a Ruby port of Perl's Regexp::Trie) # Gemfile gem 'regexp_trie' これははてなキーワードやWikipediaのリンクのように、ある程度の量のテキストに対して大量のキーワードをマッチさせるときに、最適化した正規表現を生成するライブラリです。 はてなキーワード*1をとあるブログエントリ*2にマッチさせるための簡単なベンチマークもあります。 example/benchmark.rb 結果: $ bundle exec example/benchmark.rb (snip) user system total real Regexp raw 4.270000 0.030000 4.300000 ( 4.3
[isucon] ISUCON6 予選通過しました
今回はついに予選通過しました。チーム名は円山町です。17日土曜日の予選当日にやったことをメモしておきます。 予選当日のタイムライン 10時 出社 (会社のオフィスから参加させてもらいました。大変感謝) 前の日の晩に作った無料試用アカウントでデプロイ Go 実装に変更、動作確認 記事を削除したら /initialize しても復活しなくて、初期データを壊してしまったので復旧方法を調査 /var/log/cloud-init-output.log を見て展開イメージの tar.gz を発見したので、中に入っている SQL ダンプでデータを復元 11時 Go 実装に切り替えたところ、スターが付かない不具合があったので、コードを検査、ngrep で調査して原因を特定 ローカルでコードいじるためにホームディレクトリで git init、必要そうなものを add/commit して push ローカル
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
