最長共通部分系列長（LCS）を求めるJavaプログラム - sternhellerの日記
素朴に実装。LCS長が何たるかは別のページを参照してください。 LCSのアルゴリズムは、系列Xのi番目をxi、系列Yのj番目をyjとすると、 i = 0 または j = 0 のとき、 LCS(i, j) = 0 i, j > 0 かつ xi == yj のとき、 LCS(i, j) = LCS(i-1, j-1) + 1 i, j > 0 かつ xi != yj のとき、 LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1)) ですが、Javaは配列が0オリジンなので、このまま素直に実装してしまうと系列XとYの一文字目が一致した場合でもLCS長が0になってしまいます。そこでちょっとトリッキーな実装にしてみました。 public class LongestCommonSubsequence { // 実行サンプル public static void main(S
最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリー
部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のことです。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と言います。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と言います。 X = <A, B, C, B, D, A, B> Y = <B, D, C, A, B, A> という二つの系列から得られる LCS は <B, C, B, A> で、その長さは 4 です。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列ですが、最長ではないのでこれらは LCS ではありません。また、LCS は最長であれば位置はどこでも良いので、この場合 <B, D, A, B> も LCS です。 LCS は動的計画法 (Dynamic Prog
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
交差点問題 - mad日記
大学のアルゴリズムとデータ構造という授業で題材になってた問題。それにBGL(Boost Graph Library)で取り組んでみた。 交差点問題 左図の様な交差点がある。 全ての進路に信号が設置してある。 矢印方向にしか進むことができない。 交差する進路は同時に信号を点灯することができない。 効率良く車を進めることのできる点灯の仕方を求めよ。 という問題。 まず、こういった現実の問題を数学のモデルに置き換える。それが右図。 ABなどの一つのノードがA->Bなどと進む進路の信号を表す。 交差する進路は互いに線で結ばれている。 同時に点灯する信号のノードを同じ色で塗る。 線で結ばれているノードは同じ色で塗られていてはいけない。 色の数が最も少なくなるような塗わけかたを探せ。 という感じで、モデル化することができる。"色"という概念で考えるのは四色問題がその起源なのかな。 んで、この問題は「N
SoftURR -- a preliminary software implementation of URR
SoftURR‐URRのソフトウェアによる実装の試み version 0.1 公開。 Project Page ソースコード softurr-0.1.tar.gz 1. SoftURRとは SoftURRは、URR(Universal Representation of Real numbers;万能数値表現法)の ソフトウェアによる実装です。 URRは、算術的に美しく、実用的にも優れた浮動小数点数の表現方法ですが、 ハードウェアで実現することが容易でなかったため、 IEEE 754のように広く用いられることはありませんでした。 SoftURRでは、"動く"URRをソフトウェア(x86の整数演算)で実装してみることで、 URRを実用化するときに必要となってくる知識や経験を蓄積し、 最終的には、(夢は大きく！)規格化に向けた提言を行うことを目標としています。 2. U
暗号の危殆化と新しいアルゴリズム — 旧メイン・ブログ | Baldanders.info
L が鍵長で N が被署名データのサイズです。 FIPS186-3 ドラフト案ではこの組み合わせの中から選択して使うべきとしています。 ところで署名・暗号に使う鍵の長さはどの程度が適当でしょうか。 確かに長ければ長いほど安全といえますが， 長すぎる鍵はとりまわしが不便です。 この件については IPA/ISEC による 「将来の暗号技術に関する安全性要件調査」 が参考になります。 詳しい内容はそちらを読んでいただくとして， 結論としては， 今後10年のスパンで考えるなら共通鍵暗号の鍵で128ビット程度で十分なようです。 128ビットの共通鍵暗号鍵を公開鍵暗号鍵に換算するとどの程度になるかは難しいですが（先ほど紹介した調査報告書では参考値としながらもかなり大きい鍵を要求しているように読めましたが）， これについては RSA Security による 「A Cost-Based Security
A 10-MINUTE DESCRIPTION OF HOW JUDY ARRAYS WORK AND WHY THEY ARE SO FAST
A 10-MINUTE DESCRIPTION OF HOW JUDY ARRAYS WORK AND WHY THEY ARE SO FAST By Doug Baskins, doug@sourcejudy.com October 16, 2001, Revised July 2002 As the inventor of the Judy algorithm I've been asked repeatedly, "What makes Judy so fast?" The answer is not simple, but finally I can share all of the details. (In June 2002, Judy was opened sourced with a LGPL license and hosted at http://sourceforge
Matzにっき(2006-06-28)
<< 2006/06/ 1 1. [Ruby] Bitwise Magazine :: Ruby programming tutorial 2. [Ruby] Bitwise Magazine :: Ruby Programming 3. [Ruby] mandatory arguments after splat 2 1. 平成17年度情報化月間 第26回 U20プログラミングコンテスト 2. [OSS] ZDNet.com オープンソースブログ:成功するオープンソースビジネスモデル7選 3. [Ruby] Ruby のブロックってオブジェクトじゃないよね。これって“驚き最小の法則”に反しない？ 3 1. SANYO もちつきベーカリー 2. 引っ越し 3. [教会] バプテスマ会 4. 『4797336021』 4 1. [教会] 第一安息日 5 1. マルチメディア通信と分散処理研究
ベイジアンフィルタについて
最近話題のベイズ理論を用いたフィルタについて整理してみました．まず，ベ イズ理論が注目され始めたというニュースを最初にみたのが，ＭＳも注目する “ベイズ”って何だ(oricom.co.jp)でした． このときは対して気にもとめていませんでしたが，再度興味をそそられ出した のが，グーグル、インテル、MSが注目するベイズ理論(CNET)のニュース． MSだけならまだしも，Googleが，というのが自分的には大きかったです．しか し，このニュースだけでは，この技術が具体的にどのように採用されるのか， 特に検索エンジンのような大規模なものに適用可能かどうかは大きな疑問でし た． そもそも，このベイズ理論がどこに聞いてくるのかということを考えるとその 疑問は自然だと思います．ベイズ理論（ベイズ推定）は，過去に起きた事象の 確率を利用して未来を予測する手法です．そのため，直感的にはユーザごとの 最適化
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
