Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
Google の秘密 - PageRank 徹底解説
INDEX はじめに PageRank の基本概念 どうやって PageRank を求めるか 現実に適用する際の問題 Namazu での実装実験 PageRank に対する個人的見解 参考文献 おまけ：「グーグル？／ゴーグル？」 Since: Thu Feb 1 18:22:44 JST 2001 Last Refreshed: Sat Jan 24 18:30:35 JST 2004 ★(2004/1/24) Yuan Huanglin氏によって 本ページの中国語訳 が作成されました。 ★(2003/7/1) 拙著『Namazuシステムの構築と活用』を改訂しました。 詳しくは サポートページをご覧ください。 ★(2003/5/20) Google に関するオンラインニュース記事一覧(日本語記事のみ)を 別ページ(googlenews.html) として分離しました。 ★(2001/2/
PDL で PageRank - naoyaのはてなダイアリー
id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように
CNET Japan Blog - 先端研ブログ：画像処理的アプローチによるWeb情報処理
Icon, Others そしてこれらをベースに自動的に画像要素を分類しました。 分類エンジンは SVMLight + RBF Kernel を使用。 SVM (サポートベクターマシン) は機械学習の手法の一つです。 あらかじめ与えられた正解例・誤り例から、何が正誤の判断の決め手になる要素なのかを自動的に学習し、その学習結果を用いて新たな事例に対して正誤の判断を与えます。 学習に使う特徴量（正誤判断の決め手となる要素の候補）として、ピクセル数・色数・DCT等の画像に基づくものと、周辺文字列・リンク有無等のテキストに基づくものを使用しています。 画像に基づく特徴量の一つとして、その画像に文字が含まれるか否かが重要です。 文字があれば見出しとして使われている画像の確率が高くなるわけですし。 ただし、OCRを用いても文字を認識するのは難しいので、「文字認識」ではなく画像パターンを用
N-gramモデルを利用したテキスト分析 ―インデックスページ―
↑ページ先頭 N-gramモデルを利用した事例 あるテキストから、任意のN-gram単位で共起頻度を集計し（N-gram統計を取る）、その結果を利用してテキストや言語の性格を見いだす研究によく利用される。 N-gramモデルで、ある文字列の直後に、特定の別な文字列は出現する確率を求める。 「an」の後には、必ず母音（aiueo）で始まる単語が結びつく確率が100% 「q」の後には、「u」が結びつく可能性が高い。 『論語』では「子」の後に「曰」が結びつく可能性が高い。 「百人一首」を平仮名に開いた場合の延べ数は、上位十五位までで全体の五割の使用量を占める（全部で六十八種の異なる平仮名（濁点含む）が使われている） 音声認識やOCR（原稿読みとりソフト）での利用 読みにくい文字でも、共起頻度の発生確率を考慮すれば、正しく原稿を可読出来る ↑ページ先頭 人文学的へのN-gramモデル導入 近藤みゆ
Introduction to Information Retrieval
This is the companion website for the following book. Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2008. You can order this book at CUP, at your local bookstore or on the internet. The best search term to use is the ISBN: 0521865719. The book aims to provide a modern approach to information retrieval from a co
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
