文字列リストをTRIE Optimizeされた正規表現に in Common Lisp DouKaku?

文字列リストをTRIE Optimizeされた正規表現に

これは、実例を見た方が簡単だと思います。 CPANにRegexp::Assembleというモジュールがあるのですが、要はこれの簡易版を作って欲しいということです。私自身、同様のことを行うモジュールを過去にいくつか作っています(e.g Regexp::Optimizer)。

ここでは、文字列のリストを受け取って、それをTRIE化した正規表現に出来ればOKです。Regexp::AssembleやRegexp::Optimizerは正規表現を受け取ってそれをTrie化することも可能ですし、Perl 5.10では内部的にTrie Optimizationを行ったりするのですが、そこまでの機能は求めません。

なお、ここで言う「正規表現」は、必ずしもPerl互換のものである必要はありません。それがTrieになっていることをきちんと示せればOKです。

とはいうものの、Perl5互換になっていた方が、サポートしている環境が多くて有用性は高そうです。可能であればそうして下さい。

Dan the Regexp Assembler

see: Trie (en.wikipedia)

#!/usr/local/bin/perl
use strict;
use warnings;
use Regexp::Assemble;

my $ra = Regexp::Assemble->new;
while(<>){
    chomp;
    next unless $_;
    $ra->add($_);
}
print $ra->re, "\n"
__END__

% grep program /usr/share/dict/words 
program
programist
programistic
programma
programmar
programmatic
programmatically
programmatist
programmer

% grep program /usr/share/dict/words | perl sample.pl 
(?-xism:program(?:m(?:a(?:ti(?:c(?:ally)?|st)|r)?|er)|ist(?:ic)?)?)

post comment

Posted feedbacks - Common Lisp

ごちゃごちゃになってしまいました。
(空文字列の有無 (先頭 残り)...) で trie っぽいものを作ってますが、
データ構造が適当すぎたかも。

(defun classify (strings)
  (let ((a ()) (empty nil))
    (dolist (s strings (cons empty a))
      (if (string= s "")
          (setf empty t)
        (let* ((fst (elt s 0)) (rest (subseq s 1))
               (x (assoc fst a)))
          (if x (push rest (cdr x))
            (push `(,fst . (,rest)) a)))))))

;; TRIE ::= (data (char . TRIE)*)
(defun make-trie (strings)
  (let ((x (classify strings)))
    (cons (car x)
          (mapcar (lambda (a) (cons (car a) (make-trie (cdr a))))
                  (cdr x)))))

(defun make-regexp (trie)
  (cond ((and (null (car trie)) (null (cddr trie)))
         ;; (nil (c . subtrie)) => common prefix がある
         (format nil "~C~A" (caadr trie) (make-regexp (cdadr trie))))
        ((cdr trie)
         ;; (d (c . subtrie) ...) => common prefix なし
         (format nil "(?:~{~{~C~A~}~^|~})~@[?~]"
                 (mapcar (lambda (a) (list (car a) (make-regexp (cdr a))))
                         (cdr trie))
                 (car trie)))
        (t
         ;; 空文字列しかない
         "")))

(defun trie-optimize (strings) (make-regexp (make-trie strings)))

DouKaku?

文字列リストをTRIE Optimizeされた正規表現に

Posted feedbacks - Common Lisp

Index

Feed

Other

Link

Pathtraq