Mémoires de Fin d’Etudes
Etablissement
Université de Béjaia - Abderrahmane Mira
Affiliation
Département Electronique
Auteur
ABDENOUR, Dermouche
Directeur de thèse
Rob, Irving
Filière
Electronique
Diplôme
Magister
Titre
New algorithms for the numerical approach to text searching
Mots clés
The numerical approach : New algorithms
Résumé
Approximate string matching is a relatively new branch in algorithmics. its application, however, is very wide: it extends from the file difference problem to speech processing. In the first part of this thesis some algorithms for the longest common subsequence (lcs), its dual problem the shortest edit script (ses) and the edit distance problem are reviewed. the aim is a better understanding of the factors involved in the design of algorithms to solve these problems. existing methods are placed within a general framework, and some new techniques are added. particular attention is given to the tunning of parameters associated with costs of opérations. these factors are taken into account when choosing one algorithm over another. a formulation and adaptation of hirshberg’s linear space algorithm to the case of computing tfe edit distance is also undertaken. In the second part, a detailed introduction of the numerical approach to text searching, recently introduced bay baeza-yates and gonnet, is presented in order to give a better understanding of the new algorithms presented in chapter 6. thes algorithms offer a new insight into this new approach: they present the possibility of looking for occurrences of a pattern in a text, with exactly k differences, without having to find intermediate differences. a new problem is identiffied and a solution is proposed. the problem is finding occurrences of the pattern with up to k deletations, k insertions or k subtitions but not a mixture of them. the solution is an exclusive-or generalisation of these new algorithms. the algoritm presented for the exact matching case offer an alternative to the use of shifts.
Date de soutenance
1993
Cote
621.3M/10
Pagination
110 f.
Illusatration
Couv.Ill.
Format
30 cm
Notes
Bibliography
Statut
Soutenue