Det viktigaste resultatet av tidningen är byggandet av en mycket snabb multi-mönster matchande algoritm, som kallas DAWG-MATCH. Algoritmen är av Boyer-Moore-typ. Tidigare algoritm av denna typ är Commentz-Walter algoritm. DAWG-MATCH algoritmen beter sig bättre än Commentz-Walter algoritm. Vi kombinerar idéerna om två algoritmer: Aho-Corasick-algoritmen och Reverse Factor-algoritmen från Crochemore et alii. Den nya algoritmen utför högst 2jtextj inspektioner av texttecken, och är mycket snabb i genomsnitt. Vi ger några experimentella bevis på dess goda beteende för slumpmässiga ord, mot Commentz-Walter algoritmen. Algoritmen är särskilt enkel för ett enda mönster: i detta fall Aho-Corasick algoritm kan ersättas av strategin för Knuth-Morris-Pratt algoritm. Det grundläggande verktyget i algoritmen DAWG-MATCH är den riktade acykliska ordkurvan. Denna graf används vanligtvis som representation av texten som skannas, men i vårt fall använder vi den för att representera uppsättningen av omvända mönster.
Den multi-mönster utvärdering som presenteras i REF bygger på två deterministiska automata, en byggd på prefixet för uppsättningen av mönster och den andra på de omvända mönster.
Fast Practical Multi-Pattern Matching
{'venue': 'Inf. Process. Lett.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}