Tengo una gran secuencia ordenada de símbolos, millones de símbolos. Tengo que encontrar subsecuencias ordenadas repetidas tales que:
- Las subsecuencias de búsqueda son desconocidas, tengo que encontrar subsecuencias que se repitan en otras partes de grandes secuencias.
- Las subsecuencias pueden tener diferencias, como la presencia de cierta cantidad de ruido y la ausencia de algunos símbolos.
Condición no necesaria:
- Las subsecuencias pueden tener poca cantidad de permutaciones de los símbolos vecinos.
El alfabeto consta de miles de símbolos.
¿Puede recomendar un algoritmo bien conocido y bien estudiado para tal tarea?
Respuestas
0 para la respuesta № 1Puedes probar aho-corasick multiple patternhacer coincidir y usar un comodín para buscar subcadenas. Para la subsecuencia desea también la distancia levenstein. Puede probar mi implementación en PHP del algoritmo aho-corasick con comodín en https://phpahocorasick.codeplex.com.