[B! algorithm][perl] manabouのブックマーク

乱数の性質とセッショントークンの作成 - $shibayu36->blog;

ユーザアカウントのログイン機能とか作ってると、何らかの形でセッション用のトークンを作成する機会がある。今まではこれは適当にランダムな値を利用していればいいんでしょと思っていたのだけど、ちょっと違ったのでメモ。乱数の性質 http://akademeia.info/index.php?%CD%F0%BF%F4によると、乱数には三つの性質がある。無作為性：統計的な偏りがなく、でたらめな数列になっているという性質。予測不可能性：過去の数列から次の数を予測できないという性質。再現不可能性：同じ数列を再現できないという性質。再現するためには、数列そのものを保存しておくしかない。この時、少なくとも無作為性のみ満たされていると弱い擬似乱数、無作為性と予測不可能性が満たされていると強い擬似乱数、全てが満たされていれば真の乱数と呼ばれる。ソフトウェアだけでは、真の乱数を作ることができず、真の乱数に

manabou 2015/10/27

リンク

飛行機搭乗方法のシミュレーション - Qiita

はじめに私はほぼ毎週飛行機に乗るため、飛行機搭乗時に、「混雑を避けるため、後方座席のお客様からご案内いたします」という案内、非常に良く聞くのですが、いつもこのアルゴリズムにあまり納得がいっていませんでした。搭乗時の混雑の原因は主に二つあります。手荷物の上部収納既に乗客が座っているよりも奥の座席に入る場合（例えば、通路側に既に座っている人がいる時に、窓側の席に座ろうとすると、一度通路側の席の乗客が立つ必要がある）私は、この2点については、後方座席・前方座席を分けることによって、むしろ上記渋滞発生箇所が近くで発生してしまい、より混雑を生むように思っていました。全ての乗客を早く搭乗させることを目的とするならば、例えば窓側の乗客を先に搭乗させれば上記の混雑はある程度解消されます。しかし、飛行機では上部収納がいっぱいになってしまって席の近くの収納棚が使えないことがしばしばありますので、そ

manabou 2015/09/25

リンク

Perlで完備辞書(Fully Indexable Dictionary)のモジュールを書いた - EchizenBlog-Zwei

ウェーブレット木/行列など「高速文字列解析の世界」で扱っているデータ構造やアルゴリズムは完備辞書(Fully Indexable Dictionary)を基本的な道具として用いるものが多い。とはいえ実用的な完備辞書を一から作るのは大変なので、高速文字列本を読んで「ちょっとウェーブレット行列を作ってみようかな」と思ったとしても完備辞書は適当なモックで済まさないといけなかったりして面白くない。というわけでPerlモジュールを書いた。 https://github.com/echizentm/FullyIndexableDictionary 例えば以下のような感じ。これでLOUDSもウェーブレット行列もさくさく作れますね！ use FullyIndexableDictionary; my $fid = FullyIndexableDictionary->new(); $fid->set(1,

manabou 2013/02/16

リンク

perlで高速な類似検索エンジンを構築できるようにしてみた - download_takeshi’s diary

すみません。タイトルはやや釣り気味です。類似検索エンジンというか、そのアイデア程度の話なんですが、以前から考えていた類似検索エンジン風のネタがあったので、ちょっとperlで書いてみたので、そいつを晒してみます。 Luigi 　 https://github.com/miki/Luigi 類似検索なのでLuigi。ルイージとか読みたい人はそう読んじゃっても良いです。（冷）考え方と仕組み類似文書の検索、となりますと一般的には超高次元での空間インデックスとかが必要になります。昔からR-TreeやSR-Treeなど、いろいろと提案されていますが、より高次元になると「次元の呪い」によりパフォーマンスが出なくなる、なんて言われていますね。そこで最近ではLSHに代表されるような、より高度な「近似」型のインデキシング手法が人気を集めているようです。で、今回考えたLuigiも実は近似型のインデッ

manabou 2012/03/19

リンク

Dynamic Programming による類似文字列マッチの実装例

Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを素直に Perl で実装したみた。さらにマッチ箇所取り出しロジックも実装してみた。 # DP はいわゆる「類似文字列検索（あいまい検索）」に使うと便利なalgorithm。実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二つの文字列 "

manabou 2012/03/17

リンク

livedoor Developers Blog:String::Trigram でテキストの類似度を測る - livedoor Blog（ブログ）

こんにちは。検索グループ解析チームの nabokov7 です。今回は、livedoor キーワードでの事例より、テキストの類似度を測るのに便利な手法を紹介します。 livedoor キーワードは、livedoor ブログでその日その日で話題になった語をランキング表示するサービスです。当初、はてなキーワードやWikipediaを足して2で割ったようなサービスを作れといった開き直った指示のもとで開発が開始されたともいう、分社化前の芸風の名残で、キーワードの検索結果にはユーザが自由に解説を書き込める Wikipedia 的スペースもついています。で、この解説部分に、さまざまなサイトから文章をまる写ししちゃう人がとても多いのですね。特に多いウィキペディア日本語版からの剽窃を防止するために、livedoor キーワードでは以下のような対策を講じることにしました。ウィキペディア日本語版の解説