Mere podobnosti nizov

diplomsko delo

Mojca Lorber (Avtor), Jurij Mihelič (Mentor)

Povzetek

Diplomska naloga Mere podobnosti nizov proučuje problem primerjanja nizov, kjer nas zanimajo ujemanja, ki dovoljujejo tudi napake. Takšnemu problemu pravimo tudi problem približnega ujemanja nizov in njegov bistveni del je definicija modela napak ter s tem izbira mere podobnosti oz. različnosti. V nalogi na začetku izvedemo splošen pregled mer, potem pa se v nadaljevanju osredotočimo na skupino mer, ki temelji na operacijah urejanja nizov. Definicija razdalje med nizoma je tako določena s stroškom operacij, ki prvi niz najbolj optimalno preuredi v drugega. V tem sklopu nato opišemo nekaj algoritmov na osnovi metode dinamičnega programiranja ter dodamo še par njihovih nadgradenj. S pomočjo primera nazorno prikažemo njihovo izvajanje ter z analizo predstavimo tudi njihove računske zahtevnosti.

Ključne besede

podobnost;različnost;mera podobnosti;primerjanje nizov;poravnava nizov;razdalja urejanja;najdaljše skupno podzaporedje;računalništvo;računalništvo in informatika;računalništvo in matematika;univerzitetni študij;diplomske naloge;interdisciplinarni študij;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2016
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[M. Lorber]
UDK:	004.42:519.1(043.2)
COBISS:	1536792259
Št. ogledov:	1939
Št. prenosov:	577
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	String similarity measures
Sekundarni povzetek:	The thesis String similarity measures examines string matching problem, where we are interested in matchings allowing errors. Such problem is also called approximate string matching problem, and its essential part is the definition of error model and by this the type of a similarity or dissimilarity measure. In the beginning of the thesis we present a general overview of measures, then we further focus on the group of measures based on the edit operations on strings. The definition of such distance between strings is established with the cost of operations that are needed for an optimal transformation from one string to another. Further on, we describe a few algorithms based on dynamic programming, and then we add a couple of upgraded versions. With a help of an example we try to demonstrate their performance and analyse their computational complexity.
Sekundarne ključne besede:	similarity;dissimilarity;similarity measure;string matching;string alignment;edit distance;longest common subsequence;computer science;computer and information science;computer science and mathematics;diploma;interdisciplinary studies;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	XIX, 91 str.
ID:	9126703