Return to search

Incremental Matching on Word Chains

Pattern matching, which is the process of finding a given pattern in a given text, is widely used in areas such as search and replace functions in text processing programs or in DNA sequence analysis, where the pattern can be a search term or a specific sequence of characters. Finding and analysing nucleic acid sequences in DNA data can in some cases require sequences to be found which in turn are made up of several specific sub sequences, where the nucleotides between them, as well as the number of them, are irrelevant. This pattern, also called a word chain, can more efficiently be found by pre-processing the pattern and text. This thesis explores, investigates and presents a data structure, used to match a word chain pattern, with the ability to incrementally alter this pre-computed information in order to more efficiently, time wise, handle text alterations such as split and concatenation operations.

Identiferoai:union.ndltd.org:UPSALLA1/oai:DiVA.org:umu-226701
Date January 2024
CreatorsNilsson, Wilmer
PublisherUmeå universitet, Institutionen för datavetenskap
Source SetsDiVA Archive at Upsalla University
LanguageEnglish
Detected LanguageEnglish
TypeStudent thesis, info:eu-repo/semantics/bachelorThesis, text
Formatapplication/pdf
Rightsinfo:eu-repo/semantics/openAccess
RelationUMNAD ; 1481

Page generated in 0.0019 seconds