F#. Net Regex vs. DFA Table.

Um den im letzten Beitrag erstellten DFA sinnvoll einsetzen zu können, sollten wir die Liste von Transitions in einer Tabelle (2D Array) umwandeln. Dann können wir zu jedem Symbol des Alphabets und dem aktuellen Zustand den nächsten Zustand ermitteln, wobei das Symbol als Array-Index verwendet wird.

let nextState = table.[int 'a'].[currentState]

//Program.fs
open System
open System.Text.RegularExpressions
open System.Text
open Graph
open RegExParsing
open RegExCompiling
open RegExProcessor
open ConvertNfaToDfaTable
open Microsoft.FSharp.Collections 

type DfaTableContext = { table : int[][];
                         accept : Set<Node>; //DFA accept states
                         start : Node;
                         numberofState : int;
                         fstLetter : int
                         }

let inline tabulate f size = Array.init size (fun i-> f i)

let inline createDFATable (context : ConvertContext)  =
    let fstLetter = int (List.head context.alphabet)
    let fillArr arr key transitions  = 
        Seq.fold (fun (acc : int[][]) (Transition (fromNode, toNode, _)) -> 
                 match Set.contains fromNode context.accept with
                 | false -> 
                     acc.[int key - fstLetter].[fromNode] <- toNode
                     acc
                 | true -> 
                     acc.[int key - fstLetter].[fromNode] <- fromNode
                     acc) arr transitions
    let tbl = 
        let initTable = 
            tabulate (fun _ -> Array.create context.nextNode context.start)
                (List.length context.alphabet)
        
        Seq.groupBy (fun (Transition (_, _, (Simple c))) -> c) context.trans
        |> ;Seq.fold (fun (acc : int[][]) (key, transitions) ->
                fillArr acc key transitions
                ) initTable

    {table = tbl; accept = context.accept; start = context.start;
     numberofState = context.nextNode; fstLetter = fstLetter}

Letztendlich geht es um die Anwendung vom regulären Ausdruck in dem Fall von der String-Verkettung. Die .Net Regex muss nach jede Verkettung die gesamte neu entstandene Zeichenfolge komplett durchgehen. Im Gegensatz dazu können die resultierende Zustand-Arrays in dem Fall vom DFA ganz einfach zusammengesetzt werden.

Jetzt können wir die Match-Funktion schreiben.

let inline foldUntil dfa (input:string) length = 
      let rec inner acc pos  =
          match pos = length with
          | true -> acc, false
          | _ ->
              let idx = int (input.Chars pos)
              //compose state arrays.
              let res = Array.map (fun node-> dfa.table.[idx - dfa.fstLetter].[node]) acc
              //checking if initial state 0 maps the to the one accepted final state
              match Set.contains res.[0] dfa.accept with
              | true -> res, true
              | false -> inner res (pos+1) 
      inner    
  
let inline matchInput dfa input =   
      foldUntil dfa input input.Length (tabulate id dfa.numberofState) 0 

//Simulate a stream.
let inline streamInput size =
      let str = String.Concat( Array.create size " Match Me " )
      seq{
          yield str+"("
          yield! seq{for i in 1..20 -> str}
          yield str+"007"
          yield str+"bb"
          yield str+")"
          }

let inline test f =
    printfn "Test Start"
    let sw = new System.Diagnostics.Stopwatch()
    sw.Start()
    f()
    sw.Stop()
    printfn "Time Duration : %A" sw.ElapsedMilliseconds

let inline testRegexWithStream nfa regex size letters =
    let dfaContext = convert letters nfa |> createDFATable
    let regex = new Regex (regex)
    let builder = StringBuilder()

    printfn "Array Size %A" size
    let matchStream stream=  
        Seq.fold (fun (acc : int []) x-> 
            let tbl, isMatch = matchInput dfaContext x
            if isMatch then
                printfn "match: true, %A" tbl
                tbl
            else
                let res = Array.map (fun node -> tbl.[node]) acc
                printfn "match: %A, table: %A" (Set.contains res.[0] dfaContext.accept) res
                res) (tabulate id dfaContext.numberofState) stream
    test (fun ()-> 
        printfn "Stream with DFA Table." 
        (streamInput  size |> matchStream ) |> ignore)
    
    let matchStreamRegex stream = 
        stream |> Seq.iter (fun (item: string) ->
            try
                let input = builder.Append(item).ToString() 
                printfn "Input Size: %A; match: %A" builder.Length (regex.Match(input).Success)
            with
                | :? System.ArgumentOutOfRangeException -> printfn "input to big for StringBuilder!"
                | :? System.OutOfMemoryException ->  printfn "input to big for StringBuilder!") 

