Please use this identifier to cite or link to this item:
http://repositorio.udec.cl/jspui/handle/11594/6862
Title: | Búsqueda exacta en secuencias de caracteres UTF-8: algoritmos paralelos versus algoritmos secuenciales palelizados mediante descomposición de dominio |
Authors: | Ferres, Leo; supervisor de grado Reyes Cabrera, Rodrigo Antonio |
Keywords: | Algoritmos Computacionales |
Issue Date: | 2012 |
Publisher: | Universidad de Concepción. |
Abstract: | This work focuses on comparing the efficiency of exact string matching algorithms in UTF-8 encoded strings. Specially, we will compare the effciency of sequential algorithms which have been later parallelized using domain decomposition techniques against the efficiency of originally parallelized algorithms. To this end, we will use the UTF-8 international string encoding standard which provides a big enough encoding space for all present known languages. We prove that sequential algorithms with non original parallelization are more efficient than originally parallelized algorithms. For this purpose, we implement the Naive, Knuth-Morris-Pratt, Boyer-Moore and Bitap algorithms, both in their sequential and domain decomposition based parallelized versions. Then we compare them with the originally parallelized algorithm from Vishkin. As our final result, we found out that parallelized sequential algorithms are more efficient than originally parallelized algorithms. |
Description: | Tesis para optar al grado de Magíster en Ciencias de la Computación. |
URI: | http://repositorio.udec.cl/jspui/handle/11594/6862 |
metadata.dc.source.uri: | https://go.openathens.net/redirector/udec.cl?url=http://tesisencap.udec.cl/concepcion/reyes_c_r/index.html |
Appears in Collections: | Ingeniería Informática y Ciencias de la Computación - Tesis Magister |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Resumen.pdf | 159,19 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License