Búscalo aquí:

El problema de String Matching Completo



El problema de string matching completo consiste em encontrar todas las ocurrencias de um determinado patrón p en um texto t. Este es uno de los problemas más estudiados en Ciencia de la Computación principalmente por tener aplicación directa en diversas áreas como procesamiento de texto, imágenes y señales, análisis y reconocimiento de habla, compresión de datos, recuperación de datos, entre otros. Desde 1970 se han propuesto más de 80 algoritmos de string matching, y de ellos, más del 50% son de la última década. En un trabajo de investigación se han implementado 85 diferentes algoritmos de string matching y se han realizado distintas pruebas sobre su desenvolvimiento.



Desde el algoritmo de fuerza bruta propuesta en el libro "Introduction to Algorithms" de T.H. Cormen, pasando por algoritmos conocidos como Morris-Pratt, Boyer Moore, Horspool de la década de 1970-1980, hasta algoritmos de string matching más recientes como Fast-Search, Boyer Moore - Horspool using Probabilities, Two sliding window o Genomic Rapid Algo for String Pm de los años 2003-2009 han sido implementados en lenguaje C y testeados de manera rigida en el trabajo "The Exact String Matching Problem: a Comprehensive Experimental Evaluation" de Simone Faro y Thierry Lecroq (Diciembre 2010).

En la siguiente imagen se puede observar el número de algoritmos propuestos de string matching de los últimos 21 años (1990-2010) de acuerdo a su tipo: basados en comparación, basados en autómatas, por paralelismo de bits.



Los experimentos fueron realizados sobre textos que contienen información de secuencia de genomas del Eschericia coli, secuencia de proteínas del genoma del saccharomyces cerevisiae, la Biblia (versión en inglés de King James) y el CIA World Fact Book.

La imagen superior muestra un mapa de los mejores resultados obtenidos por los algoritmos de string matching evaluados.

Las imágenes han sido tomadas del paper citado, al cual pueden acceder libremente: [ver paper en PDF].

Saludos

Quieres leer más post como éste???...suscribete aquí!!!

No hay comentarios.:

Publicar un comentario

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...