C++ プログラムで使用する LCS アルゴリズムの (空間) 効率的な実装を探しています。入力は、整数の 2 つのランダム アクセス シーケンスです。
私は現在、LCS に関するウィキペディアのページから動的プログラミング アプローチを使用しています。ただし、それはメモリと時間で O(mn) の動作をし、より大きな入力に対してメモリ不足のエラーが発生して死にます。
Hunt-Szymanski、Masek、Paterson など、メモリ使用量を大幅に改善する Hirschberg のアルゴリズムについて読んだことがあります。これらを実装するのは簡単ではないので、既存の実装で自分のデータで試してみたいと思います。そのようなライブラリを知っている人はいますか？テキストの差分ツールはかなり一般的であるため、オープンソースのライブラリがいくつかあるはずだと思いますか?
5332 次
3 に答える
3
そのようなものを検索するときは、scholate.google.com を試してください。学術的な作品を見つけるには、はるかに優れています。http://www.biotec.icb.ufmg.br/cabi/artigos/seminarios2/subsequence_algorithm.pdf このドキュメント、「最長共通サブシーケンス アルゴリズムの調査」が見つかりました。
于 2010-09-09T06:16:30.320 に答える
0
Hirschberg's Algorithmには JavaScript 実装が組み込まれています: ほぼ C.
于 2013-09-30T20:03:07.433 に答える
0
C++ではなくPythonですが、使えると思います。
于 2011-09-22T12:34:44.810 に答える