うにゅーん、って感じだ

だいたいのコンテストサイトで橙か赤です、よく C#を書きます。

編集距離を時間 O(|S| |T| / w)、空間 O(|S| + |T|) で復元までやる

以下の記事のおまけです。

rian.hatenablog.jp

おまけなので前回以上に内容が雑です。

編集距離 (Levenshtein distance) を時間計算量 $\Theta(|S| |T| / w)$、空間計算量 $\Theta(|S| + |T|)$ で復元までします（$w$ はワードサイズ）。

  • 諸注意
    • この記事では「復元なし」「復元あり」とはそれぞれ以下のような問題設定を指します。
      • 復元なし：編集距離を求める
      • 復元あり：編集距離が最小になるような編集操作列を実際に求める
    • 前回以上に理解していないのであくまで紹介記事と捉えていただけると嬉しいです。

時間 $\Theta(|S| |T| / w)$、空間 $\Theta(|S| + |T|)$、復元なし

ジャッジ

参考文献

triple-four.hatenablog.com

概要

上の参考文献をガン見します。

一部間違ってるところがある（Cp = Rn | ~(Rp & D0) とあるが正しくは Cp = Rn | ~(Rp | D0) のはず）ので気合いで直し、さらにこのあと Hirschberg's algorithm で復元することを考えて $\mathrm{Cp}, \mathrm{Cn}$ ではなく $\mathrm{Rp}, \mathrm{Rn}$ から編集距離を算出しておきます。

さらに、以下では式変形をすることで各ビット列の長さを $|S| + 1$ ではなく $|S|$ にしています。

コード

inline int idx(char c) {
  if (c <= '9') return c - '0';
  else if (c <= 'Z') return c - 'A' + 10;
  else return c - 'a' + 36;
}

int levenshtein(const string& s, const string& t) {
  int n = s.size();
  int w = (n + 63) >> 6;
  vector<vector<uint64_t>> m(62, vector<uint64_t>(w));
  for (int i = 0; i < n; ++i) {
    m[idx(s[i])][i >> 6] |= 1ULL << (i & 63);
  }
  vector<uint64_t> rp(w, uint64_t(-1)), rn(w);
  for (auto& c : t) {
    const auto& mc = m[idx(c)];
    for (int i = 0, carry = 0, cpc = 1, cnc = 0; i < w; ++i) {
      int nx = (mc[i] & rp[i]) > ~rp[i] || ((mc[i] & rp[i]) == ~rp[i] && carry);
      uint64_t d0 = (((mc[i] & rp[i]) + rp[i] + carry) ^ rp[i]) | mc[i] | rn[i];
      uint64_t cn = rp[i] & d0;
      uint64_t cp = rn[i] | ~(rp[i] | d0);
      rn[i] = (cp << 1 | cpc) & d0;
      rp[i] = cn << 1 | cnc | ~(cp << 1 | cpc | d0);
      carry = nx;
      cpc = cp >> 63;
      cnc = cn >> 63;
    }
  }
  int d = t.size();
  for (int i = 0; i < n; ++i) {
    d += (rp[i >> 6] >> (i & 63)) & 1;
    d -= (rn[i >> 6] >> (i & 63)) & 1;
  }
  return d;
}

時間 $\Theta(|S| |T| / w)$、空間 $\Theta(|S| + |T|)$、復元あり

ジャッジ

概要

bitset + Hirschberg's algorithm でできます。

韓国でもメジャーではないらしく、投稿時点ではこの計算量の提出はありませんでした（https://www.acmicpc.net/problem/status/17161 のスクリーンショット）。

コード

inline int idx(char c) {
  if (c <= '9') return c - '0';
  else if (c <= 'Z') return c - 'A' + 10;
  else return c - 'a' + 36;
}

pair<vector<uint64_t>, vector<uint64_t>> _levenshtein(const string& s, const string& t) {
  int n = s.size();
  int w = (n + 63) >> 6;
  vector<vector<uint64_t>> m(62, vector<uint64_t>(w));
  for (int i = 0; i < n; ++i) {
    m[idx(s[i])][i >> 6] |= 1ULL << (i & 63);
  }
  vector<uint64_t> rp(w, uint64_t(-1)), rn(w);
  for (auto& c : t) {
    const auto& mc = m[idx(c)];
    for (int i = 0, carry = 0, cpc = 1, cnc = 0; i < w; ++i) {
      int nx = (mc[i] & rp[i]) > ~rp[i] || ((mc[i] & rp[i]) == ~rp[i] && carry);
      uint64_t d0 = (((mc[i] & rp[i]) + rp[i] + carry) ^ rp[i]) | mc[i] | rn[i];
      uint64_t cn = rp[i] & d0;
      uint64_t cp = rn[i] | ~(rp[i] | d0);
      rn[i] = (cp << 1 | cpc) & d0;
      rp[i] = cn << 1 | cnc | ~(cp << 1 | cpc | d0);
      carry = nx;
      cpc = cp >> 63;
      cnc = cn >> 63;
    }
  }
  return { rp, rn };
}


void levenshtein(string s, string t, vector<pair<char, char>>& result) {
  if (s.size() <= 1 || t.size() <= 1) {
    int si = 0, tj = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
      for (int j = 0; j < (int)t.size(); ++j) {
        if (s[i] == t[j]) {
          si = i;
          tj = j;
        }
      }
    }
    {
      int i = 0, j = 0;
      while (i < (int)s.size() || j < (int)t.size()) {
        if (j < tj || i >= (int)s.size()) {
          result.emplace_back('a', t[j]);
          ++j;
        }
        else if (i < si || j >= (int)t.size()) {
          result.emplace_back('d', s[i]);
          ++i;
        }
        else {
          assert(i == si && j == tj);
          if (s[i] == t[j]) {
            result.emplace_back('c', t[j]);
          }
          else {
            result.emplace_back('m', t[j]);
          }
          ++i;
          ++j;
        }
      }
    }
    return;
  }
  int n = s.size();
  int l1 = t.size() / 2;
  int l2 = (int)t.size() - l1;
  auto lef = _levenshtein(s, t.substr(0, l1));
  reverse(s.begin(), s.end());
  reverse(t.begin(), t.end());
  auto rig = _levenshtein(s, t.substr(0, l2));
  reverse(s.begin(), s.end());
  reverse(t.begin(), t.end());
  int val = 0;
  int min_val = val;
  int min_idx = 0;
  for (int i = 0; i < n; ++i) {
    val += (lef.first[i >> 6] >> (i & 63)) & 1;
    val -= (lef.second[i >> 6] >> (i & 63)) & 1;
    val -= (rig.first[(n - i - 1) >> 6] >> ((n - i - 1) & 63)) & 1;
    val += (rig.second[(n - i - 1) >> 6] >> ((n - i - 1) & 63)) & 1;
    if (min_val > val) {
      min_val = val;
      min_idx = i + 1;
    }
  }
  levenshtein(s.substr(0, min_idx), t.substr(0, l1), result);
  levenshtein(s.substr(min_idx), t.substr(l1), result);
}

あとがき

むずすぎる