let run () = 
    let regex = "aa|bb"
    let letters =[' '..'z']
    let nfa = 
        regex |> RegExParsing.parseRegExp |> RegExCompiling.compile FullMatch
        
    testRegexWithStream nfa regex 2000 letters
    testRegexWithStream nfa regex 700000 letters

run()

Array Size 2000
Test Start
Stream with DFA Table.
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
match: true, [|4; 4; 4; 3; 4|]
match: true, table: [|4; 4; 4; 3; 4|]
Time Duration : 127L
Test Start
Stream with .Net Regex
Input Size: 20001; match: false
Input Size: 40001; match: false
Input Size: 60001; match: false
Input Size: 80001; match: false
Input Size: 100001; match: false
Input Size: 120001; match: false
Input Size: 140001; match: false
Input Size: 160001; match: false
Input Size: 180001; match: false
Input Size: 200001; match: false
Input Size: 220001; match: false
Input Size: 240001; match: false
Input Size: 260001; match: false
Input Size: 280001; match: false
Input Size: 300001; match: false
Input Size: 320001; match: false
Input Size: 340001; match: false
Input Size: 360001; match: false
Input Size: 380001; match: false
Input Size: 400001; match: false
Input Size: 420001; match: false
Input Size: 440004; match: false
Input Size: 460006; match: true
Input Size: 480007; match: true
Time Duration : 395L

Array Size 700000
Test Start
Stream with DFA Table.
match: false, table: [|0; 0; 0; 3; 4|]
match: false, table: [|0; 0; 0; 3; 4|]
...
match: false, table: [|0; 0; 0; 3; 4|]
match: true, [|4; 4; 4; 3; 4|]
match: true, table: [|4; 4; 4; 3; 4|]
Time Duration : 21480L
Test Start
Stream with .Net Regex
Input Size: 7000001; match: false
Input Size: 14000001; match: false
...
Input Size: 154000004; match: false
input to big for StringBuilder!
input to big for StringBuilder!
Time Duration : 106610L

Aber wie schneidet die DFA-Tabelle gegen .Net Regex bei großen Texten. Da ist .Net Regex viel schneller. Zum Glück können wir das Matching parallelisieren.

let inline matchParallel dfaContext (s : seq<int * string>) =
    PSeq.map (fun (i, s) -> i, matchInput dfaContext s) s
    |> Seq.sortBy (fun (i, _) -> i)
    |> Seq.reduce (fun (accIdx, accPair) (idx, resultPair)->
         match (snd accPair),(snd resultPair) with
         | true, _  -> accIdx, accPair
         | _, true  -> idx, resultPair
         | other    ->
             let res = Array.map (fun node -> (fst resultPair).[node]) (fst accPair)
             idx, (res, Set.contains res.[0] dfaContext.accept)) 

let inline testRegex nfa regex size letters  =
    let dfaContext = convert letters nfa |> createDFATable
    let regex = new Regex (regex)
    
    let builder = StringBuilder()
    streamInput size |> Seq.iter (fun (item: string) ->
                builder.Append(item).ToString()|>ignore)
    let input = builder.ToString()
    builder.Clear() |>ignore
    let offs = input.Length / Environment.ProcessorCount

    printfn "Regex - %A;Input Length %A" regex input.Length
    let splitSeq = Seq.map (fun i ->
        i, if i + 1 < Environment.ProcessorCount then 
               input.Substring(i * offs, offs) 
           else 
               input.Substring(i * offs)) [0..Environment.ProcessorCount - 1]   
    test (fun () -> printfn "DFA Table Parallel: match - %A" (matchParallel dfaContext splitSeq) )
    test (fun () -> printfn "DFA Table :  match - %A" (matchInput dfaContext input))
    test (fun () -> printfn ".NET Regex : match - %A" (regex.Match(input).Success))

