En informática , la rotación de cadena mínima lexicográficamente o la subcadena lexicográficamente menos circular es el problema de encontrar la rotación de una cadena que posee el orden lexicográfico más bajo de todas esas rotaciones. Por ejemplo, la rotación lexicográficamente mínima de "bbaaccaadd" sería "aaccaaddbb". Es posible que una cadena tenga múltiples rotaciones lexicográficamente mínimas, pero para la mayoría de las aplicaciones esto no importa, ya que las rotaciones deben ser equivalentes. Encontrar la rotación lexicográficamente mínima es útil como una forma de normalizar cadenas. Si las cadenas representan estructuras potencialmente isomórficas como gráficos, normalizar de esta manera permite una verificación de igualdad simple. [1] Un truco de implementación común cuando se trata de cadenas circulares es concatenar la cadena consigo misma en lugar de tener que realizar aritmética modular en los índices de cadena.
Algoritmos
El algoritmo ingenuo
El algoritmo ingenuo para encontrar la rotación lexicográficamente mínima de una cadena es iterar a través de rotaciones sucesivas mientras se hace un seguimiento de la rotación más lexicográficamente mínima encontrada. Si la cadena tiene una longitud n , este algoritmo se ejecuta en tiempo O ( n 2 ) en el peor de los casos.
Algoritmo de Booth
Booth (1980) propuso un algoritmo eficiente. [2] El algoritmo utiliza una función de preprocesamiento modificada del algoritmo de búsqueda de cadenas de Knuth-Morris-Pratt . La función de falla para la cadena se calcula como normal, pero la cadena se rota durante el cálculo, por lo que algunos índices deben calcularse más de una vez a medida que se envuelven. Una vez que todos los índices de la función de falla se han calculado con éxito sin que la cadena vuelva a girar, se sabe que se encuentra la rotación lexicográfica mínima y se devuelve su índice inicial. La exactitud del algoritmo es algo difícil de entender, pero es fácil de implementar.
def least_rotation ( S : str ) -> int : "" "algoritmo de Booth" "" S + = S string # Concatenate a si mismo para evitar la aritmética modular f = [ - 1 ] * len ( S ) # fallo de la función k = 0 # Rotación mínima de la cuerda encontrada hasta ahora para j en el rango ( 1 , len ( S )): sj = S [ j ] i = f [ j - k - 1 ] mientras que i ! = - 1 y sj ! = S [ k + i + 1 ]: si sj < S [ k + i + 1 ]: k = j - i - 1 i = f [ i ] si sj ! = S [ k + i + 1 ]: # si sj! = S [k + i + 1], entonces i == -1 si sj < S [ k ]: # k + i + 1 = k k = j f [ j - k ] = - 1 más : f [ j - k ] = i + 1 devuelve k
Es interesante que la eliminación de todas las líneas de código que modifiquen el valor de k da como resultado la función de preprocesamiento original de Knuth-Morris-Pratt, ya que k (que representa la rotación) seguirá siendo cero. El algoritmo de Booth se ejecuta entiempo, donde n es la longitud de la cadena. El algoritmo funciona como máximocomparaciones en el peor de los casos, y requiere una memoria auxiliar de longitud n para contener la tabla de función de falla.
Algoritmo de canonización rápida de Shiloach
Shiloach (1981) [3] propuso un algoritmo que mejora el resultado de Booth en términos de rendimiento. Se observó que si hay q rotaciones lexicográficamente mínimas equivalentes de una cadena de longitud n , entonces la cadena debe constar de q subcadenas iguales de longitud d = n / q . El algoritmo requiere solo n + d / 2 comparaciones y espacio constante en el peor de los casos.
El algoritmo se divide en dos fases. La primera fase es un tamiz rápido que descarta índices que obviamente no son ubicaciones de inicio para la rotación lexicográficamente mínima. La segunda fase luego encuentra el índice de inicio de rotación lexicográficamente mínimo de los índices que quedan.
Algoritmo de factorización Lyndon de Duval
Duval (1983) [4] propuso un algoritmo eficiente que implica la factorización de la cadena en sus palabras Lyndon componentes , que se ejecuta en tiempo lineal con un requisito de memoria constante.
Variantes
Shiloach (1979) [5] propuso un algoritmo para comparar eficientemente dos cadenas circulares para la igualdad sin un requisito de normalización. Una aplicación adicional que surge del algoritmo es la generación rápida de ciertas estructuras químicas sin repeticiones.
Ver también
Referencias
- ^ Kellogg S. Booth; Colbourn, Charles J. (1980). "Algoritmos de automatismo de tiempo lineal para árboles, gráficos de intervalo y gráficos planos" . Revista SIAM de Computación . Sociedad de Matemáticas Industriales y Aplicadas. 10 (1): 203–225. doi : 10.1137 / 0210015 . ISSN 0097-5397 .
- ^ Kellogg S. Booth (1980). "Subcadenas lexicográficamente menos circulares". Cartas de procesamiento de información . Elsevier. 10 (4–5): 240–242. doi : 10.1016 / 0020-0190 (80) 90149-0 . ISSN 0020-0190 .
- ^ Yossi Shiloach (1981). "Canonización rápida de cadenas circulares". Revista de algoritmos . Elsevier. 2 (2): 107–121. doi : 10.1016 / 0196-6774 (81) 90013-4 . ISSN 0196-6774 .
- ^ Jean Pierre Duval (1983). "Factorizar palabras sobre un alfabeto ordenado". Revista de algoritmos . Elsevier. 8 (8): 363–381. doi : 10.1016 / 0196-6774 (83) 90017-2 . ISSN 0196-6774 .
- ^ Yossi Shiloach (1979). "Un algoritmo de comprobación de equivalencia rápida para listas circulares". Cartas de procesamiento de información . Elsevier. 8 (5): 236–238. doi : 10.1016 / 0020-0190 (79) 90114-5 . ISSN 0020-0190 .