SESからpatchする

OSC2日目の休憩時間に走り書きした。

narazuya@bokkko% ./diff cbabac abcabba
editDistance:5
LCS:caba
SES
A a
A b
C c
D b
C a
C b
A b
C a
D c
narazuya@bokkko%       

↑は前に書いたdiffの出力そのまま。SESはShort Edit Scriptの略で、
片方の文字列からもう片方の文字列に変換するための文字の追加や削除の最短手順を表す。
これが分かればpatchするのは簡単だ。以下、テキトーにでっちあげたpatch関数。

sequence patch (sequence seq, Ses<elem> ses) {
  std::vector< std::pair<elem, editType> > sesSeq = ses.getSequence();
  std::list<elem> seqLst(seq.begin(), seq.end());
  std::list< std::pair<elem, editType> > sesLst(sesSeq.begin(), sesSeq.end());
  typename std::list<elem>::iterator lstIt = seqLst.begin();
  typename std::vector< std::pair<elem, editType> >::iterator sesIt;
  for (sesIt=sesSeq.begin();sesIt!=sesSeq.end();++sesIt) {
    switch (sesIt->second) {
    case SES_ADD :
      seqLst.insert(lstIt, sesIt->first);
      break;
    case SES_DELETE :
      seqLst.erase(lstIt);
      ++lstIt;
      break;
    case SES_COPY :
      ++lstIt;
      break;
    default :
      break;
    }
  }
  sequence patchedSeq(seqLst.begin(), seqLst.end());
  return patchedSeq;
}

要素の追加と削除が頻繁に発生するので、listを使う。

今のところ、使い方はこんな感じ。

#include "diff.hpp"

int main(int argc, char *argv[]){
  std::string A(argv[1]);
  std::string B(argv[2]);

  onp::Diff<char, std::string> d(A, B);
  d.compose();

  onp::Ses<char> ses = d.getSes();

  std::string s1(A);
  std::string s2 = d.patch(s1, ses);

  std::cout << "before:" << s1 << std::endl;
  std::cout << "after:" << s2 << std::endl;

  return 0;
}

AからBへのSESをAと同じ文字列に適用すれば当然Bと同じ文字列が得られる。

narazuya@bokkko% ./patch cbabac abcabba
before:cbabac
after:abcabba
narazuya@bokkko%