Mayor subsecuencia común
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 7 de julio de 2022; las comprobaciones requieren 15 ediciones .La tarea de encontrar la subsecuencia común más larga ( eng. subsecuencia común más larga , LCS) es la tarea de encontrar una secuencia que es una subsecuencia de varias secuencias (generalmente dos). A menudo, el problema se define como encontrar todas las subsecuencias más grandes. Este es un problema clásico de informática , que tiene aplicaciones, en particular, en el problema de comparación de archivos de texto (la utilidad diff ), así como en bioinformática .
Se puede obtener una subsecuencia de alguna secuencia finita si se elimina algún conjunto de sus elementos (posiblemente vacío) de esta última. Por ejemplo, BCDB es una subsecuencia de la secuencia ABCDBAB. Decimos que una secuencia Z es una subsecuencia común de las secuencias X e Y si Z es una subsecuencia tanto de X como de Y. Se requiere que dos secuencias X e Y encuentren una subsecuencia común de la mayor longitud. Tenga en cuenta que puede haber varios NOP.
¡Nota! Una subsecuencia es diferente de una subcadena . Por ejemplo, si hay una secuencia fuente "ABCDEF", entonces "ACE" será una subsecuencia pero no una subcadena, y "ABC" será tanto una subsecuencia como una subcadena.
Solución del problema
Comparemos dos métodos de solución: búsqueda de fuerza bruta y programación dinámica .
Enumeración completa
Existen diferentes enfoques para resolver este problema con una enumeración completa: puede ordenar las opciones de subsecuencia, las opciones de eliminación de estas secuencias, etc. Sin embargo, en cualquier caso, el tiempo de ejecución del programa será un polinomio en la longitud de las cadenas.
Método de programación dinámica
| A | B | C | D | ||
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| D | 0 | ← 0 | ← 0 | ← 0 | ↖ 1 |
| C | 0 | ← 0 | ← 0 | ↖ 1 | ← 1 |
| D | 0 | ← 0 | ← 0 | ↑ 1 | ↖ 2 |
| A | 0 | ↖ 1 | ← 1 | ← 1 | ↑ 2 |
Primero, encuentre la longitud de la subsecuencia más grande. Supongamos que estamos buscando una solución para el caso (n 1 , n 2 ), donde n 1 , n 2 son las longitudes de la primera y segunda cadena. Deje que ya existan soluciones para todos los subproblemas (m 1 , m 2 ) más pequeños que el dado. Luego, la tarea (n 1 , n 2 ) se reduce a subtareas más pequeñas de la siguiente manera:
![{\displaystyle f(n_{1},n_{2})=\left\{{\begin{array}{ll}0,&n_{1}=0\lor n_{2}=0\\f(n_ {1}-1,n_{2}-1)+1,&s_{1}[n_{1}]=s_{2}[n_{2}]\\max(f(n_{1}-1, n_{2}),f(n_{1},n_{2}-1)),&s_{1}[n_{1}]\neq s_{2}[n_{2}]\end{matriz}} \Correcto.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/247fee8787b87a38bc364638e91965c11181338a)
Ahora volvamos al problema de construir una subsecuencia. Para ello, añadimos al algoritmo existente una memoria para cada tarea de la subtarea a través de la cual se resuelve. La siguiente acción, partiendo del último elemento, subimos al principio siguiendo las direcciones dadas por el primer algoritmo, y escribimos los caracteres en cada posición. Esta será la respuesta para este problema.
El tiempo de ejecución del algoritmo será .
Véase también
- Algoritmos en cadenas
- Mayor subcadena común
Enlaces
- Hallar la mayor subsecuencia común . algolist.ru. Consultado: 15 de agosto de 2013.
- Algoritmo para encontrar la longitud de la subsecuencia común más grande . codificadores.ask-ru.net.
| Instrumentos de cuerda | |
|---|---|
| Medidas de similitud de cadenas | |
| Búsqueda de subcadena | |
| palíndromos | |
| Alineación de secuencia | |
| Estructuras de sufijos | |
| Otro | |