Design and implementation of backward tree pattern matching algorithm modifications

V této práci je navrhnutý nový algoritmus pro vyhledávání ve stromech. Jeho fungování je založeno na myšlence heuristiky good-suffix-shift algoritmu Boyer-Moore pro vyhledávání v řetězcích a poznatcích z existujícího adaptovaného algoritmu Morris-Pratt pro stromy. Algoritmus najde všechny výskyty vyhledávaného vzoru stromu v daném prohledávaném stromě, k tomu využívá dvě pomocné datové struktury. Při běhu algoritmu jsou vstupní stromy převedeny do linearizované podoby, konkrétně do postfixové, rankové notace. Implementovaný algoritmus je na závěr testován s nejlepšími existujícími algoritmy pro vyhledávání ve stromech a výsledky měření ukazují, že se řadí mezi nejrychlejší z nich.In this thesis is designed a new tree pattern matching algorithm. Its idea is based on a concept of good-suffix-shift heuristic of Boyer-Moore string searching algorithm and findings of an existing adaptation of Morris-Pratt algorithm for trees. The algorithm finds all occurences of a sought tree pattern in a given sought through tree using two auxiliary data structures. During the algorithm's run input trees are transformed into a linearised form, specifically postfix, ranked notation. Finally the implemented algorithm is tested with the best existing tree pattern matching algorithms and measurements outcomes show that it ranks among the fastest of them