文字列リストをTRIE Optimizeされた正規表現に in Scheme 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 - Scheme

共通部分文字列を切り出しながら Trie を作っています。もう少しスマートにできないものかしらん。

出力:

(?:program(?:ist(?:ic)?|m(?:a(?:r|ti(?:c(?:ally)?|st))?|er))?)

(use srfi-1)
(use srfi-13)
(use gauche.collection)

(define (make-trie strs)
  (define (string-ref* s n)
    (or (string-null? s) (string-ref s n)))
  (define (make-node xs)
    (if (null? (cdr xs))
        xs
        (let ((b (apply min
                        (pair-fold
                         (lambda (ys knil)
                           (if (null? (cdr ys))
                               knil
                               (cons (string-prefix-length (car ys) (cadr ys))
                                     knil)))
                         '() xs))))
          (cons (string-take (car xs) b)
                (make-trie* (map (cut string-drop <> b) xs))))))
  (define (make-trie* ss)
    (map make-node (group-collection ss :key (cut string-ref* <> 0))))
  (cons "" (make-trie* strs)))

(define (trie->regexp-str tree)
  (define (null-node? node)
    (and (pair? node)
         (string-null? (car node))
         (null? (cdr node))))
  (if (null? (cdr tree))
      (car tree)
      (format "~A(?:~A)~A"
              (car tree)
              (string-join (map trie->regexp-str
                                (remove null-node? (cdr tree))) "|")
              (if (any null-node? (cdr tree)) "?" ""))))

(print (trie->regexp-str
        (make-trie '("program"
                     "programist"
                     "programistic"
                     "programma"
                     "programmar"
                     "programmatic"
                     "programmatically"
                     "programmatist"
                     "programmer"))))

DouKaku?

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

Posted feedbacks - Scheme

Index

Feed

Other

Link

Pathtraq