Jewels of Stringology: Text Algorithms es un libro sobre algoritmos para la coincidencia de patrones en cadenas y problemas relacionados. Fue escrito por Maxime Crochemore y Wojciech Rytter , y publicado por World Scientific en 2003.
Temas
Los primeros temas del libro son dos algoritmos básicos de búsqueda de cadenas para encontrar subcadenas que coincidan exactamente , el algoritmo de Knuth-Morris-Pratt y el algoritmo de búsqueda de cadenas de Boyer-Moore . Luego describe el árbol de sufijos , un índice para buscar rápidamente subcadenas coincidentes y dos algoritmos para construirlo. Otros temas del libro incluyen la construcción de autómatas finitos deterministas para el reconocimiento de patrones, el descubrimiento de patrones repetidos en cadenas, algoritmos de coincidencia de cadenas de espacio constante y la compresión sin pérdidas de cadenas. La coincidencia aproximada de cadenas se cubre en varias variaciones, incluida la distancia de edición y el problema de subsecuencia común más largo . El libro concluye con temas avanzados que incluyen la coincidencia de patrones bidimensionales, algoritmos paralelos para la coincidencia de patrones, el problema de supercuerdas común más corto , coincidencia de patrones parametrizados y detección de código duplicado , y el algoritmo Rabin-Karp . [1]
Audiencia y recepción
El libro está escrito para un público familiarizado con el diseño y análisis de algoritmos, pero no necesariamente familiarizado con los algoritmos de cadenas. [1] El revisor Rolf Klein sugiere que este público objetivo puede ser limitado, ya que evalúa el libro como demasiado difícil para muchos estudiantes, pero no proporciona tanta profundidad para los expertos como el libro anterior Text Algorithms (1994) de los mismos autores . [2]
El crítico Shoshana Marcus escribe que los algoritmos elegidos para su inclusión en el libro son "elegantes pero fundamentales", pero a menudo se han pasado por alto en los libros de texto sobre algoritmos más generales. Ella escribe que el libro en sí debería convertirse en una referencia valiosa para los investigadores en esta área, y que también podría usarse para complementar el material de cursos de pregrado o posgrado en algoritmos. [1] El revisor Ricardo Baeza-Yates sugiere que la omisión del libro de las técnicas de programación paralela a nivel de bits refleja su sesgo hacia métodos teóricos más que prácticos, pero sin embargo está de acuerdo con su idoneidad para cursos de posgrado. [3]
Referencias
- ^ a b c Marcus, Shoshana (septiembre de 2015), "Review of Jewels of Stringology " (PDF) , ACM SIGACT News , 46 (3): 11-14, doi : 10.1145 / 2818936.2818940 , S2CID 29751366
- ^ Klein, Rolf, zbMATH , Zbl 1078.68151CS1 maint: publicación periódica sin título ( enlace )
- ^ Baeza-Yates, Ricardo (2005), Revisiones Matemáticas , MR 2012571CS1 maint: publicación periódica sin título ( enlace )