15 章「真珠の列」 - 珠玉のプログラミング（Programming Pearls）

珠玉のプログラミングの15章。

15.5.1

タグを無視すればよい。レイアウト情報の削除をする。

15.5.2

全ての単語を set/map に保持する。その分だけメモリが必要。

15.5.3

incword の中は探索に時間がかかっているのでそこまで速くならない。

15.5.4

略。

15.5.5

map をソート。

15.5.6

サフィックス配列を2分探索して近い物を見つける。

15.5.7

全て同じ文字だと比較に多くの時間が割かれるので遅くなる。実際に計測したが 10 倍以上遅くなった。

15.5.8

max = M としてスタートすればよい。

15.5.9

suffix array に付属データとしてどちらの配列のデータかのフラグを持たせる。

15.5.10

最後の出力の時に前後の文字を見て最長を決める。

15.5.11-15

マルコフ連鎖は以前、書いた事があるので略。

15.5.16

適当な文章を見つけてきて suffix array を作り重複している単語をリストに入れる。

15.5.17

BlockSorting を利用した圧縮に使われているらしい。

コード

;; Programming Pearls Chapter 15
;; Programming Pearls Chapter 15
(import (rnrs)
        (mosh)
        (mosh file)
        (mosh control)
        (only (srfi :13) string<= string-prefix-length)
        (mosh test))

(define (make-suffix-array str)
  (let1 vec (make-vector (string-length str))
    (do ([i 0 (+ i 1)])
        ((= i (vector-length vec)))
      (vector-set! vec i i))
    (let1 len (string-length str)
      (vector-sort! (lambda (i j)
                      (string<= str str i len j len))
                    vec))
    vec))

(define (find-longest-shared str sa)
  (let loop ([i 0]
             [max-index 0]
             [max-len 0])
    (cond
     [(= (- (vector-length sa) 1) i)
      (substring str max-index (+ max-index max-len))]
     [else
      (let* ([len (string-length str)]
             [common-len (string-prefix-length str str (vector-ref sa i) len (vector-ref sa (+ i 1)) len)])
        (if (> common-len max-len)
            (loop (+ i 1) (vector-ref sa i) common-len)
            (loop (+ i 1) max-index max-len)))])))

(define (main args)
  (let1 content (file->string (cadr args))
    (write (find-longest-shared content (make-suffix-array content)))))

(main (command-line))