let run () = 
    let regexList = ["aa|bb";".*\(.*007.*\).*"]
    let letters =[' '..'z']

    regexList |> List.iter (fun regex ->
        let nfa = 
            regex |> RegExParsing.parseRegExp |> RegExCompiling.compile FullMatch
        testRegex nfa regex 200 letters 
        testRegex nfa regex 20000 letters
        testRegex nfa regex 200000 letters)
    Console.ReadLine()|>ignore 

Regex - aa|bb;  Input Length 48007
DFA Table Parallel: match - ([|4; 3; 4; 3; 4|], true)
Time Duration : 48L
++++++++++++++++++++++++++++++++++++
DFA Table :  match - ([|4; 4; 4; 3; 4|], true)
Time Duration : 7L
++++++++++++++++++++++++++++++++++++
.NET Regex : match - true
Time Duration : 4L


Regex - aa|bb;  Input Length 4800007

DFA Table Parallel: match - ([|4; 3; 4; 3; 4|], true)
Time Duration : 111L
++++++++++++++++++++++++++++++++++++
DFA Table :  match - ([|4; 4; 4; 3; 4|], true)
Time Duration : 283L
++++++++++++++++++++++++++++++++++++
.NET Regex : match - true
Time Duration : 256L

Regex - aa|bb;  Input Length 48000007

DFA Table Parallel: match - ([|4; 3; 4; 3; 4|], true)
Time Duration : 1052L
++++++++++++++++++++++++++++++++++++
DFA Table :  match - ([|4; 4; 4; 3; 4|], true)
Time Duration : 2814L
++++++++++++++++++++++++++++++++++++
.NET Regex : match - true
Time Duration : 2555L
-----------------------------------------------
Regex - .*\(.*007.*\).*;  Input Length 48007

DFA Table Parallel: match - ([|8; 8; 8; 8; 8; 8; 8; 8; 8; 8; 10; 11; 8; 13|], true)
Time Duration : 7L
++++++++++++++++++++++++++++++++++++
DFA Table :  match - ([|8; 8; 8; 8; 8; 8; 8; 8; 8; 8; 10; 11; 8; 13|], true)
Time Duration : 8L
++++++++++++++++++++++++++++++++++++
.NET Regex : match - true
Time Duration : 3L

Regex - .*\(.*007.*\).*;  Input Length 4800007

DFA Table Parallel: match - ([|8; 8; 8; 8; 8; 8; 8; 8; 8; 8; 10; 11; 8; 13|], true)
Time Duration : 278L
++++++++++++++++++++++++++++++++++++
DFA Table :  match - ([|8; 8; 8; 8; 8; 8; 8; 8; 8; 8; 10; 11; 8; 13|], true)
Time Duration : 564L
++++++++++++++++++++++++++++++++++++
.NET Regex : match - true
Time Duration : 258L

Regex - .*\(.*007.*\).*;  Input
Post veröffentlichen Length 48000007

DFA Table Parallel: match - ([|8; 8; 8; 8; 8; 8; 8; 8; 8; 8; 10; 11; 8; 13|], true)
Time Duration : 2050L
++++++++++++++++++++++++++++++++++++
DFA Table :  match - ([|8; 8; 8; 8; 8; 8; 8; 8; 8; 8; 10; 11; 8; 13|], true)
Time Duration : 5443L
++++++++++++++++++++++++++++++++++++
.NET Regex : match - true
Time Duration : 2618L
-----------------------------------------------

Das gesamte Visual Studio Project kann man hier herunterladen.

F# Subset Construction Algorithm. Converting NFA to DFA.

In Zusammenhang mit dem alten Regex-Posting habe ich überlegt, wenn einen regulären Ausdruck zu einer DFA Übergangstabelle konvertiert werden kann, dann können wir einen solchen Ausdruck auf eine unendliche Eingabefolge anzuwenden ohne überhaupt die Gesamt- oder Teilfolge zu speichern. Wir brauchen nur die aktuelle Werte von der Übergangstabelle zu wissen um festzustellen, ob ein Regex die gesamte Eingabe "matcht".

