Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
Natural Order String Comparison
by Martin Pool This project has moved to github.com/sourcefrog/natsort. Computer string sorting algorithms generally don't order strings containing numbers in the same way that a human would do. Consider: rfc1.txt rfc2086.txt rfc822.txt It would be more friendly if the program listed the files as rfc1.txt rfc822.txt rfc2086.txt Filenames sort properly if people insert leading zeros, but they don't
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
QuickSilverが実装しているAlcorの「Abbreviation Scoring」解説 | gihyo.jp
Macを持ってない人がMacを使ってみたいと思うキラーソフトがいくつかあります。プレゼンソフト「Keynote」やウィンドウ整列ソフト「Expose」が代表格でしょう。そして、アプリケーションやファイルを開くことからiTunesの操作、Twitter投稿までが数回のキータイプで行える「QuickSilver」もその一つでしょう。 この記事では、QuickSilverで実現している「タイプされた文字から適切なアプリケーションを特定する」操作に使われているアルゴリズム「AlcorのAbbreviation Scoring」について解説しています。「Alcor」は、このアルゴリズムを実装した人の名前です。QuickSilverはGoogle Codeにてオープンソース化されており、このアルゴリズムはJavaScriptやPython、Emacs Lispなど、さまざまな言語にポーティングされて
レーベンシュタイン距離 - Wikipedia
レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される[1]。名称は、1965年にこれを考案したロシアの学者ウラジーミル・レーベンシュタイン (露: Влади́мир Левенште́йн) にちなむ。 レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。レーベンシュタイン距離の更なる一般化として、例えば一回の操作で二文字を変換する等の方法が考えられる。 実際的な距離の求め方を例示すれば、「kitten」を「s
ベルマンフォードのアルゴリズムで実行される結果も逐次表示 - yasuhisa's blog
離散最適化理論の課題が出ていたので、ベルマンフォードのアルゴリズムを実装してみることにした。アルゴリズムが実行されていく様子の例もレポートに貼ろうと思ったんだけど、アルゴリズムはもうあるんだから、その様子をruby-graphvizとかで吐けばいいじゃんということでやってみた。 pngファイルをアニメーションgifに変換するのはこんな感じで。この辺を参考に。 convert -geometry 320x500! -delay 150 -loop 0 bellman_ford_example_a_uniq*.png bellman_ford_example_a.gif 俺はRubyで書いたわけだけど、こんなことをやってるid:mickey24に「それRでできるよ!!」と言われそうである。 単一始点最短路問題に対するその他のアルゴリズムベルマンフォードのアルゴリズムは単一始点最短路問題に対する
アルゴリズムと計算量
金庫破りと計算量膨張 n 桁の番号をもつ暗証ロックがあるとします。 2 桁であれば 00 〜 99 の 100 個の正解があるわけで、 0 番から順に入力していく解き方では、 最悪の場合は 100 手目に開きます。 99 が正解とは限らないので、平均的にはこれより早く解き終わります。 0 であるときの確率は 1/100 で、このときの手数は 1 手です。 1 であるときの確率は 1/100 で、このときの手数は 2 手です。 2 であるときの確率は 1/100 で、このときの手数は 3 手です。 3 であるときの確率は 1/100 で、このときの手数は 4 手です。 : 99 であるときの確率は 1/100 で、このときの手数は 100 手です。 つまり、平均手数は により、100 手目の約半分です。 ここでいう解き方をアルゴリズムといい、 問題を解くための手数 (てかず) のことを計
クイックソートをpthreadで並列化 - yarbの日記
クイックソートはソート対象領域をどんどん分割していく方式なので単純に並列化できるらしい。pthreadでやってみた。 pthread_createには関数へのポインタと、その関数への引数をvoid型ポインタで渡すようになっている。ということは複数の引数を渡すのって構造体にするのかなと思って、そう書いてみた。動いてるっぽい。 200万個のintの並べ替えだと、シングルスレッド処理のものに比べて7倍ぐらい速い気がする。うーん、7倍？ 追記：中途半端にしかソートができてなくて、なんかコレ、壊れてまっせ。。。 #include <stdio.h> #include <stdlib.h> #include <time.h> #include <pthread.h> #define NUM_THREADS 3 #define SWAP(type, x, y) do {type tmp = x; x =
アルゴリズムの天才 － ＠IT自分戦略研究所
本連載を初めて読む人へ：先行き不透明な時代をITエンジニアとして生き抜くためには、何が必要なのでしょうか。それを学ぶ1つの手段として、わたしたちはIT業界で活躍してきた人々の偉業を知ることが有効だと考えます。本連載では、IT業界を切り開いた117人の先駆者たちの姿を紹介します。普段は触れる機会の少ないIT業界の歴史を知り、より誇りを持って仕事に取り組む一助としていただければ幸いです。（編集部） 本連載は、2002年 ソフトバンク パブリッシング（現ソフトバンク クリエイティブ）刊行の書籍『IT業界の冒険者たち』を、著者である脇英世氏の許可を得て転載しており、内容は当時のものです。 ドナルド・クヌース（Donald Knuth）―― 元スタンフォード大学教授、TeX開発者 日本では、Knuthという彼の名字をクヌースと表記するが、外国でも彼の名前を何と呼ぶかが常に問題になるらしい。インターネ
追記型オブジェクトストレージ「Kastor」（pre-alpha） - Blog by Sadayuki Furuhashi
Facebookで写真配信のために使われているストレージシステム「Haystack」に関する情報が公開されました。（Needle in a haystack: efficient storage of billions of photos） Facebookは最初はNFSを使っていたようです。しかし写真の1枚1枚をファイルとして保存していたため、ディレクトリエントリなどのinodeメタデータの総量がキャッシュに収まらないサイズになってしまい、一つの写真を保存したり取り出したりするのにHDDのシークが複数回発生していたのがボトルネックになっていたそうです。 （もしかしたら「NetAppは高すぎた」のがもっと重要だったかも知れません：Facebook、独自の写真配信ネットワーク、Haystackを完成―収益性の改善に寄与か？） シークの問題を軽減するために、profile用などの小さな写真はキ
ベジェ曲線がわかった！ - ザリガニが見ていた...。
今までいろいろな説明を見てみたけど、頭では直感的に理解できていなかった。 制御点を動かした時、曲線がどのように変化するのか、イメージできなかった...。 そもそも、制御点と曲線の関係性が全く分かっていない...。 でも、てっく煮ブログさんid:nitoyonを一目見て、今までのモヤモヤが一瞬でクリアになってしまった！特に1と3の解説で使われている図やフラッシュを実際に操作してみると、難しい話は抜きにして、制御点を操作した時の曲線の心が分かってしまった気になる。 ベジエ曲線の仕組み (1) - 昔話 ベジエ曲線の仕組み (2) - ２次ベジエ曲線を詳しく ベジエ曲線の仕組み (3) - ３次ベジエ曲線 ベジエ曲線の仕組み (4) - ActionScript 3.0 でベジエ曲線を描く おおっー、感動！こんなにシンプルな方法で作図できるとは！（√2や円周率πを単純な数列から計算できることを知
参照の局所性 - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Locality of reference|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針に
近畿大学産業理工学部情報学科ニュース » Ruby言語で書いた２行マージソート
これまた、どうでもいいことですが。2行でマージソートが書けたので載せます。ただし、クイックソートと違って読みにくいのがちょっと納得いかないです。 def msort(a) a.size==1?a:merge(msort(a[0..(a.size/2-1)]),msort(a[(a.size/2)..-1])) end def merge(a,b) a==[]?b:(b==[]?a:(a[0]<=b[0]?[a[0]]+merge(a[1..-1],b):[b[0]]+merge(a,b[1..-1]))) end
B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 : 404 Blog Not Found
2009年01月31日01:00 カテゴリLightweight LanguagesMath アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 これなのですが.... 同じ文字列のn回繰り返しを作る最速の方法を探求してみた - muddy brown thang ちょっとした事情により、ある文字列のn回繰り返しを作る関数 (PHPでいうところのarray_repeat(), Perlで言うところの「"..." x n」、RubyやPythonで言うところの「"..." * n」) を高速に実装しなければならない状況に遭遇したのでベンチマークをとってみたところ、その結果がとても新鮮で驚いたので、これを共有しつつもダメ出ししてもらえないかなーと思って晒してみることに。 なぜかもっとシンプルな奴がなかったので。 以下、比較。初期値はIEにあわせてあります。Firefox/Saf
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Hot XXX Images, Best Porn Pics and Free Sex Photos on www.pornfalcon.com
GitHub - livedoor/cicindela2: a highly customizable recommendation engine written in perl + MySQL
PRoxy Diary(2009-02-04) - [研究室] STOCの論文の内容
セルオートマトンの「Star Wars」というルールがカッコよすぎる xe-kdoo(2008-11-22)
Home
