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

Text.RegexモジュールではデフォルトではPOSIXの正規表現をつかっている．
ここではそれにしたがった正規表現文字列を生成する．
メタ文字のエスケープもしたつもり．

実行結果
*Main> putStrLn $ oregex (unfoldTree phi sample) ""
program(ist(ic)?|m(a(r|ti(c(ally)?|st))?|er))?

import Data.List
import Data.Tree

type Trie = Tree (Bool,String)

eqapp f x y = f x == f y

lcp :: [String] -> (String, [String])
lcp [] = ("",[])
lcp xxs@(x:xs) 
 = if null x 
      then ("",xxs)
      else if all (isPrefixOf [head x]) xs 
              then case lcp (map tail xxs) of
                     (ps,yys) -> (head x:ps,yys)
              else ("",xxs)


phi :: [String] -> ((Bool,String), [[String]])
phi [x] = ((False,x), [])
phi xxs  = case lcp xxs of
 (ps,"":ys) -> ((True,ps), groupBy (eqapp head) ys)
 (ps,yys)   -> ((False,ps),groupBy (eqapp head) yys)

oregex :: Trie -> ShowS
oregex (Node (p,s) [])
 | p         = showString (escape s) . showString "?"
 | otherwise = showString (escape s)
oregex (Node (p,s) cs)
 | p         = (showString (escape s) .) $ (. showString "?") $ paren $ foldr (.) id (intersperse (showString "|") (map oregex cs))
 | otherwise = (showString (escape s) .) $ paren $ foldr (.) id (intersperse (showString "|") (map oregex cs))

paren :: ShowS -> ShowS
paren s = showString "(" . s . showString ")"

metaChars = "\\|[](){}.*+?^$"
escapeMeta c | elem c metaChars = '\\':[c]
             | otherwise        = [c]

escape = concatMap escapeMeta

sample = sort ["program"
              ,"programist"
              ,"programistic"
              ,"programma"
              ,"programmar"
              ,"programmatic"
              ,"programmatically"
              ,"programmatist"
              ,"programmer"
              ]

DouKaku?

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

Posted feedbacks - Haskell

Index

Feed

Other

Link

Pathtraq