Un algoritmo de descomposición de tareas para el reconocimiento de patrones de texto = A task decomposition algorithm for string matching.
| dc.contributor.advisor | Ferres, Leo | es |
| dc.contributor.author | Elejalde Sierra, Erick | es |
| dc.date.accessioned | 2021-07-06T17:11:36Z | |
| dc.date.accessioned | 2024-08-28T20:05:38Z | |
| dc.date.available | 2021-07-06T17:11:36Z | |
| dc.date.available | 2024-08-28T20:05:38Z | |
| dc.date.issued | 2014 | |
| dc.description | Tesis presentada para optar al grado de Magíster en Ciencias de la Computación. | es |
| dc.description.abstract | Previous attempts to parallelize string matching algorithms have focused on data decomposition; that is, splitting the text on the number of available cores. In this work, we demonstrate that it is possible to use task decomposition efficiently, using a multiprocessor model. We introduce the Task Decomposition String Matching algorithm, a new algorithm based on bit parallelism and finite automata theory. We also present a producer/consumer strategy which may be applied to the traditional algorithms as an alternative way to parallelize them. We run experiments that compare both our approaches against traditional algorithms (such as Boyer-Moore, KMP and Bitap) by varying the length of the pattern and the properties of alphabets, two critical variables that affect performance in string matching. The Domain Decomposition strategy proved to be very efficient for this problem. Although task decomposition is asymptotically optimal, it is practically affected by cache contingencies. | en |
| dc.description.campus | Concepción | es |
| dc.description.departamento | Departamento de Ingeniería Informática y Ciencias de la Computación | es |
| dc.description.facultad | Facultad de Ingeniería | es |
| dc.identifier.uri | https://repositorio.udec.cl/handle/11594/6718 | |
| dc.language.iso | es | es |
| dc.publisher | Universidad de Concepción | es |
| dc.rights | CC BY-NC-ND 4.0 DEED Attribution-NonCommercial-NoDerivs 4.0 International | en |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| dc.source.uri | https://go.openathens.net/redirector/udec.cl?url=http://tesisencap.udec.cl/concepcion/elejalde_s_e/index.html | |
| dc.subject | Algoritmos | es |
| dc.subject | Procesamiento de Datos | es |
| dc.subject | Algoritmos Computacionales | es |
| dc.subject | Análisis | es |
| dc.subject | Álgebra | es |
| dc.subject | Análisis Matemático | es |
| dc.subject | Algoritmos | es |
| dc.subject | Estructura | es |
| dc.title | Un algoritmo de descomposición de tareas para el reconocimiento de patrones de texto = A task decomposition algorithm for string matching. | es |
| dc.type | Tesis | es |