複数の文字列を1passで検索
無駄に長くなりそうなので先に結論から。
バカな文字列検索と比べると速い文字列の検索のコードを書きました。
オートマトンとか使ってるからちょっと格好良くなった気分です。
(defvar *test-data* #("This ''text'' is bold sample."
"This '''text''' is italic sample."
"This %%text%% is torikeshi sample."
"This ((text)) is footnote sample."))
(defun aho-search (str)
(cond ((search "'''" str) 'italic)
((search "''" str) 'bold)
((search "%%" str) 'torikeshi)
((search "((" str) 'footnote)))
(defun use-dfa (str)
(dfa-multi-search (str)
"''" 'bold
"'''" 'italic
"%%" 'torikeshi
"((" 'footnote))
(defun bench ()
(time (dotimes (i 100000) (aho-search (aref *test-data* (mod i 4)))))
(time (dotimes (i 100000) (use-dfa (aref *test-data* (mod i 4))))))
aho-searchが「バカな文字列検索」。
use-dfaが「今回作った文字列検索」。
CLISPとSBCLでbenchを呼んで2つの関数の速度を比べてみました。
;;;CLISP > (bench) ;; aho-search Real time: 2.924899 sec. Run time: 2.813147 sec. Space: 0 Bytes ;; use-dfa Real time: 0.822901 sec. Run time: 0.779974 sec. Space: 11600000 Bytes GC: 17, GC time: 0.177573 sec. NIL
;;;SBCL * (bench) ;; aho-search Evaluation took: 0.391 seconds of real time 0.367416 seconds of total run time (0.367416 user, 0.000000 system) 93.86% CPU 584,719,558 processor cycles 0 bytes consed ;; use-dfa Evaluation took: 0.079 seconds of real time 0.057791 seconds of total run time (0.057791 user, 0.000000 system) 73.42% CPU 118,089,578 processor cycles 1,601,536 bytes consed
めちゃくちゃ速くなった反面、メモリを使いすぎてます。
原因は不明。どうやってメモリ使用量を減らせれるかが今後の課題です。
(ここまで結論でした。)
—
ちょっとずつですが、Common LispでWikiをつくってます。
で、Wiki文法からHTMLへの変換の際の文字列処理の話を少し。
Wiki文法からHTMLへの変換規則の一例として、
– 「”bold”」と出会ったら「<b>bold</b>」に変換
– 「”’italic”’」と出会ったら「<i>italic</i>」に変換
といったものがあります。
で、私が「とりあえず動けばいいや」で最初に書いたコードはというと、
searchで文字列から「”’」を探して変換して、「”」を探して変換して…
と言ったものでした。非常にばかばかしくて素晴らしいです。
「じゃあ、正規表現を使えばええやん」
という意見が飛んできそうですが、それじゃあ面白くない
正規表現を使っても以下のような問題がありそうです。
1) 変換規則の数だけ文字列全体を走査しないといけない
2) 「”」の前に「”’」を探さないといけないといった制約がある
(拡張された正規表現をガリガリ書ける人は上手く書けるのかもしれませんが…)
「単純な文字列の変換処理くらい1passで終わらせたいよね」という考えを前提にして、
「検索候補が複数書けるsearchがあればいいんじゃないか」という結論にたどり着きました。
(multi-search "''" "'''" "%%" "((" target)
=> (最初に)どの文字列にtargetの何文字目でヒットしたか
どの文字列にヒットしたかであとで条件分岐するのはほぼ確実なんだから
ということで、
(multi-search (target pos)
"''" `(bold at ,pos)
"'''" `(italic at ,pos)
"%%" `(torikeshi at ,pos)
"((" `(footnote at ,pos))
こんな風に書けるようにしよう。
と、目標を定めたところで作り始めました。
「探す文字列は先に決まっているんだから、効率のよいコードを生成しよう。」
ということで、決定性有限オートマトンを作って探索をすることに。
だいたいこんな感じです。
文字列のリスト -> NFA -> DFA -> Lispコード
(NFA : 非決定性オートマトン, DFA : 決定性オートマトン)
「NFAはすぐに作れるし、DFAに変換するのも教科書的なやり方で充分だろう」
と最初は思ったんですが、よくよく考えてみると少々厄介でした。
pat1 = aa
pat2 = baaab
pat3 = aaac
文字列の中から上記pat1, pat2, pat3を検索する場合、入力が
「baaab」の場合 => 0文字目でpat2にヒット
「baaac」の場合 => 1文字目でpat3にヒット
「baaad」の場合 => 1文字目でpat1にヒット
こんな風に動作して欲しいんですが、ただただDFAを作るだけではこれが実現出来ません。
ヒットするものの候補が複数ある場合、
A) より手前でヒットしたものが優先
B)同じ時点でヒットしたものがあれば長い物を優先
という規則で動作して欲しいので、これを考慮してDFAを構築することにしました。
規則Aは、NFAにおいて「初期状態から何回で遷移可能か」という情報から、
「何文字手前からヒットし始めたか」という情報が得られるので、
これを使ってDFAの遷移から不要なものを消すことによって達成出来ました。
規則Bは、規則Aさえ満たしていれば、「最後に到達した受理状態」を覚えておき、
遷移できなくなれば、それを使うという風にすればすぐに出来ました。
そんなこんなでエントリー冒頭の結論に辿り着きました。
なんであんなにメモリを食うのか、現状ではまったく分かりません。
マクロの展開形を載せておくので、原因が分かった人はこっそり教えてください(笑)
CL-USER> (macroexpand-1
'(dfa-multi-search (str)
"''" 'bold
"'''" 'italic
"%%" 'torikeshi
"((" 'footnote))
(LET ((#:STR131488 STR))
(LET (#:LAST-POS131490 #:LAST-STATE131491)
(BLOCK #:BLOCK131484
(LABELS
((#:TRANS131486 (#:STATE131487 #:CHAR131483 #:POS131489)
(CASE #:STATE131487
((T)
(CASE #:CHAR131483 (#\( '#:G131507) (#\% '#:G131506) (#\' '#:G131505)
(OTHERWISE T)))
((#:G131507)
(CASE #:CHAR131483 (#\( '#:G131508) (#\% '#:G131506) (#\' '#:G131505)
(OTHERWISE T)))
((#:G131508) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131502)
(CASE #:CHAR131483 (OTHERWISE (RETURN-FROM #:BLOCK131484 T))))
((#:G131506)
(CASE #:CHAR131483 (#\% '#:G131509) (#\( '#:G131507) (#\' '#:G131505)
(OTHERWISE T)))
((#:G131509) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131499)
(CASE #:CHAR131483 (OTHERWISE (RETURN-FROM #:BLOCK131484 T))))
((#:G131505)
(CASE #:CHAR131483 (#\' '#:G131510) (#\( '#:G131507) (#\% '#:G131506)
(OTHERWISE T)))
((#:G131510) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131492)
(CASE #:CHAR131483 (#\' '#:G131511)
(OTHERWISE (RETURN-FROM #:BLOCK131484 T))))
((#:G131511) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131495)
(CASE #:CHAR131483 (OTHERWISE (RETURN-FROM #:BLOCK131484 T)))))))
(DO
((#:STATE131487 T) (#:POS131489 0 (1+ #:POS131489))
(#:LEN131485 (LENGTH #:STR131488)))
((>= #:POS131489 #:LEN131485)
(#:TRANS131486 #:STATE131487 #\Null #:POS131489) NIL)
(SETF #:STATE131487
(#:TRANS131486 #:STATE131487 (AREF #:STR131488 #:POS131489)
#:POS131489)))))
(CASE #:LAST-STATE131491 ((#:G131502) (LET NIL 'FOOTNOTE))
((#:G131499) (LET NIL 'TORIKESHI)) ((#:G131492) (LET NIL 'BOLD))
((#:G131495) (LET NIL 'ITALIC)))))
T