エディットグラフでの最短経路探索 - pocketberserkerの爆走
diffっぽいもの - pocketberserkerの爆走ではプログラムを見せるだけで終了してしまったので、今回は最短経路探索についてお話します。 以下の図は、strengthとstringのエディットグラフに、編集距離(Edit Distance)を求める際に通った座標(以降ではノードと呼びます)と通った順番を付加したものです。 最短経路は最終ノードから逆順に道をたどればとれるのですが、プログラムにしようとすると編集距離を求めるアルゴリズムにいくつもの処理を加えなければならなくなり非常にめんど……わかりづらいです。 そこで今回の実装では、ノードを通る時にひとつ前に通ったノードを親ノードとして記憶することにしました。 つまり、以下のようにノードがつながっています。 プログラムではノード生成時にデータを放り込むだけです。 さて、最終ノードに到達した（ということにしておいてください）ので、こ
レコメンデーションとエディットグラフ
レコメンデーションとエディットグラフ：コーディングに役立つ！ アルゴリズムの基本（10）（1/4 ページ） プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部） 実際のアプリケーションで使われるアルゴリズム これまで見てきたアルゴリズムは、実際のアプリケーション開発の際にそのまま使われることはあまりなく、プログラム言語やライブラリなどですでに機能が用意されているものが大半でした。 今回は最終回ということで、実際のアプリケーション開発でそのまま使えるものを紹介したいと思います。 レコメンデーション ECサイトで、「あなたにお勧めの商品」を表示していることがあります。いろいろなデータベースや行動履歴のデータから、その人ごとにお勧めの商品をはじき出して推薦する機能をレコメンデー
文書比較（diff）アルゴリズム
文書比較（diff）アルゴリズム 前のドキュメント 次のドキュメント ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。 これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。 オリジナル論文は以下のＷｅｂサイトから入手可能である。 http://www.cs.arizona.edu/people/gene [1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266 [2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparis
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
