「4人のロシア人の方法」で編集距離を高速化する
ちょっと前に「4人のロシア人の方法(Method of Four Russians)」というのを論文で見かけて面白かったので紹介しておく。
簡単に言ってしまうと、ある処理を高速化したい時にデータ全体を小さなブロックに分割してブロック単位での結果を事前に計算したテーブルで持っておくよ、というアルゴリズム。
名前は知らなくてもアルゴリズム自体は知ってる人は多いかもしれない。
アルゴリズム自体は汎用的なものだが編集距離の高速化を例として説明するのが一般的なようなのでそれに倣う。
文章で書くとごちゃごちゃするのでスライドで。もっふる。
※追記：↑のスライド、正直自分でもわかりやすいとは思えないので余裕があったら後で補足します。待てないよって人は↓の本を読んでください。
ちなみにこの手法は「バイオインフォマティクスのためのアルゴリズム入門」という書籍にわかりやすい解説が書いてあるので、興味がある人は是非。
そうそう。もっふる実在してた。もちで作ったワッフルなんだとか。へええ。
