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.*\).*; InputLength 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 -----------------------------------------------Post veröffentlichen
Das gesamte Visual Studio Project kann man hier herunterladen.
Keine Kommentare:
Kommentar veröffentlichen