A Fast and Practical Bit-Vector Algorithm for the Longest Common Subsequence ... - todo314 @ ウィキ

A Fast and Practical Bit-Vector Algorithm for the Longest Common Subsequence Problem

• Maxime Crochemore, Costas S. Iliopoulos, Yoan J. Pinzon, James F. Reid
• IPL(Information Processing Letters) 2001

概要

• bit vectorによる爆速LCS、正確にはその長さ
• 時間: O(nm/w)
• 空間: O(m/w)
  • w: ビット数

事前知識

• Σ: アルファベット
• s=|Σ|
• LCSの時間計算量の下界: Ω(nlogm)
• 最速
  • Σサイズ制限無: $$ O(n^2 \log \log n/\log n) $$
  • Σサイズ制限有: $$ O(n^2 /\log n) $$
• AllisonとDixのアルゴリズム
  • O(nm/w)、但しビット演算が5回

提案アルゴリズムCIPR

• ビット演算の回数5->4
• しかも減算じゃなくて加算
• DP配列を書いた時に、隣り合う要素は1しか変わらんので、ビットで表現できる
• ΔL[i,j]=L[i,j]-L[i-1,j]
• 計算のために ΔL'=NOTΔL を求める
• 前計算
  • M[a]_i=[x_i=a]
  • O(m|Σ|)
  • Σがやばいならハッシュ
• ΔL'の計算
  • a=y_jとする
  • ΔL'_jをΔL'_{j-1}とM[a]_{1:m}とM'[a]_{1:m}で更新
  • $$ \Delta L'_j = (\Delta L'_{j-1} + (\Delta L'_{j-1} \texttt{ AND } M[y_j])) \texttt{ OR } (\Delta L'_{j-1} \texttt{ AND } M'[y_j]) $$
    • ここで使っている演算はAND, OR, AND, +の4つ
  • 一番最初(j=0)は2^m-1、つまり全部1
• 上の更新の後にΔL'_j[m+1] = 1だったらLCSの長さを+1

その他

• 実験でAllison&Dixと比較すると、CIPRの法がめっちゃ速い
• もしLCSそのものが欲しい時には分割統治をすれば同じ計算量で構築できる

まとめ

• コンテスト的には長さ10^5の2つの文字列のLCS長が分かるので、強い
• 大体1secで終わる

IPL LCS bit parallel

2013-12-08 23:31:24 (Sun)