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

だいたい同じことを OCaml で。
パターンマッチのおかげで多少は読みやすくなったかも。
リストの破壊的操作ができないので Map を使ってみました。

open Printf

type trie = Node of bool * (char * trie) list

module M = Map.Make(struct type t = char let compare = Char.compare end)

let rec classify b map = function
  | [] -> b, map
  | ""::rest -> classify true map rest
  | str::rest ->
      let c, s = str.[0], String.sub str 1 (String.length str - 1) in
      let newmap =
        M.add c (s::try M.find c map with Not_found -> []) map in
        classify b newmap rest

let rec make_trie strings =
  let b, map = classify false M.empty strings in
    Node(b, M.fold (fun c strs al -> (c, (make_trie strs))::al) map [])

let rec make_regexp = function
  | Node(false, [c, trie]) -> sprintf "%c%s" c (make_regexp trie)
  | Node(b, (_::_ as alist)) ->
      let res =
        List.map (fun (c, t) -> sprintf "%c%s" c (make_regexp t)) alist in
      let re = String.concat "|" res in
        sprintf "(?:%s)%s" re (if b then "?" else "")
  | _ -> ""

let trie_optimize strings = make_regexp (make_trie strings)

DouKaku?

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

Posted feedbacks - OCaml

Index

Feed

Other

Link

Pathtraq