Cuerda (estructura de datos)

Estructura de datos para almacenar cadenas.

Una simple cuerda construida sobre la cuerda de "Hello_my_name_is_Simon".

En programación informática , una cuerda , o cordón , es una estructura de datos compuesta de cadenas más pequeñas que se utiliza para almacenar y manipular eficientemente una cadena muy larga. Por ejemplo, un programa de edición de texto puede utilizar una cuerda para representar el texto que se está editando, de modo que operaciones como inserción, eliminación y acceso aleatorio se puedan realizar de manera eficiente. ^[1]

Descripción

Una cuerda es un tipo de árbol binario donde cada hoja (nodo final) contiene una cuerda y una longitud (también conocida como "peso"), y cada nodo más arriba en el árbol contiene la suma de las longitudes de todas las hojas en su subárbol izquierdo . Un nodo con dos hijos divide así toda la cadena en dos partes: el subárbol izquierdo almacena la primera parte de la cadena, el subárbol derecho almacena la segunda parte de la cadena y el peso de un nodo es la longitud de la primera parte.

Para las operaciones con cuerdas, se supone que las cadenas almacenadas en los nodos son objetos constantes e inmutables en el caso típico no destructivo, lo que permite cierto comportamiento de copia en escritura . Los nodos hoja generalmente se implementan como cadenas básicas de longitud fija con un recuento de referencia adjunto para desasignación cuando ya no se necesitan, aunque también se pueden usar otros métodos de recolección de basura .

Operaciones

En las siguientes definiciones, N es la longitud de la cuerda, es decir, el peso del nodo raíz.

Recoger hojas

Definición: crear una pila S y una lista L. Recorra la columna más a la izquierda del árbol hasta llegar a una hoja l', agregando cada nodo n a S. Suma l' a L . El padre de l' ( p ) está en la parte superior de la pila. Repita el procedimiento para el subárbol derecho de p.

La clase final InOrderRopeIterator implementa Iterator <RopeLike> {​      pila final privada Deque <RopeLike> ;​​    InOrderRopeIterator ( @NonNull RopeLike root ) { pila = new ArrayDeque <> (); var c = raíz ; mientras ( c ! = nulo ) { pila . empujar ( c ); c = c . obtenerIzquierda (); } }                       @Override public boolean hasNext () { pila de retorno . tamaño () > 0 ; }          @Override public RopeLike next () { val resultado = pila . estallido ();         if ( ! pila . está vacío ()) { var padre = pila . estallido (); var derecha = padre . obtenerDerecha (); if ( correcto ! = nulo ) { pila . empujar ( derecha ); var hendidura = derecha . obtenerIzquierda (); while ( hendido ! = nulo ) { pila . empujar ( hendidura ); hendidura = hendidura . obtenerIzquierda (); } } }                                 resultado de retorno ; } }  

Reequilibrar

Definición: Recoge el conjunto de hojas L y reconstruye el árbol de abajo hacia arriba.

estático booleano isBalanced ( RopeLike r ) { val profundidad = r . profundidad (); if ( profundidad >= FIBONACCI_SEQUENCE . longitud - 2 ) { return false ; } devolver FIBONACCI_SEQUENCE [ profundidad + 2 ] <= r . peso (); }                        reequilibrio estático de RopeLike ( RopeLike r ) { if ( ! isBalanced ( r )) { val leaves = Ropes . recoger hojas ( r ); return merge ( hojas , 0 , hojas . tamaño ()); } devolver r ; }                  fusión estática RopeLike ( Lista < RopeLike > hojas ) { return merge ( hojas , 0 , hojas . tamaño ()); }        fusión estática RopeLike ( List < RopeLike > hojas , int inicio , int fin ) { int rango = fin - inicio ; if ( rango == 1 ) { return hojas . obtener ( comenzar ); } if ( rango == 2 ) { return new RopeLikeTree ( hojas . get ( inicio ), hojas . get ( inicio + 1 )); } int mid = inicio + ( rango / 2 ); devolver nuevo RopeLikeTree ( fusionar ( hojas , inicio , mitad ), fusionar ( hojas , mitad , final )); }                                                  

Insertar

Definición: Insert(i, S’) inserte la cadena S' comenzando en la posición i en la cadena s , para formar una nueva cadena C ₁ , ..., C _i , S' , C _{i + 1} , ..., C _m .

Complejidad del tiempo: ⁠ ⁠ ${\displaystyle O(\log N)}$ .

Esta operación se puede realizar mediante una Split()y dos Concat()operaciones. El costo es la suma de los tres.

inserción de cuerda pública ( int idx , secuencia CharSequence ) { if ( idx == 0 ) { return anteponer ( secuencia ); } if ( idx == longitud ()) { return append ( secuencia ); } val lhs = base . dividir ( idx ); devolver nueva cuerda ( cuerdas . concat ( lhs . fst . append ( secuencia ), lhs . snd )); }                              

