dc.contributorFerres, Leo; supervisor de grado
dc.creatorElejalde Sierra, Erick
dc.date.accessioned2021-07-06T17:11:36Z
dc.date.available2021-07-06T17:11:36Z
dc.date.created2021-07-06T17:11:36Z
dc.date.issued2014
dc.identifierhttp://repositorio.udec.cl/jspui/handle/11594/6718
dc.description.abstractPrevious 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.
dc.languageeng
dc.publisherUniversidad de Concepción.
dc.publisherDepartamento de Ingeniería Informática y Ciencias de la Computación
dc.publisherDepartamento de Ingeniería Informática y Ciencias de la Computación.
dc.rightshttps://creativecommons.org/licenses/by-nc-nd/4.0/deed.es
dc.rightsCreative Commoms CC BY NC ND 4.0 internacional (Atribución-NoComercial-SinDerivadas 4.0 Internacional)
dc.sourcehttps://go.openathens.net/redirector/udec.cl?url=http://tesisencap.udec.cl/concepcion/elejalde_s_e/index.html
dc.subjectAlgoritmos
dc.subjectProcesamiento de Datos
dc.subjectAlgoritmos Computacionales
dc.subjectAnálisis
dc.subjectÁlgebra
dc.subjectAnálisis Matemático
dc.subjectAlgoritmos
dc.subjectEstructura
dc.titleUn algoritmo de descomposición de tareas para el reconocimiento de patrones de texto = A task decomposition algorithm for string matching.
dc.typeTesis


Este ítem pertenece a la siguiente institución