Estoy buscando una implementación (espacial) eficiente de un algoritmo LCS para usar en un programa C++. Las entradas son dos secuencias de números enteros de acceso aleatorio.
Actualmente estoy usando el enfoque de programación dinámica de la página wikipedia sobre LCS. Sin embargo, eso tiene un comportamiento O (mn) en la memoria y el tiempo y muere en mí con errores de memoria para entradas más grandes.
He leído sobre el algoritmo de Hirschberg, que mejora considerablemente el uso de memoria, Hunt-Szymanski y Masek y Paterson. Como no es trivial implementar esto, preferiría probarlos en mis datos con una implementación existente. ¿Alguien sabe de una biblioteca así? Me imagino que dado que las herramientas de diferencia de texto son bastante comunes, debería haber algunas bibliotecas de código abierto.biblioteca de algoritmos de subsecuencia común más larga eficiente?
Respuesta
Cuando busque cosas por el estilo, intente scholar.google.com. Es mucho mejor para encontrar trabajos académicos. Resultó http://www.biotec.icb.ufmg.br/cabi/artigos/seminarios2/subsequence_algorithm.pdf este documento, una "encuesta de algoritmos subsecuencias comunes más largas".
Grudging +1 porque el OP realmente quiere implementaciones de biblioteca de dichos algoritmos, no descripciones. Pero probablemente un papel útil de todos modos. –
También sería útil saber la fecha de publicación y otros detalles. –
No C++ pero Python pero creo que se puede usar.
Hirschberg's Algorithm incrusta una implementación javascript: casi C.
- 1. La subsecuencia más larga común
- 2. Diferencia de datos basada en SQL: subsecuencia común más larga
- 3. La subsecuencia común más larga para múltiples secuencias
- 4. Subsección palindrómica común más larga
- 5. Seleccionar TimeRange común más larga
- 6. Subcadena común más larga de más de dos cadenas - Python
- 7. problema de subcadena común más larga
- 8. Encontrar una subsecuencia en la secuencia más larga
- 9. Explicar el algoritmo para resolver el problema de la 'subsecuencia creciente más larga'
- 10. ¿Cómo encontrar la subcadena común más larga usando árboles?
- 11. Cómo encontrar la subcadena común más larga usando C++
- 12. Biblioteca de colecciones primitivas de Java más eficiente
- 13. Manera eficiente de practicar algoritmos de teoría de grafos
- 14. Encontrar la subcadena común más larga en un gran conjunto de datos
- 15. Extensiones de comunidad SQLCLR o biblioteca común
- 16. . Biblioteca de .NET para algoritmos de texto?
- 17. ¿La forma más eficiente de Python para elegir la cadena más larga en la lista?
- 18. ¿Cómo acelerar el cálculo de la longitud de la subcadena común más larga?
- 19. Arreglo de prefijo común más largo
- 20. subsecuencia más largo que el primero aumenta y luego disminuye
- 21. ¿Obtener una stacktrace más larga de FastMM?
- 22. Buscar la subcadena común más larga de varias cadenas utilizando factor oracle mejorado con matriz LRS
- 23. ¿Cuál es la forma más eficiente de calcular el mínimo común múltiplo de dos enteros?
- 24. La forma más eficiente de generar una cadena realmente larga (decenas de megabytes) en JS
- 25. Ruta simple más larga
- 26. Encuentra más larga secuencia
- 27. ¿La "encuesta larga" es la forma más eficiente de crear una aplicación web en tiempo real?
- 28. Cualquier biblioteca de algoritmos de geometría 3D en Java?
- 29. ¿Hay una descripción general de los algoritmos más comunes?
- 30. ¿Cómo hacer esto más eficiente?
¿Le interesa la subsecuencia común más larga real o simplemente su longitud? – IVlad
Necesito la secuencia real. – BuschnicK
Decepcionado que algunas búsquedas rápidas de la web no encontraron nada especialmente útil (un montón de implementaciones ad hoc para 'char' en C, pero nada con la aceleración del espacio lineal de Hirschberg o con plantillas en el tipo de elemento para C++). Si encuentras (o creas: D) algo, ¡por favor actualiza! –