Diff
出典: やる気向上作戦
目次 |
何ですかこれは？
二つのシーケンスのLongest Common Subsequence, Longest Common Subsequence Distance及びShortest Edit Scriptを求めるクラス。 Subversionのコードを、C++に移植したものです。
アルゴリズムは、"An O(NP) Sequence Comparison Algorithm" (Sun Wu et al.)に述べられているものと同一で、計算量は最悪でO(NP)、平均的にはO(N+PD)です。ただし、N=二つのシーケンスの長さの和、P=D/2-Δ/2、D=LCS距離、Δ=二つのシーケンスの長さの差です。
ここでいうLCS距離(longest common subsequence distance)は、あるシーケンスを別のシーケンスに変化させるために必要な、シンボルの挿入及び削除操作の最小の回数です。すなわち、置換操作を禁じたLevenshtein距離になります。
使い方
#include <string>
#include "diffpp.h"
typedef diffpp::LCS<std::string::iterator> lcsc;
typedef diffpp::SES<std::string::iterator> sesc;
std::string a("aabc");
std::string b("dacb");
// LCSに与えるiteratorは、forward iterator以上の機能を備えていなければならない。
lcsc lcs(a.begin(), a.end(), b.begin(), b.end());
sesc ses(lcs);
lcsc::iterator it;
for (it=lcs.begin(); it!=lcs.end(); ++it) {
std::cout << std::string(it->begin[0], it->end[0]);
}
sesc::iterator sit;
for (sit=ses.begin(); sit!=ses.end(); ++sit) {
switch (it->command) {
case SES<std::string::iterator>::ADD:
std::cout << "A " << std::string(sit->begin, sit->end) << std::endl;
break;
case SES<std::string::iterator>::DELETE:
std::cout << "D " << std::string(sit->begin, sit->end) << std::endl;
break;
case SES<std::string::iterator>::COPY:
std::cout << "C " << std::string(sit->begin, sit->end) << std::endl;
break;
}
}
ライセンス
Subversionに準じます。
