Jewels of Stringology: Text Algorithms es un libro sobre algoritmos para la comparación de patrones en cadenas y problemas relacionados. Fue escrito por Maxime Crochemore y Wojciech Rytter y publicado por World Scientific en 2003.
Los primeros temas del libro son dos algoritmos básicos de búsqueda de cadenas para encontrar subcadenas que coincidan exactamente , el algoritmo Knuth–Morris–Pratt y el algoritmo de búsqueda de cadenas 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 en espacio constante y la compresión sin pérdida de cadenas. La coincidencia aproximada de cadenas se cubre en varias variaciones, incluida la distancia de edición y el problema de la subsecuencia común más larga . El libro concluye con temas avanzados que incluyen la coincidencia de patrones bidimensionales, algoritmos paralelos para la coincidencia de patrones, el problema de la supercuerda común más corta , la coincidencia de patrones parametrizada y la detección de código duplicado , y el algoritmo Rabin–Karp . [1]
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 crítico 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 de los mismos autores Text Algorithms (1994). [2]
La revisora Shoshana Marcus escribe que los algoritmos elegidos para su inclusión en el libro son "elegantes pero fundamentales", pero que a menudo han sido pasados por alto por libros de texto de algoritmos más generales. Escribe que el libro en sí mismo 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 técnicas de programación paralela a nivel de bits refleja su sesgo hacia métodos teóricos en lugar de prácticos, pero no obstante está de acuerdo con su idoneidad para cursos de posgrado. [3]
{{citation}}: CS1 maint: publicación periódica sin título ( enlace ){{citation}}: CS1 maint: publicación periódica sin título ( enlace )