Dazu muss erst ein Regex in einen DFA umgewandelt werden. Der Algorithmus ist hier in Details beschrieben und es gibt bereits eine F#-Implementierung zur Kompilierung eines regulären Ausdrucks in einen nicht-deterministischen endlichen Automaten (NFA). Was fehlt, ist der Übergang zum DFA und darum geht es hier.

Subset Construction Algorithm (aka Powerset Construction)


Ich hoffe ich verletze keine Copyright-Bestimmungen, wenn ich oben genannte Implementierung nutze ( hier kann man das Projekt herunterladen). 

Wie bei mir schon üblich ist, diente der Haskell-Code als Vorbild.

// Required RegExProcessor from  
// http://stevehorsfield.wordpress.com/2009/08/05/download-the-regular-expression-processor/
open RegExCompiling
open RegExParsing.RegExProcessor

  type Node = int
  //Transition: fromNode * toNode * Label 
  type Transition = Transition of Node * Node * NdfaEdge
  type ConvertContext = { nfa : RegExCompiling.NdfaGraph;
                          trans :  Transition list;   //DFA Transition list.
                          //mapping NFA sets of nodes  to a single node in the DFA.
                          setMap : Map<Set<Node>, int>;
                          setStack : Set<Node> list;
                          finalNfa : Set<Node>;  // set of NFA final states
                          accept : Set<Node>;   //  DFA accept states
                          nextNode : Node;
                          start : Node
                          alphabet : char list}
  // Search the table of transitions to find all nodes you can reach given an initial set of nodes.
  // Auto - epsilon transition.
  let inline findToNodes startNode trans value fromNodes = 
      let matchNodes  (from, _to, edge) nodes =
          match from with 
          | from' when (from' = fromNodes) ->
              match edge, value with
              | AnyChar, Simple _ -> Set.add _to nodes
              | Auto,    Auto     -> Set.add _to nodes
              | CharacterTest criteria, Simple c when (testCharacter criteria c)     -> 
                  Set.add _to nodes  
              | CharacterTest criteria, Simple c when not (testCharacter criteria c) -> 
                  Set.add startNode nodes 
              | Simple v, Simple c when  v = c  -> Set.add _to nodes 
              | Simple v, Simple c when  v <> c -> Set.add startNode nodes 
              | other -> nodes
          | other -> nodes
      List.foldBack matchNodes trans Set.empty  
  
  // Check if we already added this transition if not add it
  let inline checkTransition ts context = 
    match List.exists (fun x -> x = ts) context.trans with
    | true  -> context
    | false -> {context with trans = ts :: context.trans }

  // Check if a given node set contains a accept state
  // if so add it to the dfa accept states
  let inline updateAcceptStates nfaAccepts dfaAccepts nSet nSetIndex = 
    match Set.intersect nSet nfaAccepts |> Set.isEmpty with
    | true  -> dfaAccepts
    | false -> Set.add nSetIndex dfaAccepts
          
  let inline addNodeSet nSet context = 
    let newNodesStack   = context.setStack @ [nSet]
    let newNode         = context.nextNode
    let newNodesMap     = Map.add nSet newNode context.setMap
    let newAccepts      = updateAcceptStates context.finalNfa context.accept nSet newNode
    
    newNode, {context with setMap = newNodesMap; 
                           nextNode = newNode + 1; 
                           setStack = newNodesStack; 
                           accept = newAccepts}

  // Checks a NodeSet to see if it has a node number value
  // If it doesnt we assign it one and add it to the nodeSet stack
  let inline checkNodeSet nSet context = 
    match Map.containsKey nSet context.setMap with
    | true  -> context.setMap.[nSet], context
    | false -> addNodeSet nSet context   
  
  // Given a node and a set of nodes, union orginal set with the set of nodes you can 
  // traverse to from node on the value
  let inline closure startNode trans value oldSet nodes = 
      Set.union (findToNodes startNode trans value nodes) oldSet
  
  // Given an initial set of nodes, find the set of all nodes you can reach by taking 
  // transitions on epsilon only
  let inline epsilonClosure start trans = 
      let generator = Set.fold (closure start trans Auto) Set.empty
      Set.unionMany 
      << Seq.unfold (fun state -> 
              match Set.isEmpty state with
              | true  -> None
              | false -> Some(state, generator state)) 
  //Move takes a set of nodes and input character and returns all nodes you can reach by taking transitions on given input character. 
  let inline moveClosure start trans character =
      epsilonClosure start trans << Set.fold (closure start trans character) Set.empty
  

  let inline buildTransition oldTrans context value= 
      let nodes = List.head context.setStack
      let newSet = moveClosure context.start oldTrans value nodes
      match Set.isEmpty newSet with
      | false ->
          let fromNode, c1 = checkNodeSet nodes context
          let toNode, c2 = checkNodeSet newSet c1
          checkTransition (Transition (fromNode, toNode, value)) c2
      | true -> context
        
  let inline runConversion machine nodes finalNfa letters =
      let context = { nfa = machine;
                      trans = [];
                      setMap = Map.empty;
                      setStack = [];
                      finalNfa = finalNfa;
                      accept = Set.empty;
                      nextNode = 0;
                      start = 0;
                      alphabet = letters}
      let popSetStack context   = {context with setStack = List.tail context.setStack}
      let trans                 = Graph.toTable context.nfa
      let edges                 = context.alphabet |> List.map Simple
      let startSet              = epsilonClosure context.start trans nodes

      checkNodeSet startSet context
      |> snd
      |> Seq.unfold (fun ctx -> 
          match List.isEmpty ctx.setStack with
          | true  -> None
          | false -> 
              let newCtx = List.fold (buildTransition trans) ctx edges |> popSetStack
              Some(newCtx, newCtx))
      |> Seq.tryFind (fun ctx -> List.isEmpty ctx.setStack)
  
  let inline convert letters nfa =
    let fstLetter = List.head letters
    let final = 
      getClosureMap nfa
      |>Array.mapi (fun node isFinal -> 
          match isFinal with
          | true  -> Some(node)
          | false -> None)
      |>Array.choose id 
      |>Set.ofArray 

    let initialStates = 
      getStartStates nfa

    let startNodes = (List.map (fun (i,_,_,_,_) -> i) initialStates)
    
    let context = 
        match runConversion nfa (startNodes |> Set.ofList) final letters with
        | Some v -> v
        | None   -> failwith "Conversion is not possible."
    context 

