Názov:The Distances on Words
Vedúci:Prof. Branislav Rovan, PhD.
Kµúčové slová:edit distance, longest common subsequence, delta similarity,
Abstrakt:Lot of research was done on the string similarity, due to many practical applications (similarities of DNA/RNA structures, etc). In the first part of this work, we shall introduce an abstract model of the distance of words, from which the known distances such as edit-distance (Levenshtein distance) can be derived. We shall present some other instances of this model. We shall discuss what derivations can/cannot be effectively computed. In the second part of this work we shall extend the notion of the distance on words to the distance of a word and a language. We present algorithm for computing $\Delta$-similarity of a word and a context-free language.

Súbory diplomovej práce: