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

連想配列を使って普通に木を作る方法で。

標準ライブラリ(std.regexp)では後方参照なしのグルーピングがサポートされないので、普通の括弧にしました。

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

import std.stdio, std.string, std.utf;

class Trie {
    private struct Node {
        Node*[dchar] nodes;
        bool matchTail;
        
        const string toString() {
            if(!nodes.length) return "";
            string[] patterns;
            foreach(c, node; this.nodes) {
                patterns ~= quotemeta(toUTF8([c])) ~ node.toString();
            }
            string pattern = patterns.join("|");
            if(nodes.length == 1) {
                return matchTail ? "(" ~ pattern ~ ")?" : pattern;
            } else {
                return "(" ~ pattern ~ ")" ~ (matchTail ? "?" : "");
            }
        }
    }
    
    private Node tree;
    
    this() { }
    
    this(const(string)[] words) {
        foreach(word; words) {
            this.addWord(word);
        }
    }
    
    void addWord(string word) {
        auto node = &this.tree;
        foreach(dchar c; word) {
            if(auto p = c in node.nodes) {
                node = *p;
            } else {
                node = node.nodes[c] = new Node;
            }
        }
        node.matchTail = true;
    }
    
    const string toString() {
        return tree.toString();
    }
}

private string quotemeta(string str) {
    string result;
    foreach(c; str) {
        switch(c) {
            case '.': case '*': case '+': case '?':
            case '^': case '$': case '{': case '}':
            case '[': case ']': case '(': case ')':
            case '|':
                result ~= ['\\', c];
                break;
            default:
                result ~= c;
        }
    }
    return result;
}

void main(){
    auto words = `program
programist
programistic
programma
programmar
programmatic
programmatically
programmatist
programmer`.splitlines();
    writeln(new Trie(words));
}

DouKaku?

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

Posted feedbacks - D

Index

Feed

Other

Link

Pathtraq