SA-IS: SuffixArray線形構築: 訂正
以前に書いた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)))