問題タブ [lcs]

2つの文字列の間に存在する可能な最長のサブシーケンスの量を計算しようとしています。

例：String X = "efgefg"; 文字列Y="efegf";

出力：最長の一般的なシーケンスの数は次のとおりです：3（つまり、efeg、efef、efgf-これはアルゴリズムによって計算する必要はありません。デモのためにここに示しています）

ここでの一般的な考え方に基づく動的計画法を使用して、O（| X | * | Y |）でこれを行うことができました：最も安いパスアルゴリズム。

より良いランタイムでこの計算を効率的に行う方法を誰かが考えることができますか？

-ジェイソンのコメントに応えて編集。

私はFlex/AS3で（簡単にするために）XMLエディターで作業しています。元に戻す/やり直し機能を提供する必要があります。

もちろん、1つの解決策は、編集のたびにソーステキスト全体を保存することです。ただし、メモリを節約するために、代わりにdiffを保存したいと思います（これらのdiffは、自動保存のために更新をサーバーに送信するためにも使用されます）。

私の質問は、これらのXMLの変更を追跡するためにプレーンテキストのdiffアルゴリズムを使用できますか？

インターネットでの私の調査は、私がそうすることができないことを示しています。しかし、私は明らかに何かが欠けています。平文diffは、次のような機能を提供します。

XMLは単なるテキストですが、なぜdiff（）とpatch（）を使用してテキストを確実に変換できないのでしょうか。

例：私が詩人だとしましょう。詩を書くときは、ファンキーな句読点をたくさん使います... <、/、>のように。（これでどこに行くのかわかるかもしれません...）diffを使用して元に戻す/やり直し機能を提供するアプリケーションで詩を書いている場合、編集を元に戻す/やり直すと詩が文字化けしますか？ただのテキストです！なぜそれがアルゴリズムに違いをもたらすのですか？

私は明らかにここで何かを得ていません...説明してくれてありがとう！:)

アップデート：

平文アルゴリズムを使用したXMLの差分に関して私が遭遇したいくつかの議論：

• http://code.google.com/p/google-diff-match-patch/wiki/Plaintext
• プレーンテキストのgoogle-diff-match-patchのように、htmlstringに対するJS diffライブラリはありますか？

また、コマンドパターンがUndo/Redoを実装するためのより良い方法である可能性が高いことを理解しています。簡単にするためにユースケースを簡略化しましたが、それでもXML差分が最善のアプローチだと思います。

2 つの非常に大きな文字列があり、それらのLongest Common Substringを見つけようとしています。

1 つはサフィックス ツリーを使用する方法(複雑な実装ですが、非常に複雑であると想定されます) であり、もう 1 つは動的プログラミング方法です(どちらも上記のリンク先の Wikipedia ページで言及されています)。

動的計画法の使用

問題は、動的計画法の実行時間が非常に長いことです (複雑さはO(n*m)で、nとmは 2 つの文字列の長さです)。

私が知りたいこと (接尾辞ツリーの実装にジャンプする前に):共通部分文字列の長さだけを知りたい場合 (共通部分文字列自体ではなく)、アルゴリズムを高速化することは可能ですか?

2つのシーケンスX[1..m]とY[1..n]を考えてみましょう。メモ化アルゴリズムは、時間O（m * n）でLCSを計算します。LCS wrt timeを見つけるためのより良いアルゴリズムはありますか？斜めにメモ化すると、O（min（m、n））の時間計算量が得られると思います。

C++ プログラムで使用する LCS アルゴリズムの (空間) 効率的な実装を探しています。入力は、整数の 2 つのランダム アクセス シーケンスです。
私は現在、LCS に関するウィキペディアのページから動的プログラミング アプローチを使用しています。ただし、それはメモリと時間で O(mn) の動作をし、より大きな入力に対してメモリ不足のエラーが発生して死にます。
Hunt-Szymanski、Masek、Paterson など、メモリ使用量を大幅に改善する Hirschberg のアルゴリズムについて読んだことがあります。これらを実装するのは簡単ではないので、既存の実装で自分のデータで試してみたいと思います。そのようなライブラリを知っている人はいますか？テキストの差分ツールはかなり一般的であるため、オープンソースのライブラリがいくつかあるはずだと思いますか?

Cで最長共通部分列問題を実装していました。再帰バージョンのソリューションと動的計画法バージョンの実行にかかる時間を比較したいと思います。さまざまな入力の両方のバージョンでLCS関数を実行するのにかかる時間をどのように見つけることができますか？また、SciPyを使用してこれらの値をグラフにプロットし、時間計算量を推測できますか？

前もって感謝します、

かみそり

再帰的および動的プログラミングアプローチにおける最長共通サブシーケンス問題について、入力のサイズに対して時間をプロットしたいと思います。これまで、私は lcs 関数を両方の方法で評価するためのプログラムを開発してきました。単純なランダム文字列ジェネレーター (ヘルプはこちらから) と、グラフをプロットするプログラムです。次に、これらすべてを次の方法で接続する必要があります。

今、これらすべてを接続する必要があります。つまり、lcs を計算する 2 つのプログラムは、単純なランダム文字列ジェネレーターからの出力をコマンド ライン引数としてこれらのプログラムに与えて、約 10 回実行する必要があります。

これらのプログラムの実行にかかった時間が計算され、使用された文字列の長さと一緒に次のようなファイルに保存されます。

これは python プログラムによって解析され、次のリストに入力されます

そして、グラフがプロットされます。上記に関して、以下の質問があります。

1) ある C プログラムの出力をコマンドライン引数として別の C プログラムに渡すにはどうすればよいですか?

2)関数の実行にかかる時間をマイクロ秒単位で評価する関数はありますか? 現在、私が持っている唯一のオプションは、UNIX の時間関数です。コマンドラインユーティリティであるため、扱いが難しくなります。

どんな助けでも大歓迎です。

圧縮されていないサフィックス ツリーを実装しました。文字列内で最も長く繰り返される部分文字列を見つける問題を解決する方法を知りたかったのです。2 つの子を持つ最も深い内部ノードを見つけなければならないことはわかっていますが、これをどのようにコーディングすればよいでしょうか。また、最も長く繰り返される部分文字列が何であるかを知るにはどうすればよいでしょうか。JAVAのコードに興味があります。PlsはJavaの実装を提供します。参考までに、私のTrieNodeは次のようになります

3 つ以上の文字列の最長共通部分列を見つけようとしています。ウィキペディアの記事には、2 つの文字列に対してこれを行う方法が詳しく説明されていますが、これを 3 つ以上の文字列に拡張する方法が少しわかりません。

2文字列のLCSを求めるライブラリはたくさんあるので、できればそのうちの1つを使いたいです。3 つの文字列 A、B、C がある場合、A と B の LCS を X として見つけてから、X と C の LCS を見つけることは有効ですか、それとも間違った方法ですか?

次のようにPythonで実装しました。

これは「ba」を出力しますが、「baa」のはずです。