#:g1: cl-string-matchの紹介

Posted 2014-04-13 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の104日目です。

cl-string-matchとはなにか

 cl-string-matchは、Victor Anyakin氏作の文字列探索のライブラリです。

パッケージ情報

パッケージ名cl-string-match
Quicklisp
プロジェクトサイトcl-string-match | Free Development software downloads at SourceForge.net
CLiKihttp://cliki.net/cl-string-match
Quickdocshttp://quickdocs.org/cl-string-match

インストール方法

(ql:quickload :cl-string-match)

試してみる

 どんな関数があるかは、Quickdocsで確認できます。

 現在のところ

がサポートされているようです。

(defvar *text* (*:read-file-to-string "/usr/share/dict/words"))

(search "lithographing" *text*) ;=> 548599

(sm:string-contains-ac "lithographing" *text*) ;=> 548599

(sm:string-contains-bm "lithographing" *text*) ;=> 548599

(sm:string-contains-rk "lithographing" *text*) ;=> NIL

(sm:string-contains-bmh "lithographing" *text*) ;=> NIL

(sm:string-contains-kmp "lithographing" *text*) ;=> 548599

(sm:string-contains-brute "lithographing" *text*) ;=> 548599

(let ((idx (sm:initialize-rk "list"))) (sm:search-rk idx *text*)) ;=> NIL

(let ((idx (sm:initialize-ac "list"))) (sm:search-ac idx *text*)) ;=> 3365 ; 0

(let ((idx (sm:initialize-bm "list"))) (sm:search-bm idx *text*)) ;=> 3365

(let ((idx (sm:initialize-bmh "list"))) (sm:search-bmh idx *text*)) ;=> 21736

(let ((idx (sm:initialize-kmp "list"))) (sm:search-kmp idx *text*)) ;=> 3365

bmhとrkの結果がどういうことなのかについては置いておいて、速度等はどうなのかCL:SEARCHとでも比較してみます〈bmhとrkは除外〉

(defmacro ss-bench (pat text &optional (times 100))
  `(progn 
     ,@(mapcar (lambda (x)
                 (let ((xpr `(time 
                              (dotimes (i ,times)
                                (,x ,pat ,text)))))
                   `(progn
                      (pprint ',xpr)
                      ,xpr)))
               '(search 
                 sm:string-contains-ac
                 sm:string-contains-bm
                 ;; sm:string-contains-rk
                 ;; sm:string-contains-bmh
                 sm:string-contains-kmp
                 sm:string-contains-brute))))
(ss-bench "lithographing" *text*)
;>> (TIME (DOTIMES (I 100) (SEARCH "lithographing" *TEXT*)))
;>> Evaluation took:
;>>   1.546 seconds of real time
;>>   1.544096 seconds of total run time (1.544096 user, 0.000000 system)
;>>   99.87% CPU
;>>   3,700,604,277 processor cycles
;>>   0 bytes consed
;>>   
;>> 
;>> (TIME (DOTIMES (I 100) (SM:STRING-CONTAINS-AC "lithographing" *TEXT*)))
;>> Evaluation took:
;>>   4.300 seconds of real time
;>>   4.272267 seconds of total run time (4.272267 user, 0.000000 system)
;>>   99.35% CPU
;>>   10,293,248,214 processor cycles
;>>   1,694,576 bytes consed
;>>   
;>> 
;>> (TIME (DOTIMES (I 100) (SM:STRING-CONTAINS-BM "lithographing" *TEXT*)))
;>> Evaluation took:
;>>   0.303 seconds of real time
;>>   0.304019 seconds of total run time (0.304019 user, 0.000000 system)
;>>   100.33% CPU
;>>   725,790,519 processor cycles
;>>   221,072 bytes consed
;>>   
;>> 
;>> (TIME (DOTIMES (I 100) (SM:STRING-CONTAINS-KMP "lithographing" *TEXT*)))
;>> Evaluation took:
;>>   0.467 seconds of real time
;>>   0.468029 seconds of total run time (0.468029 user, 0.000000 system)
;>>   100.21% CPU
;>>   1,118,114,415 processor cycles
;>>   32,704 bytes consed
;>>   
;>> 
;>> (TIME (DOTIMES (I 100) (SM:STRING-CONTAINS-BRUTE "lithographing" *TEXT*)))
;>> Evaluation took:
;>>   0.389 seconds of real time
;>>   0.388024 seconds of total run time (0.388024 user, 0.000000 system)
;>>   99.74% CPU
;>>   929,401,578 processor cycles
;>>   38,784 bytes consed

bm(ボイヤー-ムーア法)あたりは5倍程度速いようです。

まとめ

 今回は、cl-string-matchを紹介してみました。
プロジェクトページもドキュメントも綺麗にまとまっているので今後の発展に期待したいプロジェクトです。

comments powered by Disqus