Sufiksno stablo

undergraduate thesis

• Title (english): Suffix tree
• Author: Tomislav Šebrek
• Mentor: Mile Šikić (mentor)
• Committee member: Mile Šikić (predsjednik povjerenstva)
• Committee member: Krešimir Križanović (član povjerenstva)
• Committee member: Andrej Novak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2015-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Sufiksno stablo je struktura podataka koja omogućuje razne manipulacije nad znakovnim nizom u linearnom vremenu ovisnom samo o duljini podniza nad kojima se ostvaruje upit, a moguće ga je izgraditi u linearnom vremenu. U ovom radu opisana je izgradnja stabla Ukkonenovim algoritmom koji se temelji na izgradnji implicitnih sufiksnih stabala za svaki prefiks znakovnog niza kroz implicitna i eksplicitna proširenja, a svoju linearnost postiže kroz eliminaciju implicitnih proširenja, uvođena strukture aktivne pozicije te sufiksnim vezama.
U ovom radu opisana je implementacija Ukkonenovog algoritma za izgradnju poopćenog sufiksnog stabla, što je zapravo generalizacija algoritma za skup znakovnih nizova. Kao primjena poopćenog stabla, prikazan je implementacija pronalaska svih sufiks-prefiks preklapanja između znakovnih nizova nad kojima je stablo izgrađeno. Rezultati testiranja složenosti programskog rješenja nad znakovnim nizovima različitih duljina podudaraju se s teorijskom analizom složenosti.

Abstract (english)

Suffix tree is a data structure that allows various string operations to be executed in linear time dependent only on the length of the substring for which the operation is executed, and its construction is possible in linear time. Ukkonen's algorithm for suffix tree construction is based on construction of implicit suffix trees for each string prefix through implicit and explicit extensions. Linearity of Ukkonen's algorithm is achieved through elimination of implicit extension check, active position structure and suffix links.
In this thesis implementation of Ukkonen's algorithm for construction of generalised suffix tree, which in fact is generalisation of algorithm over set of strings, is shown. As an example of suffix tree, implementation of finding all suffix-prefix matches between strings over which the tree was built is demonstrated. Complexity calculated by running several tests over different sized strings matches the complexity obtained by theoretical analysis of the algorithm.

• Keywords: eksplicitno proširenje; implicitno proširenje; implicitno sufiksno stablo; poopćeno sufiksno stablo; sufiks-prefiks preklapanje; sufiksna veza; sufiksno stablo; Ukkonenov algoritam
• Keywords (english): explicit extension; implicit extension; implicit suffix tree; generalised suffix tree; suffix-prefix match; suffix link; suffix tree; Ukkonen's algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:444680
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 12:13:57