Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
ベイズを学びたい人におすすめのサイト - download_takeshi’s diary
ベイジアンフィルタとかベイズ理論とかを勉強するにあたって、最初はなんだかよくわからないと思うので、 そんな人にお勧めのサイトを書き残しておきます。 @IT スパム対策の基本技術解説（前編）綱引きに蛇口当てゲーム？！楽しく学ぶベイズフィルターの仕組み http://www.atmarkit.co.jp/fsecurity/special/107bayes/bayes01.html いくつかの絵でわかりやすく解説してあります。 自分がしるかぎり、最もわかりやすく親切に解説してる記事です。数学とかさっぱりわからない人はまずここから読み始めるといいでしょう。 茨城大学情報工学科の教授のページから http://jubilo.cis.ibaraki.ac.jp/~isemba/KAKURITU/221.pdf PDFですが、これもわかりやすくまとまってます。 初心者でも理解しやすいし例題がいくつかあ
おとうさん、ぼくにもYコンビネータがわかりましたよ！ - 2009-04-09 - きしだのはてな
やっと、Yコンビネータが何を意味するものなのか、どういう意義があるのかがわかりました。 名前を使わず再帰ができますよ！というだけのものじゃなかったのですね。 まずλありき 関数の話をしたいのです。 そのとき、いちいち hoge(x) = x * 2 としてhogeを・・・、とか名前をつけて話を進めるのがめんどうなので、関数を値としてあらわすと便利ということで、λという値を定義するのです。 そうすると、上のhoge関数なんかはλ(x)(x*2)などとあらわせますが、引数をあらわすのに()を使うといろいろまぎらわしいので、 λx.x*2 のように表記します。 というのがλ。 このとき、λになにかわたされたら、引数としてあらわされる部分を単純におきかえます。 (λx.x*2)y とあったら、xの部分をyでおきかえて (λx.x*2)y → y * 2 となります。λの引数部分を与えられた引数で置
Perlでアニメ顔を検出＆解析するImager::AnimeFace - デー
というのを作ったので自己紹介します。 2月頃から、コンピュータでアニメ顔を検出&解析する方法をいろいろ試しつつ作っていて、その成果のひとつとして、無理やり出力したライブラリです。 はじめに はじめにざっとライブラリの紹介を書いて、あとのほうでは詳細な処理の話を僕の考えを超交えつつグダグだと書きたいと思います。 Imager::AnimeFaceでできること Imager::AnimeFaceは、画像に含まれるアニメキャラクター的な人物の顔の位置を検出し、さらに目や口など顔を構成する部品位置や大きさの推定、肌や髪の色の抽出を簡単に行うことができるライブラリです。 これらが可能になると、 画像から自動でいい感じのサムネイルを作成できる 動画から自動でいい感じのサムネイルを作成できる 自動的にぐぬぬ画像が作れる 自動的に全員の顔を○○にできる 顔ベースのローカル画像検索 など、最新鋭のソリューシ
anlife - anlife
お知らせ † (09.02.28) バージョン0.9.5をリリース．ダウンロード． (09.02.07) Webページの内容を刷新． (09.01.29) 動作学習のアルゴリズムを改善．その結果の 動画をアップロード． ↑
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
LISPMEMO
LISPUSERLISPMEMOLisp isn't a language, it's a building material. -- Alan Kay 先日 ANSI Common Lisp の bfs がわかりにくい、という話があったので。 A -> B, C B -> C C -> D で、このようなネットワークの A から C までの最短経路を求める。 (defun shortest-path (start end net) (bfs end (list (list start)) net)) (defun bfs (end queue net) (if (null queue) nil (let ((path (car queue))) (let ((node (car path))) (if (eql node end) (reverse path) (bfs end (app
アルゴリズムイントロダクション輪講 動的計画法の発表資料 - てっく煮ブログ
2009年3月2日に、はてな京都オフィスで開催された アルゴリズムイントロダクション輪講 の第12回で「動的計画法」について発表しました。資料をここにおいておきます。View more presentations from nitoyon.分かりやすくしようと気合を入れてまとめたら165ページの大作になっちゃいました。無駄に長くてすいません。アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)作者: T.コルメン, R.リベスト, C.シュタイン, C.ライザーソン, Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, Charles E. Leiserson, 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一出版社/メーカー: 近代科学社発売日: 2007/03メディア: 単行本
形態素解析と検索APIとTF-IDFでキーワード抽出
形態素解析と検索APIとTF-IDFでキーワード抽出 2005-10-12-1 [Programming][Algorithm] 形態素解析器と Yahoo! Web 検索 API と TF-IDF を使ってキーワード抽 出するという先日の検索会議でのデモ、KEYAPI[2005-09-30-3]。 教科書に載っているような基本中の基本ですが、あらためてエッセンスを 簡単な例で解説したいと思います。 目的：キーワード抽出対象テキストから、そのテキストを代表する キーワードを抽出します。TF-IDF という指標を用います。（この値が大 きいほどその単語が代表キーワードっぽいということでよろしく。） TF-IDF を計算するためには、 (1) キーワード抽出対象テキスト中の代表キーワード候補出現数 (TF)、 (2) 全てのドキュメント数 (N)、 (3) 代表キーワード候補が含まれるドキュメ
手軽にTF/IDFを計算するモジュール - download_takeshi’s diary
情報検索の分野でよく使われるアルゴリズムで「TF/IDF」というものがあります。 ドキュメントの中から「特徴語」を抽出する、といったような用途でよく使われています。 TF/IDFアルゴリズムのくわしい解説はこことかここを見てください。 今回はこのTF/IDFの計算を「簡単」に実現するためのperlモジュールをCPANに上げましたので、ご紹介します。なまえはLingua::JA::TFIDFといいます。 Lingua::JA::TFIDF - TF/IDF calculator based on MeCab. http://search.cpan.org/~miki/Lingua-JA-TFIDF TF/IDF実装の困りどころ TF/IDFの実装を試みた方であればわかると思うのですが、実際にやろうとすると、TF（Term Frequency）の計算はなんら難しくありませんが、IDF（Inve
文字列の中から効率良くキーワードを探し出せ
文字列の中から効率良くキーワードを探し出せ：コーディングに役立つ！ アルゴリズムの基本（7）（1/4 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 前回「Firebugで探索アルゴリズムを見ていこう」では、数値の集合の中から特定の数値を探索しました。今回は文字列の中から検索ワードを探索してみましょう。 UNIXのコマンドならgrep、Javaなどのプログラムなら文字列のindexOfメソッドなどに相当する処理です。 力任せ法 それでは例によって最もベタなアルゴリズムの紹介から始めましょう。 文字列の中に検索ワードがあるかどうか調べます。文字列の先頭から1文字ずつ検索ワードと比較していきます。不一致があったら文字列の2文字目から1文字ずつ検索ワードと比較し
分散ハッシュテーブル（DHT） - FreeStyleWiki
分散ハッシュテーブル（DHT : Distributed Hash Table）とは、大量のデータから検索情報を手早くたどることができる構成である。 たとえば、「リンゴ」「ぶどう」「みかん」「バナナ」「パイナップル」のようなキーワードがあった場合に、 リンゴ ==> 「ら」行のノードに格納 ぶどう ==> 「は」行のノードに格納 みかん ==> 「ま」行のノードに格納 バナナ ==> 「は」行のノードに格納 パイナップル ==> 「は」行のノードに格納 のように、「あかさたな...」で分類して、インデックスで引き出せるように効率化したものをイメージするとよい。 ただし、上記のように「は」行が多いようであると、それを管理するノードに処理が集中してしまう。それを回避するために、「ハッシュコード」を使用する。 ハッシュ値（メッセージダイジェスト）とは？ 与えられた原文から生成された固定長
Erlang で分散ハッシュテーブル(kademlia)を使った Key-Value Store 作ってみたよ - cooldaemonの備忘録
Kai に kademlia の組み込みを提案する為、試しに作っていたのですが、README に書いた How to Use の項目が動くようになったので晒してみます。 cooldaemon's ermlia at master ― GitHub 設置方法なんかも README に書いてあるので、ご興味のある方は、そちらをご参考に。 まだ、いくつかの機能が未実装(定期的にデータを publish していない)だったり、不具合(Key のバージョン管理がされていない)があるけれど、そこそこに動きます。 おまえは kademlia を勘違いしている！等、突っ込み大歓迎。 参考 URI Erlangで分散ハッシュテーブルを実装してみた - NO!と言えるようになりたい id:ytakano 氏に多謝！ Amazon.co.jp： P2P教科書 (インプレス標準教科書シリーズ): 江崎 浩: 本
KH Coder: 計量テキスト分析・テキストマイニングのためのソフトウェア
分析結果の再現や生成AI活用についてのチュートリアル公開中 医療用語の辞書をご用意（無料） 産学連携プロダクト「KH Coderオフィシャルパッケージ」発売中 KH Coderとは KH Coderとは、計量テキスト分析またはテキストマイニングのための自由ソフトウェアです。 アンケートの自由記述・インタビュー記録・新聞記事など、さまざまなテキストの分析にお使いいただけます。 プログラミング不要、マウス操作で本格的な分析 安心の分析プロセス完全公開、研究利用も多数 New! 機能紹介（スクリーンショット） スクリーンショット集 ［旧ページ：言葉・文書・可視化・他］ KH Coder 3 正式版の新機能 New! 機能追加プラグイン「文錦®」シリーズ New! ダウンロードと使い方 KH Coder 3 正式版ダウンロード (Version 3.02) 使い方を知るためのチュートリアル ヘルプ
Yコンビネータ - Mae向きなブログ
相変わらず，Yコンビネータについては理解できていないのですが，昨日に引き続き，Rubyの学習もかねて，Schemeで書かれたYコンビネータをRubyで書くことに挑戦しました。 http://d.hatena.ne.jp/kazu-yamamoto/20080402/1207127522 でYコンビネータは，以下のように紹介されています。 (lambda (le) ((lambda (f) (f f)) (lambda (g) (le (lambda (x) ((g g) x)))))) 昨日は，たくさん出てくるlambdaをRubyでどう書けば良いのか分からなかったのですが，今日はなんとかYコンビネータをRubyで書くことができました。 y = lambda { |le| lambda { |f| f.call(f) }.call( lambda { |g| le.call(lambda
第 7 回アルゴリズムイントロダクション輪講会資料: Days on the Moon
すでにニュースでも伝えられている通り、12 月 1 日に第 7 回アルゴリズムイントロダクション輪講会がありました。今回の担当は私だったので、その発表資料を公開します。 中央値と順序統計量 (その 1) 予定 順序統計量とは 選択問題とは 最小値と最大値 平均線形時間選択アルゴリズム 中央値と順序統計量 (その 2) 最悪線形時間選択アルゴリズム 3 つずつのグループに分割した場合 7 つずつのグループに分割した場合 参考文献 中央値と順序統計量 (補足) 4 つずつのグループに分割した場合 6 つずつのグループに分割した場合 Lazy-Select Randomized-Partition スタッフロール 「どうせ後から Web で公開するんだから、PDF とか見るのに手間がかかるものは使ってられないよね。やっぱ時代は XML 複合文書でしょ!」と、数式を表現するのに MathML を使
Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー
,. -‐'''''""¨¨¨ヽ (.＿＿_,,,... -ｧァﾌ| あ…ありのまま 今日 起こった事を話すぜ！ |i i| }! }} /／| |l､{ j} /,,ｨ//｜ 『BWT について調べていたら Suffix Array のライブラリができていた』 i|:!ヾ､_ﾉ／ u {:}//ﾍ |ﾘ u' } ,ﾉ _,!V,ﾊ | ／´fト､_{ﾙ{,ィ'ｅﾗ , ﾀ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ おれも何をされたのかわからなかった… ,ﾞ ／ )ヽ iLﾚ u' | | ヾｌﾄﾊ〉 |／_／ ﾊ !ニ⊇ '／:} V:::::ヽ 頭がどうにかなりそうだった… /／ 二二二7'T'' ／u' __ /:::::::/｀ヽ /'
LZ法再び - DO++
可逆データ圧縮としてはgzipやlha, pngなどダントツで使われているLZ法（Lemple Ziv法）ですが、他のデータ圧縮法（BWT法、PPM法、CM法）に比べ圧縮率が低いということで研究の対象としてはあまり注目をあびていませんでした。ところが次の論文で真面目にやれば圧縮率は非常に高くなる可能性があり、BWT法とかそれを超える可能性があることが示されています。。 "On the bit-complexity of Lempel-Ziv compression", SODA 2009, P. Ferragina, et. al. [pdf] まず、LZ法についておさらいですが、基本的にはデータを前から順番に見ていったときに、既に出現した文字列がもう一度出現（マッチング）したら、その文字列を前回出現した（相対）位置と長さのペア(pos, len)で置き換えることで圧縮する方法です。データ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
15-462 Computer Graphics, Fall 2007
はてなブログ | 無料ブログを作成しよう
