String Matching Aproximado Mejorado con SIMD

Mostrar todas las versiones(2)

Consideramos la versión de k sustituciones de string matching aproximado (o búsqueda aproximada de cadenas) para uno solo y múltiples patrones. El problema básicamente consiste en encontrar todas las ocurrencias de uno o más patrones con a lo sumo k sustituciones de caracteres en un texto. Dada...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Fiori, Fernando Jesus
Otros Autores: Tarhio, Jorma
Formato: bachelorThesis Tésis de Grado acceptedVersion
Lenguaje:Español
Publicado: 2020
Materias:
algoritmos
strings
SIMD
distancia Hamming
string matching aproximado
Acceso en línea:http://hdl.handle.net/2133/19090
http://hdl.handle.net/2133/19090
Aporte de:
Repositorio Hipermedial de la Universidad Nacional de Rosario (UNR) de Universidad Nacional de Rosario
Descripción
Sumario:Consideramos la versión de k sustituciones de string matching aproximado (o búsqueda aproximada de cadenas) para uno solo y múltiples patrones. El problema básicamente consiste en encontrar todas las ocurrencias de uno o más patrones con a lo sumo k sustituciones de caracteres en un texto. Dada la gran popularidad de las extensiones de conjuntos de instrucciones SIMD (Single Instruction Multiple Data) en las CPUs actuales, presentamos nuevos algoritmos eficientes para este problema que las aprovechan. Medimos el rendimiento de cada nuevo algoritmo mediante pruebas exhaustivas en diferentes textos de la vida real comparándolo con los algoritmos más competitivos conocidos hasta la fecha. Tomamos un enfoque práctico al tratar de mejorar el tiempo promedio de cada algoritmo.

Ejemplares similares