読者です 読者をやめる 読者になる 読者になる

SA-IS: SuffixArray線形構築: 訂正

common lisp algorithm

以前に書いたSA-ISの記事(及びソースコード)には明確な間違いがあったので訂正しておく。

間違い

確か以前の記事では「入力文字列の各LMS部分文字列が互いにユニークなら、初めのinduced-sortを終えた段階でSuffixArrayが求まる」というようことを何箇所かで書いていたように思うが、これは間違い。


理由は簡単。
一回目のinduced-sortのステップ一の段階では各LMS部分文字列の先頭位置がバケツに挿入されることになるが、もしそれらに重複する文字があった場合、同じ文字(で始まるsuffix)同士のバケツ内での位置は、それらの挿入順に依存することになる。
そして、この挿入を、最終的なソート順に合わせた順番で行うことは、この段階では不可能なため、ここで挿入されたSタイプの文字(が表すsuffix)同士が適切な順で並んでいる保証はない。

また、induced-sortのステップ二でバケツに挿入されるLタイプの文字の順番は、ステップ一で挿入されたSタイプの文字の順番に依存することになるので、これらの文字の順番も同様にソート順になっている保証はない。

つまり「入力文字列の各LMS部分文字列が互いにユニーク」な場合の、一回目のinduced-sortでは、各suffixはほぼソートされた状態になるが、細かい順番がステップ一での要素挿入順に依存してしまうため、完全なSuffixArrayを得るには至らない。

正しくは

一回目のinduced-sortで保証されている(得られる)のは、入力文字列に対する完全なSuffixArrayではなく、そのサブセット。
結果配列中の「各LMS部分文字列の先頭文字」に対応する要素の順番に関してはソート順となっていることが確か。
で、この「各LMS部分文字列の先頭文字」というのはinduced-sordのステップ一でバケツに挿入する要素と等しいので、この時点でinduced-sortのステップ一でのバケツへの適切な挿入順が判明したことになる。
後は、そのソート順に従ってステップ一で要素を挿入してinduced-sortを行えば、今度こそ完全なSuffixArrayが得られることとなる(はず…)

修正ソースコード

差分のみ掲載。

;;;;;;;;;;;;;;;;;;;;;;;;
;; 実際にSA-ISを行う関数
(defun sais-impl (str)
  (let* ((types (classify str))                ; 入力文字列をSとLに分類する
         (lms-blocks (calc-lms-blocks types))) ; LMS部分文字列列を求める
    (multiple-value-bind (s1 sa1 uniq?) (induced-sort str types lms-blocks)  ; induced-sort
      (if uniq?
          ;; 全てのLMS部分文字列がユニークな場合
          
          ;; 修正:
          ;; induced-sort関数の結果、
          ;; LMS部分文字列の先頭文字一の適切な挿入順が分かったので(s1)、
          ;; それをもとに、もう一度induced-sortを行う。
          (induce-sa2 str types s1 lms-blocks)

          ;; 旧(間違い): induced-sort関数の返り値をそのまま返していた
          ;; sa1
          
        ;; 重複する部分文字列がある場合は、簡約化された入力(s1)に対してsais-implを再帰的に適用し、
        ;; その結果に対して、もう一度induced-sortを行う。 ※ ただし、やることが若干ことなるので、上とは関数は別
        (induce-sa str types (sais-impl s1) lms-blocks)))))

;; 追加:
;; 入力文字列の各LMS部分文字列がユニークな場合の二回目のinduced-sort関数
(defun induce-sa2 (s ty s1 lms &aux (bkt (init-buckets s)) (i (length s1)))
  (let ((ordered-lms (make-array (length lms))))
    ;; LMS部分文字列列をsuffixのソート順に並び替えた配列を作成する
    (dotimes (i (length lms))
      (setf (aref ordered-lms (aref s1 i)) (aref lms i)))

    ;; 後は普通にinduced-sortを行う
    (induce (lambda ()
              (when (plusp i)
                (aref ordered-lms (decf i))))
            s ty bkt)))