SuffixArray - みずぴー日記
30分プログラム、その580。id:Gemmaさんに借りたWEB+DB PRESS Vol.50に、suffix arrayの解説が載っていたのでやってみた。 解説を読んだときは「ちょう簡単じゃん。さくっと実装してやんよ」と思っていたけど、いざ始めたけど、けっこう大変だった。簡単とか言って、ごめんなさい。 そもそもararyとついてる時点で大変なことに気がつくべきだった。ボク、OCamlでarrayを使ったことなんてほとんどないじゃないか。 使い方 シグネチャはこんな感じ。 type t val make : string -> t val find : t -> string -> int list まず、suffix arrayを作る。 # let s = SuffixArray.make "abracadabra";; val s : SuffixArray.t = <abstr>
全文検索エンジンを試作してみたよ - やればできる子の日記
今日は奥様とタイ料理&タイ式マッサージの日でした。マッサージはちょっと素晴らしいなあ。 表題のように、全文検索エンジンをGAE上で試作してみました。GAEはGoogle様提供のサービスにもかかわらず「なんで全文検索機能がないねん」という声が上がっていたんですよね。主にtwitter界隈から。 「Introduction to Information Retrieval」という本のドラフトPDFと、たつをさんのところのIIR輪講の資料を参考に作りました。つっても、第1章の一部の知識しか使ってないですが。論理和検索もスキップリストも使ってないし(論理和検索はクエリ式のパーサを書くのが面倒だった)。 import logging import re from urllib import urlencode import wsgiref.handlers from google.appengine
perlによる大規模データの取扱い
本ページでは，perlでどのようにして大規模なデータを保存するかついて 説明します．主にスタンドアロンで動くもの (クライアント<->サーバ型 でない，いわゆる組込み型) について紹介したいと思います． Menu Berkeley DB BerkeleyDB DB_File SDBM SDBM_File GDBM GDBM_File CDB CDB_File QDBM Depot Curia Villa TDB TDB_File SQLight DBD::SQLite SUFFIX ARRAY SUFARY SARY 複雑なデータ構造 Data::Dumper Storable MLDBM いろいろな比較 ファイルサイズ Benchmark Link サンプルデータについて Berkeley DB Berkeley DBは，組み込み向けデータベースです．通常データベースという とOracl
RPC サーバの遅延リターン - steps to phantasien(2009-07-04)
最近は過労気味でウェブにものを書くこともできない, という話で上司の同情を誘うべく 日本人の労働時間やストレスの実態をまとめた エンドレス・ワーカーズ を読んだら, 自分の労働時間は日本人労働者の上位 2 割から漏れていることを知り愕然とした. あんなに働いたってのに...残業エリートへの道は険しい. 道を進みたいわけじゃないけれど. (平均は越えてたぜ!) いずれにせよ流行からはすっかり脱落しているので, 時流を無視して仕事の話でもしよう. 以前, 会社の blog で RPC の結果をノンブロッキングスタイルで受け取るプリミティブ "弱関数" を提案した. でも試行錯誤の結果, いまは使っていない. C++ での弱参照は意図しないリークを作りやすい. 使いわすれることも多く, 忘れた頃にクラッシュする. 要求は明示的にキャンセルした方がいいことがわかった. (世間はみんなそうやってます
フォードファルカーソン法をRubyで実装 - yasuhisa's blog
グラフに対する基本的な問題として 最小全域木 最短路問題 最大フロー の3つがあると思う。で、最小全域木は離散最適の課題としてPrim法を使って解いてみたし、最短路問題はベルマンフォードのアルゴリズムをRubyとC++で解いてみた。となったら、最大フローを実装しないわけにはいかないな、ということでフォードファルカーソン法を実装してみました。上の3つの問題では一番ややこしかった気がする。というわけでコードと実行結果。 繰り返しの中で残余ネットワークを更新していって、残余ネットワークにおいて始点から終点へのパスが存在するかを幅優先探索を使って探索していくという流れ。 # -*- coding: utf-8 -*- require "pp" class DirectedGraph attr_reader :nodes attr_reader :weights attr_reader :edges
経路からツリーへの変換 - みずぴー日記
30分プログラム、その614。昨日やっていたやつ(id:mzp:20090630:tree)の逆変換。一晩寝たら、すんなり解けた。 (foo) (foo bar) (foo bar baz) (foo xyzzy) (foo baz) みたいな木の根から末端までの経路リストがあったとする。これから、木を再構築したい。 (make-tree 'foo (make-tree 'bar (make-tree 'baz)) (make-tree 'xyzzy) (make-tree 'baz)) これで、flash.display.Spriteとかflash.text.TextFieldみたいな完全修飾名からパッケージの階層構造を再構築できるようになる。 使い方 gosh> (path-list->tree '((foo bar baz) (foo bar) (foo xyzzy))) (foo
Ohmm: Online Training for Hidden Markov Model
English 概要 ohmmは隠れマルコフモデルにおいて，Online EMアルゴリズム[1]を用いて学習するためのライブラリです．大規模なデータを利用した学習に対応しており数十万語規模の学習データを利用した学習を行うことができます．また学習結果を他用途で利用できるような形で出力することができます． ダウンロード ohmmはフリーソフトウェアです．BSD ライセンスに従って本ソフトウェアを使用，再配布することができます. ohmm-0.01.tar.gz: HTTP 更新情報 2009-05-19: ohmm 0.01 0.01をリリースしました 使い方 ソースコードで配布しています。インストール方法は以下の通りです。 >configure >make >sudo make install として使ってください。プログラムohmmが作成されます ohmmは各行に１例ずつ単語列が書か
終了いたしました。
作者ホームページサービス（hp.vector）は終了いたしました。 長らくのご利用、ありがとうございます。 ご不明な点があれば、お問い合わせページをご覧の上、お問い合わせください。 ※15秒後にトップページに戻ります。 (c) Vector HOLDINGS Inc.All Rights Reserved.
Rubyのある風景 - Y Combinator
再帰的な関数を作るときに関数に名前をつけずに定義するにはどうしたらいいのかというのが、Y Combinatorの中心的な話題です。 まずは、再帰の定番、階乗を計算する関数に登場願いましょう。 fact = lambda{|n| if n < 2 1 else n * fact[n - 1] end } puts fact[10] ここからfactという名前を取り除こうというわけですね。 最終目標は、以下のようにして階乗を計算する関数を定義することができるようになることです。 fact = y[lambda{|h| lambda{|n| if n < 2 1 else n * h[n - 1] end } ] ) puts fact[10] ここで出てきたyが、Y Combinatorと呼ばれるものです。 見やすさの為に、factという名前をつけましたが、関数を定義するところではfact
Kansai.pmでコルーチンについて発表してきた - はこべにっき ♨
Kansai.pm#11にて「Perlで学ぶコルーチン」という発表をしてきました． だいぶ前のRuby勉強会でRuby 1.9のFiberをみてPerlでもいろいろやってみていたので，その時しらべたことを中心にぐだぐだとしゃべりました． Perlで学ぶコルーチンView more presentations from hakobe. コルーンは継続や並行処理などいろいろな概念がからんでいて調査がたいへんでした．PerlでのCoroの実装がどうなっているのかもう少し詳細に調査/発表できたらよかったです． スライドにも書いてますが，Ruby 1.9のFiberとまったく同じインターフェースをもったFiber.pmをつくってみました．githubで 公開しています． http://github.com/hakobe/perl-fiber/tree 以下のように簡単にFiber(=コルーチン)をつ
編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
おとうさん、ぼくにも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は、画像に含まれるアニメキャラクター的な人物の顔の位置を検出し、さらに目や口など顔を構成する部品位置や大きさの推定、肌や髪の色の抽出を簡単に行うことができるライブラリです。 これらが可能になると、 画像から自動でいい感じのサムネイルを作成できる 動画から自動でいい感じのサムネイルを作成できる 自動的にぐぬぬ画像が作れる 自動的に全員の顔を○○にできる 顔ベースのローカル画像検索 など、最新鋭のソリューシ
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
アルゴリズムイントロダクション輪講 動的計画法の発表資料 - てっく煮ブログ
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メディア: 単行本
文字列の中から効率良くキーワードを探し出せ
文字列の中から効率良くキーワードを探し出せ：コーディングに役立つ！ アルゴリズムの基本（7）（1/4 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 前回「Firebugで探索アルゴリズムを見ていこう」では、数値の集合の中から特定の数値を探索しました。今回は文字列の中から検索ワードを探索してみましょう。 UNIXのコマンドならgrep、Javaなどのプログラムなら文字列のindexOfメソッドなどに相当する処理です。 力任せ法 それでは例によって最もベタなアルゴリズムの紹介から始めましょう。 文字列の中に検索ワードがあるかどうか調べます。文字列の先頭から1文字ずつ検索ワードと比較していきます。不一致があったら文字列の2文字目から1文字ずつ検索ワードと比較し
分散ハッシュテーブル（DHT） - FreeStyleWiki
分散ハッシュテーブル（DHT : Distributed Hash Table）とは、大量のデータから検索情報を手早くたどることができる構成である。 たとえば、「リンゴ」「ぶどう」「みかん」「バナナ」「パイナップル」のようなキーワードがあった場合に、 リンゴ ==> 「ら」行のノードに格納 ぶどう ==> 「は」行のノードに格納 みかん ==> 「ま」行のノードに格納 バナナ ==> 「は」行のノードに格納 パイナップル ==> 「は」行のノードに格納 のように、「あかさたな...」で分類して、インデックスで引き出せるように効率化したものをイメージするとよい。 ただし、上記のように「は」行が多いようであると、それを管理するノードに処理が集中してしまう。それを回避するために、「ハッシュコード」を使用する。 ハッシュ値（メッセージダイジェスト）とは？ 与えられた原文から生成された固定長
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Suffix Arrayを用いたフレーズ抽出 - kuronekonacchan
サービス終了のお知らせ