Índice

Figura 2.1: Ejemplo de búsqueda de índice en una cuerda.

Definición: Index(i) : devuelve el carácter en la posición i

Complejidad del tiempo: ⁠ ⁠ ${\displaystyle O(\log N)}$

Para recuperar el i -ésimo carácter, comenzamos una búsqueda recursiva desde el nodo raíz:

@Override public int indexOf ( char ch , int startIndex ) { if ( startIndex > peso ) { retorno a la derecha . indexOf ( ch , startIndex - peso ); } regresar a la izquierda . indexOf ( ch , índiceInicio ); }                    

Por ejemplo, para encontrar el carácter en i=10la Figura 2.1 que se muestra a la derecha, comience en el nodo raíz (A), encuentre que 22 es mayor que 10 y hay un hijo izquierdo, así que vaya al hijo izquierdo (B). 9 es menor que 10, así que resta 9 de 10 (dejando i=1) y ve al hijo derecho (D). Luego, como 6 es mayor que 1 y queda un hijo izquierdo, vaya al hijo izquierdo (G). 2 es mayor que 1 y hay un hijo izquierdo, así que ve al hijo izquierdo nuevamente (J). Finalmente, 2 es mayor que 1 pero no queda ningún hijo, por lo que el carácter en el índice 1 de la cadena corta "na" (es decir, "n") es la respuesta. (índice basado en 1)

Concat

Figura 2.2: Concatenación de dos cuerdas secundarias en una sola cuerda.

Definición: Concat(S1, S2) concatenar dos cuerdas, S ₁ y S ₂ , en una sola cuerda.

Complejidad del tiempo: ⁠ ⁠ ${\displaystyle O(1)}$ (o ⁠ ⁠ ${\displaystyle O(\log N)}$ tiempo para calcular el peso de la raíz)

Se puede realizar una concatenación simplemente creando un nuevo nodo raíz con left = S1 y right = S2 , que es un tiempo constante. El peso del nodo padre se establece en la longitud del hijo izquierdo S ₁ , lo que llevaría ⁠ ⁠ tiempo, si el árbol está equilibrado. ${\displaystyle O(\log N)}$

Como la mayoría de las operaciones con cuerdas requieren árboles equilibrados, es posible que sea necesario reequilibrar el árbol después de la concatenación.

Dividir

Figura 2.3: Partiendo una cuerda por la mitad.

Definición: Split (i, S) : dividir la cadena S en dos nuevas cadenas S ₁ y S ₂ , S ₁ = C ₁ , ..., C _i y S ₂ = C _{i + 1} , ..., C _m .

Complejidad del tiempo: ⁠ ⁠ ${\displaystyle O(\log N)}$

Hay dos casos que deben abordarse:

1. El punto de división está al final de una cadena (es decir, después del último carácter de un nodo hoja)
2. El punto de división está en medio de una cuerda.

El segundo caso se reduce al primero al dividir la cadena en el punto de división para crear dos nuevos nodos hoja y luego crear un nuevo nodo que sea el padre de las dos cadenas componentes.

Por ejemplo, para dividir la cuerda de 22 caracteres que se muestra en la Figura 2.3 en dos cuerdas componentes iguales de longitud 11, consulte el carácter 12 para ubicar el nodo K en el nivel inferior. Elimine el vínculo entre K y G. Vaya al padre de G y reste el peso de K del peso de D. Suba por el árbol y elimine los enlaces derechos a los subárboles que cubren los caracteres más allá de la posición 11, restando el peso de K de sus nodos principales (solo los nodos D y A , en este caso). Finalmente, construya los nodos K ​​y H recién huérfanos concatenándolos y creando un nuevo padre P con un peso igual a la longitud del nodo izquierdo K.

Como la mayoría de las operaciones con cuerdas requieren árboles equilibrados, es posible que sea necesario reequilibrar el árbol después de dividirlo.

Par público < RopeLike , RopeLike > split ( int index ) { if ( índice < peso ) { val split = left . dividir ( índice ); volver Par . de ( reequilibrar ( split . fst ), reequilibrar ( new RopeLikeTree ( split . snd , right ))); } else if ( índice > peso ) { val split = right . dividir ( índice - peso ); volver Par . de ( reequilibrar ( nuevo RopeLikeTree ( izquierda , dividir . fst )), reequilibrar ( dividir . snd )); } else { return Par . de ( izquierda , derecha ); } }                                            

Borrar

Definición: Delete(i, j) eliminar la subcadena C _i , …, C _{i + j − 1} , de s para formar una nueva cadena C ₁ , …, C _{i − 1} , C _{i + j} , …, C _m .

Complejidad del tiempo: ⁠ ⁠ ${\displaystyle O(\log N)}$ .

