タグ

algorithmとperlに関するhiromarkのブックマーク (29)

  • Consistent Hashing を試す

    Consistent Hashing は、 複数のノードにレコードを分散させる方法として、 Amazon Dynamo や Cache::Memcached::Fast などで使われているアルゴリズムです。 この文章では、Perl で実際に Consistent Hashing を実装し、 その特徴を理解することを目的とします。 更新履歴 2008-06-01: 公開 サーバー台数で割った余り (mod) を使用する まず Consistent Hashing と比較するために、レコードに対して整数のハッシュ値を求め、 ハッシュ値をノード数で割った余り (mod) で、ノードを選択するという方法を書いてみます。 ここでは、ハッシュ値の算出に CRC (Cyclic Redundancy Check) を使用しています。 use strict; use String::CRC; use Pe

    hiromark
    hiromark 2010/08/25
    ああ、まとまってる。
  • 誤り許容カウント法(lossy count method)のサンプルプログラム

    誤り許容カウント法(lossy count method)のサンプルプログラム 2010-05-12-1 [Programming][Algorithm] 1行1ラベル形式で、 1万種類のラベルを持つ、 100万行のデータがあるとします (ラベルの頻度分布はジップの法則にだいたい準拠するとします)。 各ラベルの頻度をハッシュを使ってカウントするとなると、ハッシュエントリ1万個分のメモリ容量が必要になります。(1万じゃたいしたことないな、という人はもっと大きな数に置き換えて読んでください。) しかし、カウント後に高頻度のものしか使わないということも多いと思います。例えば頻度5000以上のもののみ取り出してあとはいらない、とか。 そうなると、全部のラベルのカウントデータを最後まで保持するのは無駄に思えます。 そこで登場するのが「誤り許容カウント法(lossy count method)」。 低

    誤り許容カウント法(lossy count method)のサンプルプログラム
  • 動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし(寅年)の日記

    組み合わせ最適化の手法として「動的計画法」というモノがあります。 wikipediaから抜粋 動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP) コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法 一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。 ナップサック問題と動的計画法 動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。 こんな感じの問題です。 今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各

    動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし(寅年)の日記
    hiromark
    hiromark 2010/03/02
    うわ、だいぶ忘れてた。
  • ギレンも登場!BM25なPerlモジュール書いたよ - download_takeshi’s diary

    久しぶりに何か書きます。 情報検索のアルゴリズムで「BM25」というものがあります。 何年か前に某研究所に遊びに行ったときに「TF/IDFより精度のいいやつ」みたいな感じでかなりアバウトに教えてもらいました。 その時は「名前だけでも覚えて帰ろう」と思っていたのですが、帰りに安い居酒屋で大酒をのみ、電車のなかで騒いでしまうほど酔っ払ってすっかりその名前を忘れてしまってました。(なにやってんだか・・・) で、最近Web+DB pressをパラパラ見ていたらBM25の名前を発見!ああ、これだこれだ、思い出したよ! というわけで、重い腰を上げてモジュール化してみました。 githubに上げてあります。 Lingua::JA::OkapiBM25 http://github.com/miki/Lingua-JA-OkapiBM25 そのうちCPANからも落とせるようになります。 正式名称は「Okap

    ギレンも登場!BM25なPerlモジュール書いたよ - download_takeshi’s diary
    hiromark
    hiromark 2009/12/07
    いろいろな部分で GJ!
  • Bayesian Setsを試してみた - のんびり読書日記

    この前YAPC Asia 2009に参加してきたのですが、そこで「はてなブックマークのシステムについて」の発表の中で、「はてブの関連エントリはBayesian Setsを使って計算されている」という話を聞いてBayesian Setsに俄然興味が湧いてきました。Bayesian Setsは以前論文だけ少し読んで、あまりよく分からないまま放置していたのですが、せっかくなのでPerlで作って試してみました。 Bayesian Setsについて詳しくは、以下のリンク先の資料をご参照下さい。 Bayesian Setsの論文 Bayesian Setsの詳しい説明記事 bsets, The Bayesian Sets algorithm. (Matlabのコード) 実際に作成したコードは以下の通りです。上記のMatlabのコードを参考にさせていただいています。 #!/usr/bin/perl #

    Bayesian Setsを試してみた - のんびり読書日記
    hiromark
    hiromark 2009/09/24
    おお、結構いい感じ。
  • YAPC::Asia 2009 1日目 「Perlで圧縮」の資料 - naoyaのはてなダイアリー

    1日目の発表を終えました。資料を公開します。 Perlで圧縮View more presentations from Naoya Ito. 発表の方は少し駆け足になってしまいました。明日ははてなブックマークのシステム事例の話をしたいと思います。 発表の様子 via: http://yapcasia2009.ficia.com/

    hiromark
    hiromark 2009/09/11
    相変わらずわかりやすいなあ。
  • Perl で Range Coder - naoyaのはてなダイアリー

    練習がてら、圧縮符号化の手法のひとつである Range Coder を Perl で実装してみました。 http://github.com/naoya/perl-algorithm-rangecoder/tree/master Range Coder は算術符号を実数ではなく整数で実現した手法です。高速な算術圧縮を実現する「Range Coder」 (1/2):CodeZine(コードジン) に詳しい解説があります。今回の実装も、この記事にあるソースコードを参考に実装しました。参考、というか結局ほとんど移植に近くなってしまいました。 インタフェースは以下のようになっています。入力文字列における各記号の出現頻度、累積出現頻度をあらかじめ算出して RangeCoder オブジェクトにセットしてから、encode することで圧縮結果が得られます。(出現頻度表をバイナリに添加する実装は行っていませ

    Perl で Range Coder - naoyaのはてなダイアリー
    hiromark
    hiromark 2009/09/08
    Range Coder の Perl 実装。
  • Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー

    圧縮アルゴリズムにおける適応型算術符号の実装では、累積頻度表を効率的に更新できるデータ構造が必要になります。もともと算術符号を実装するには累積頻度表が必要なのですが、これが適応型になると、記号列を先頭から符号化しながら、すでに見た記号の累積頻度を更新していく必要があるためです。 累積度数表をナイーブに実装すると、更新には O(n) かかってしまいます。配列で表を持っていた場合、適当な要素の頻度に更新がかかるとその要素よりも前の要素すべてを更新する必要があります。適応型算術符号のように記号を符号化する度に更新がかかるケースには向いていません。 Binary Indexed Tree (BIT, P.Fenwick 氏の名前を取って Fenwick Tree と呼ばれることもあるようです) を使うと、累積頻度表を更新 O(lg n)、参照 O(lg n) で実現することができます。BIT は更

    Binary Indexed Tree (Fenwick Tree) - naoyaのはてなダイアリー
    hiromark
    hiromark 2009/09/08
    あとでじっくり
  • 完全2部グラフをGraphvizとPerlを使って簡単に書く方法 - salmonsnareの日記

    [追記: 2010/08/18] id:ksmemoさんがGraphVizモジュールを使って書かれたコードの方がすっきりしているのでこちらを推奨します。 ケーズメモ, GraphVizを使ってPerlで簡単にGraphvizでグラフを書く方法, http://d.hatena.ne.jp/ksmemo/20090903/p1 CPAN, GraphViz, http://search.cpan.org/dist/GraphViz/ はじめに 「頂点数の大きな完全2部グラフを手で書くより、自動化した方がいいだろう。」 っていう動機で、 Graphvizのファイル形式である、dotを出力するためのPerlスクリプトを書きました。 Graphvizは、グラフ理論でいうグラフを簡単に描画するための便利なツールです。 導入の資料は、[1]に紹介したので参照してください。 完全2部グラフとは 2部グラ

    完全2部グラフをGraphvizとPerlを使って簡単に書く方法 - salmonsnareの日記
    hiromark
    hiromark 2009/09/03
    色々便利そうなやり方なのでメモ。
  • 正規表現でCommon Prefix Search

    正規表現でCommon Prefix Search 2007-05-15-1 [Programming][Algorithm] 正規表現でCommon Prefix Searchを行う力技な方法のPerlによるサンプル。 ちょっと試すとき用のコピペ用コード片、といった感じのものです。 TRIEとかオートマトンとかでちゃんとやるのが王道ですよ。 コード: use strict; use warnings; use utf8; binmode STDOUT, ":utf8"; my $str = "あうえういあおういいういああ"; my $key = "ういあ"; my @chars = split("", $key); my $pat = join("(", @chars).(")?" x $#chars); while ($str =~ /($pat)/g) { print "$1\n";

    正規表現でCommon Prefix Search
    hiromark
    hiromark 2009/08/25
    ちょっとした実験に便利そう。
  • low が 31 ビットの Range Coder - naoyaのはてなダイアリー

    先日実装した Range Coder (id:naoya:20090724:1248433187) は Perl が use integer すると整数を signed int で扱う関係から low を 24 ビットで妥協し、整数32ビットの上位1バイトを使わない実装を行っていましが、signed int の場合でも 32 ビットの最上位ビットを使わない、すなわち 31 ビットで計算すると良いということ、またその実装方法を広井さん (参考にさせていただいた Algorithms with Python の広井さんです) に教えていだだきました。ありがとうございます! github のレポジトリに 31 ビット版の実装を追加しました。 http://github.com/naoya/perl-RangeCoder/tree/master の、lib/RangeCoder.pm が 24 ビ

    low が 31 ビットの Range Coder - naoyaのはてなダイアリー
    hiromark
    hiromark 2009/07/27
    31 ビット版 Range Coder。ゆっくり読む。
  • 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー

    昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベンシュタイン距離, Levenshtein Distance) は二つの文字列の類似度 (異なり具合) を定量化するための数値です。文字の挿入/削除/置換で一方を他方に変形するための最小手順回数を数えたものが編集距離です。 例えば 伊藤直哉と伊藤直也 … 編集距離 1 伊藤直と伊藤直也 … 編集距離 1 佐藤直哉と伊藤直也 … 編集距離 2 佐藤B作と伊藤直也 … 編集距離 3 という具合です。 編集距離はスペルミスを修正するプログラムや、近似文字列照合 (検索対象の文書から入力文字にある程度近い部分文字列を探し出す全文検索) などで利用されます。 編集距離算出は動的計画法 (Dynamic Programming, DP) で計算することができることが

    編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
    hiromark
    hiromark 2009/03/30
    ”説明は長いのに実装するとあっけないというのは 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

    最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
    hiromark
    hiromark 2009/03/30
    さすが、お仕事がはやい。
  • 第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー

    昨日は第11回 Kansai.pm でした。 今回は無理を言って自分がホストを担当させていただきましたが、面白い発表が多く開催した自分も非常に満足でした。 PFI の吉田さんによる Cell Challenge での計算機に合わせたアルゴリズムのチューニング手法の発表 (発表資料) は圧巻でした。伊奈さんの文抽出の話 (発表資料)、はこべさんのコルーチンの話 (発表資料)、いずれも難解になりがちなところを凄く分かりやすく解説されていて、さすがだなと思いました。各々ショートトークも、いずれも良かったです。 スペルミス修正プログラムを作ろう 自分も 20 分ほど時間をいただいて、スペルミス修正プログラムの作り方について発表しました。 スペルミス修正プログラムを作ろうView more presentations from Naoya Ito. スペルミス修正プログラムについてはずばり スペル

    第11回 Kansai.pm / スペルミス修正プログラムを作ろう - naoyaのはてなダイアリー
    hiromark
    hiromark 2009/03/24
    相変わらず分かりやすいなあ。全体のまとめも嬉しい。
  • Locality Sensitive Hashing に挑んでみた - download_takeshi’s diary

    久々のエントリです。 Locality Sensitive Hashing を perl で使うためのモジュールを書いてみました。Algorithm::LSHと名付けました。 先ほどDeveloper ReleaseとしてCPANにあげましたが、反映されるまで時間かかるので、興味ある方はcodereposからみてください。 Algorithm::LSH CPAN: http://search.cpan.org/~miki/Algorithm-LSH/ coderepos: http://coderepos.org/share/browser/lang/perl/Algorithm-LSH 超アルファバージョンな状態ですが、そのうちgithubにもupする予定。 そうそう、そう言えば WEB+DB PRESS Vol.49 にレコメンドエンジンの特集があって、その中に偶然にもLocality

    Locality Sensitive Hashing に挑んでみた - download_takeshi’s diary
    hiromark
    hiromark 2009/03/23
    Perl で LSH
  • PDL で PageRank - naoyaのはてなダイアリー

    id:smly さんが PageRank や HITS を Python で実装 されているのに触発されて、自分も PageRank を Perl で実装してみました。 PageRank の計算の中心になるのは Power Method (べき乗法) です。べき乗法では行列とベクトルの積を計算しますので、手軽に使える行列演算ライブラリがあると楽でしょう。 色々調べてみたところ、PDL (The Perl Data Language) が良く使われているようでしたので、これを選択しました。PDL では各種行列演算が簡単に行える他、文字列評価をオーバーライドして行列の文字列出力を良い具合で定義してくれていたりと、なかなかに便利です。PDL は行列計算以外にも色々な科学技術計算やグラフ描写などの操作をサポートしているようです。 さて、PDL を使った PageRank 計算のコードは以下のように

    PDL で PageRank - naoyaのはてなダイアリー
    hiromark
    hiromark 2009/03/05
    GJ! いつもながらに説明が分かりやすくて嬉しいです。
  • k-means++を試し中 - のんびり読書日記

    http://d.hatena.ne.jp/kaiseh/20090113/1231864089 上の記事を見て、k-means++が面白そうだったので、ちょっとだけ試してみた。 k-meansは初期値に大きく依存するところが嫌い。初期値への依存度を軽減するために、初期値を変えて何回か試行してその中で一番良い結果のものを使用する、なんてことをしないといけない。そのため処理時間も馬鹿にならなくなってしまうので、ちょっとこれじゃあなあ…ということで使ってなかった。 でも今回のk-means++は初期値をうまく求めることで、精度と速度の向上が得られるらしい。これはうれしい! 論文著者のページにサンプルコードがあったので試してみようと思ったんだけど、MFCを使っているみたいで僕の環境ではコンパイルできず…。 http://www.stanford.edu/~darthur/kMeansppTest

    k-means++を試し中 - のんびり読書日記
    hiromark
    hiromark 2009/01/17
    Perl での k-means++ の実装例。
  • 「日本語テキストを分類するベイジアンフィルタ」を簡単につくるyo - download_takeshi’s diary

    数週間前の話になりますが、「はてブのリニューアル会見」の記事を読んでいたところ、はてブにも「自動カテゴライズによる記事分類」の機能が搭載されるとか。。。 同じようなタイミングで「似たようなモノ」というか「ほぼ同じようなモノ」を作っていたので、すごーくインスパイアされてしまいました。ジュワ〜。(アドレナリンの放出音) 数週間たってもいまだ興奮冷めやらぬ状態なので、今日はその件について書いてみようと思います。 Lingua::JA::Categorize - a Naive Bayes Classifier for Japanese document. http://search.cpan.org/~miki/Lingua-JA-Categorize-0.00001/ 「はてブのパクリ」ではありません。「ベイジアンによる日語テキスト分類器」を「簡単に作る」ことを目的としたモジュールです。 も

    「日本語テキストを分類するベイジアンフィルタ」を簡単につくるyo - download_takeshi’s diary
    hiromark
    hiromark 2008/11/25
    試してみよう。
  • 名義尺度間の連関係数を算出するperlモジュール - ダウンロードたけし(寅年)の日記

    データマイニングを行う際に、適当な2つの変数にどれだけの相関関係があるのか確かめたくなったとします。 それらのデータはいわゆる「名義尺度」なデータ(地域別の野球チームの好き嫌いなど)だとしましょう。 名義尺度なデータ間における連関係数と言えば「クラメール係数」。 これをぱっと算出してくれるモジュールが欲しくなったので書いてみました。 Statistics::Associations - Calculates Association Coefficients of Nominal Scale. http://search.cpan.org/~miki/Statistics-Associations/ 使い方はこう。 use strict; use Statistics::Associations; my $asso = Statistics::Associations->new; my $m

    名義尺度間の連関係数を算出するperlモジュール - ダウンロードたけし(寅年)の日記
    hiromark
    hiromark 2008/11/19
    あ、これは色々使えそう。
  • Wavelet Tree - naoyaのはてなダイアリー

    圧縮全文索引の実装などでしばしば利用される Rank/Select 辞書と呼ばれるデータ構造があります。詳しくは参考文献を参照していただくとして、今回は一般の文字列に対して効率的に Rank/Select を可能とするデータ構造である Wavelet Tree (ウェーブレット木) のライブラリを作りました。 http://github.com/naoya/perl-algorithm-wavelettree/tree/master my $wt = Algorithm::WaveletTree->new("abccbbabca"); is $wt->rank(6, 'a'), 2; is $wt->rank(6, 'b'), 3; is $wt->rank(9, 'b'), 4; is $wt->select(0, 'a'), 0; is $wt->select(1, 'a'), 6;

    Wavelet Tree - naoyaのはてなダイアリー
    hiromark
    hiromark 2008/11/17
    WaveletTree のライブラリ。