Data structures for efficient string algorithms [Elektronische Ressource] / vorgelegt von Johannes Fischer

Data Structures for EfficientString AlgorithmsJohannes FischerMu¨nchen 2007Data Structures for EfficientString AlgorithmsJohannes FischerDissertationan der Fakult¨at fu¨r Mathematik, Informatik und Statistikder Ludwig–Maximilians–Universita¨tMu¨nchenvorgelegt vonJohannes Fischeraus Kronberg i. Ts.Mu¨nchen, den 10. Oktober 2007Erstgutachter: Prof. Dr. Volker HeunZweitgutachter: Prof. Dr. Enno OhlebuschTag der mu¨ndlichen Pru¨fung: 8. Oktober 2007AbstractThis thesis deals with data structures that are mostly useful in the area ofstring matching and string mining. Our main result is an O(n)-time prepro-cessing scheme for an array of n numbers such that subsequent queries askingfor the position of a minimum element in a specified interval can be answeredin constant time (so-called RMQs for Range Minimum Queries). The spacefor this data structure is 2n+o(n) bits, which is shown to be asymptoticallyoptimal inageneral setting. Thisimproves allpreviousresultsonthisproblem.The main techniques for deriving this result rely on combinatorial propertiesof arrays and so-called Cartesian Trees. For compressible input arrays we showthat further space can be saved, while not affecting the time bounds. For thetwo-dimensional variant of the RMQ-problem we give a preprocessing schemewith quasi-optimal time bounds, but with an asymptotic increase in space con-sumption of a factor of logn.