open RegExParsing
> let test () =
    let regex = "aa|bb"
    let letters =['a'..'c']
    let context = 
        "aa|bb" |> RegExParsing.parseRegExp |> RegExCompiling.compile FullMatch
        |> convert letters 
    printfn "Context: %A" context;;

> test();;
Context: {nfa =
    ((7, 6),
    [((6, (Closure, null)), []); ((5, (Normal, null)), [(4, 1, 4, Simple 'b')]);
     ((4, (Normal, null)), [(5, 0, 6, Simple 'b')]); ((3, (Closure, null)), []);
     ((2, (Normal, null)), [(1, 0, 1, Simple 'a')]);
     ((1, (Normal, null)), [(2, 0, 3, Simple 'a')]);
     ((0, (Start, null)), [(3, 1, 5, Auto); (0, 0, 2, Auto)])]);
trans =
    [Transition (4,0,Simple 'c'); Transition (4,4,Simple 'b');
     Transition (4,1,Simple 'a'); Transition (3,0,Simple 'c');
     Transition (3,2,Simple 'b'); Transition (3,3,Simple 'a');
     Transition (2,0,Simple 'c'); Transition (2,4,Simple 'b');
     Transition (2,1,Simple 'a'); Transition (1,0,Simple 'c');
     Transition (1,2,Simple 'b'); Transition (1,3,Simple 'a');
     Transition (0,0,Simple 'c'); Transition (0,2,Simple 'b');
     Transition (0,1,Simple 'a')];
setMap =
  map
    [(set [0; 1; 2; 3; 5], 3); (set [0; 1; 2; 5], 1); (set [0; 2; 4; 5], 2);
     (set [0; 2; 4; 5; 6], 4); (set [0; 2; 5], 0)];
setStack = [];
finalNfa = set [3; 6];
accept = set [3; 4];
nextNode = 5;
start = 0;
alphabet = ['a'; 'b'; 'c'];}
val it : unit = ()

Fortsetzung folgt.