Esta operación se puede realizar mediante dos Split()y una Concat()operación. Primero, divida la cuerda en tres, dividida por el carácter i -ésimo e i+j -ésimo respectivamente, lo que extrae la cadena para eliminar en un nodo separado. Luego concatene los otros dos nodos.

@Override public RopeLike eliminar ( int inicio , int longitud ) { val lhs = split ( inicio ); val rhs = dividir ( inicio + longitud ); reequilibrio de retorno ( nuevo RopeLikeTree ( lhs . fst , rhs . snd )); }                    

Informe

Definición: Report(i, j) : genera la cadena C _i , …, C _{i + j − 1} .

Complejidad del tiempo: ⁠ ⁠ ${\displaystyle O(j+\log N)}$

Para informar la cadena C _i ,…, C _{i + j − 1} , encuentre el nodo u que contiene C _i y weight(u) >= j, y luego recorra T comenzando en el nodo u . Salida C _i , …, C _{i + j − 1} haciendo un recorrido en orden de T comenzando en el nodo u .

Comparación con matrices monolíticas.

Ventajas:

• Las cuerdas permiten una inserción y eliminación de texto mucho más rápidas que las matrices de cadenas monolíticas, en las que las operaciones tienen una complejidad temporal O (n).
• Las cuerdas no requieren memoria adicional O(n) cuando se operan (las matrices la necesitan para las operaciones de copia).
• Las cuerdas no requieren grandes espacios de memoria contiguos.
• Si solo se utilizan versiones no destructivas de las operaciones, la cuerda es una estructura de datos persistente . En el ejemplo del programa de edición de texto, esto permite admitir fácilmente múltiples niveles de deshacer .

Desventajas:

• Mayor uso general del espacio cuando no está en funcionamiento, principalmente para almacenar los nodos principales. Existe un equilibrio entre la cantidad de memoria total que representa dicha sobrecarga y la duración de los datos que se procesan como cadenas. Las cadenas en las figuras de ejemplo anteriores son irrealmente cortas para las arquitecturas modernas. La sobrecarga es siempre O(n), pero la constante puede hacerse arbitrariamente pequeña.
• Aumento del tiempo para gestionar el almacenamiento adicional.
• Mayor complejidad del código fuente; mayor riesgo de errores

Esta tabla compara las características algorítmicas de las implementaciones de cuerdas y cuerdas, no su velocidad bruta . Las cadenas basadas en matrices tienen una sobrecarga menor, por lo que (por ejemplo) las operaciones de concatenación y división son más rápidas en conjuntos de datos pequeños. Sin embargo, cuando se utilizan cadenas basadas en matrices para cadenas más largas, la complejidad del tiempo y el uso de memoria para insertar y eliminar caracteres se vuelven inaceptablemente grandes. Por el contrario, una estructura de datos de cuerda tiene un rendimiento estable independientemente del tamaño de los datos. Además, la complejidad espacial de las cuerdas y las matrices es O(n). En resumen, las cuerdas son preferibles cuando los datos son grandes y se modifican con frecuencia.

Ver también

• El entorno de programación Cedar , que utilizó cuerdas "casi desde sus inicios" ^[1]
• La enfilada Modelo T , una estructura de datos similar de principios de los años 1970
• Gap buffer , una estructura de datos comúnmente utilizada en editores de texto que permite operaciones eficientes de inserción y eliminación agrupadas cerca de la misma ubicación.
• Tabla de piezas , otra estructura de datos comúnmente utilizada en editores de texto

Referencias

1. Boehm, Hans-J; Atkinson, Russ; Plass, Michael (diciembre de 1995). «Cuerdas: una alternativa a las cuerdas» ( PDF ) . Software: práctica y experiencia . 25 (12). Nueva York, NY, Estados Unidos: John Wiley & Sons, Inc.: 1315–1330. doi : 10.1002/spe.4380251203. Archivado desde el original el 8 de marzo de 2020.
2. "Descripción general de la implementación de cuerdas". www.sgi.com . Archivado desde el original el 19 de diciembre de 2017 . Consultado el 1 de marzo de 2017 .

Enlaces externos

• Implementación de cuerdas "absl::Cord" dentro de la biblioteca The Abseil
• Implementación de cuerdas "C cords" dentro de la biblioteca Boehm Garbage Collector
• Especificación SGI C++ para cuerdas (compatible con STLPort y libstdc++)
• Cuerdas para C#
• cuerdas para Common Lisp
• Cuerdas para Java
• Cuerdas tipo cuerda para Java
• Cuerdas para JavaScript
• Cuerdas para el limbo
• cuerdas para nim
• Cuerdas para OCaml
• piropos para Python
• Cuerdas para Smalltalk
• SwiftRope para Swift
• "Ropey" para Rust