「4人のロシア人の方法」で編集距離を高速化する - EchizenBlog-Zwei

2012/05/20 43 users アルゴリズム 論文 アルゴリズム自体 ブロック単位 テーブル

計算機科学ちょっと前に「4人のロシア人の方法(Method of Four Russians)」というのを論文で見かけて面白かったので紹介しておく。簡単に言ってしまうと、ある処理を高速化したい時にデータ全体を小さなブロックに分割してブロック単位での結果を事前に計算したテーブルで持っておくよ、というアルゴリズム。名前は知らなくてもアルゴリズム自体は知ってる人は多いかもしれない。Method of F... 続きを読む

編集距離が近いメソッドを勝手に呼ぶ - hitode909のダイアリー

2011/09/18 49 users ダイアリー hitode909 args method

メソッド名を打ち間違えてメソッドを呼べないことがあって寂しかったので，呼ぼうとしたメソッドがないときは編集距離が近いメソッドを勝手に呼ぶのを作ってみた． module AutoCall def method_missing(method, *args) __send__(find_nearest_method(method), *args) end private def find_nearest... 続きを読む

Luceneの曖昧検索を100倍高速化したアルゴリズム - nokunoの日記

2011/03/28 32 users Lucene nokuno オートマトン アルゴリズム 実装

@nobu_k さんのつぶやきでこのエントリを知りました。Changing Bits: Lucene’s FuzzyQuery is 100 times faster in 4.0Luceneで曖昧検索を効率化した話です。 最初の実装では、転置インデックスを全探索して編集距離がN以下の単語を拾っていたレーベンシュタインオートマトンという、編集距離がN以下の単語のみをアクセプトするオートマトンを利用... 続きを読む

プログラミング：diffの動作原理を知る～どのようにして差分を導き出すのか｜gihyo.jp … 技術評論社

2011/03/11 921 users diff アルゴリ アルゴリズム コマンド プログラミング

diffの動作原理を知る～どのようにして差分を導き出すのか2011年3月11日初出：Software Design2009年6月号（2009年5月18日発売）久保達彦diff, アルゴリズム, UNIXプログラム, 編集距離, アルゴリズム, エディットグラフ, diffこの記事を読むのに必要な時間：およそ 7 分1234UNIXの基本的なコマンドの1つであるdiff。これに実装されているアルゴリ... 続きを読む