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

Squeak Smalltalk で。

SiroKuro さんの #4105 を参考にさせて頂きました。最後、たたみ込みながら正規表現を生成するところはたいへん小気味よいですね。

| assemble |
assemble := [:words |
    | prefixSizes |
    words := words sort.
    prefixSizes := words overlappingPairsCollect: [:aa :bb |
        | shorterSize found |
        shorterSize := aa size min: bb size.
        found := (1 to: shorterSize) findFirst: [:idx | (aa at: idx) ~= (bb at: idx)].
        found isZero ifTrue: [shorterSize] ifFalse: [found - 1]].
    prefixSizes asSet asArray sort reverseDo: [:idx |
        | found |
        [(found := prefixSizes lastIndexOf: idx) > 0] whileTrue: [
            words at: found put: ('{1}(?:{2}|{3})' format: {
                (words at: found) first: idx.
                (words at: found) allButFirst: idx.
                (words at: found + 1) allButFirst: idx}).
            words := words copyWithoutIndex: found + 1.
            prefixSizes := prefixSizes copyWithoutIndex: found]].
    '^', words first, '$'].

assemble value: #(
    program
    programist
    programistic
    programma
    programmar
    programmatic
    programmatically
    programmatist
    programmer)

"=> '^program(?:|(?:ist(?:|ic)|m(?:a(?:|(?:r|ti(?:c(?:|ally)|st)))|er)))$' "

DouKaku?

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

Posted feedbacks - Smalltalk

Index

Feed

Other

Link

Pathtraq