TP1: búsqueda exacta en cadenas
El objetivo del trabajo práctico es el de implementar algoritmos de búsqueda exacta en cadenas, extraer conclusiones sobre sus aplicaciones y presentarlas frente a la clase.
Consigna
Los grupos estarán compuestos de hasta cuatro personas. Deberán implementar el algoritmo ingenuo, y por persona un algoritmo de los siguientes:
- Colussi1 (una variación de KMP)
- Apostólico-Giancarlo2 ó bien Zhu-Takaoka3 (variaciones de Boyer-Moore)
- Karp-Rabin4
- Ukkonen5
- DC36
Alternativamente, los grupos pueden escoger profundizar una investigación relacionada con temas de matching en cadenas y prescindir de implementar los algoritmos.
Los días viernes 13/10 y viernes 20/10, los alumnos deberán presentar el trabajo realizado frente a la clase, explicando:
- la lógica de funcionamiento de los algoritmos elegidos
- los casos de prueba en donde el algoritmo fue evaluado
- un rápido repaso del código escrito
- cualquier tipo de investigación adicional que haya sido realizada
- una breve demostración del algoritmo funcionando
- una serie de conclusiones relacionadas a las pruebas hechas con diferentes juegos de datos,
por ejemplo:
- ¿Qué algoritmo usar si sólo quiero buscar P en T? ¿y si quiero buscar n patrones en T?
- ¿Qué algoritmo usar si con un alfabeto muy chico? ¿y con uno muy grande?
- ¿Qué algoritmo usar de acuerdo al tamaño de T?
Además, deberán intregar impreso un informe que detalle brevemente los puntos de la presentación.
El trabajo será evaluado de acuerdo a los siguientes ítems:
- algoritmos implementados y evaluados
- profundidad de la investigación adicional
- calidad y diversidad de los sets de datos utilizados
- calidad de la presentación
- calidad del informe escrito
Se adjunta aquí un set de datos de ejemplo para realizar pruebas.
Referencias
- 1: L. Colussi. 1991. Correctness and Efficiency of Pattern Matching Algorithms.
- 2: A. Apostolico, R. Giancarlo. 1986. The Boyer-Moore-Galil string searching strategies revisited.
- 3: R. F. Zhu, T. Takaoka. 1987. On improving the average case of the Boyer-Moore string matching algorithm”
- 4: R. Karp, M. Rabin. 1987. Efficient randomized pattern-matching algorithms.
- 5: E. Ukkonen. 1995. On-line construction of suffix trees.
- 6: J. Kärkkäinen, P. Sanders, S. Burkhardt. 2003. Linear Work Suffix Array Construction.
La bibliografía de la materia contiene descripciones y explicaciones de varios algoritmos, y secciones dedicadas a aplicaciones adicionales:
- D. Gusfield. 1997. Algorithms on Strings, Trees and Sequences.
También hay material sobre los algoritmos clásicos en otros libros de referencia:
- T. Cormen, C. Leiserson, R. Rivest, C. Stein. 2009. Introduction to Algorithms (3ra edición). Cap. 32.
- R. Sedgewick, K. Wayne. 2011. Algorithms (4ta edición).
Para investigar sobre variaciones a los algoritmos clásicos pueden consultar las siguientes publicaciones:
- R. Kothari, N. Mishra, S. Sharma, R. Patel. 2015. A Survey and Analysis on String Matching Techniques and its Applications.
- K. Al-Khamaiseh, S. Al-Shagarin. 2014. A Survey of String Matching Algorithms.
- C. Charras, T. Lecroq. 2004. Handbook of Exact String-Matching Algorithms.