In this chapter, we presented a novel approach to generate adaptive matching automata for non-sequential pattern set using genetic programming. we first defined some notation and necessary terminologies. Then, we formulated the problem of pattern matching and the impact that the traversal order of the patterns has on the process efficiency, when the patterns are ambiguous. We also gave some heuristics that allow the engineering of a relatively good traversal order. In the main part of the chapter, we described the evolutionary approach that permits the discovery of traversal orders using genetic programming for a given pattern set. For this purpose, we presented how the encoding of traversal orders is done and consequently how the decoding of an evolved traversal order into the corresponding adaptive pattern-matcher. We also developed the necessary genetic operators and showed how the fitness of evolved traversal orders is computed. We evaluated how sound is the obtained traversal. The optimisation was based on three main characteristics for matching automata, which are termination, code size and required matching time. Finally, we compared evolutionary adaptive matching automata, obtained for some universal benchmarks, to their counterparts that were designed using classic heuristics.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
- Evolutionary Pattern Matching Using Genetic Programming
Luiza de Macedo Mourelle
- Springer Berlin Heidelberg
in-adhesives, MKVS, Zühlke/© Zühlke