En la programación de computadoras , una cuerda , o cordón , es una estructura de datos compuesta de cuerdas más pequeñas que se usa para almacenar y manipular eficientemente una cuerda muy larga. Por ejemplo, un programa de edición de texto puede usar 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 árbol binario donde cada hoja (nodo final) sostiene una cuerda y una longitud (también conocida como "peso"), y cada nodo más arriba del árbol contiene la suma de las longitudes de todas las hojas en su subárbol izquierdo. . Un nodo con dos hijos divide la cadena completa 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 inmutables constantes 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 la 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.
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 1 ,…, C i , S' , C i + 1 ,…, C m . - Complejidad del tiempo:.
Esta operación se puede realizar mediante ay Split()
dos Concat()
operaciones. El costo es la suma de los tres.
Índice
- Definición:
Index(i)
devuelve el carácter en la posición i - Complejidad del tiempo:
Para recuperar el carácter i -ésimo, comenzamos una búsqueda recursiva desde el nodo raíz:
índice de función ( nodo RopeNode , entero i ) si nodo . peso <= i y existe ( nodo . derecha ) luego devuelve índice ( nodo . derecha , i - nodo . peso ) final si existe ( nodo . izquierda ) , devuelve el índice ( nodo . izquierda , i ) final nodo de retorno . cadena [ i ] final
Por ejemplo, para encontrar el carácter en i=10
en la 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 reste 9 de 10 (saliendo i=1
) y vaya al niño correcto (D). Luego, como 6 es mayor que 1 y hay un hijo izquierdo, vaya al hijo izquierdo (G). 2 es mayor que 1 y hay un hijo izquierdo, así que ve de nuevo al hijo izquierdo (J). Finalmente, 2 es mayor que 1 pero no hay un hijo a la izquierda, por lo que el carácter en el índice 1 de la cadena corta "na" (es decir, "a") es la respuesta.
Concat
- Definición::
Concat(S1, S2)
concatenar dos cuerdas, S 1 y S 2 , en una sola cuerda. - Complejidad del tiempo: (o 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 derecha = S2 , que es tiempo constante. El peso del nodo padre se establece en la longitud del hijo izquierdo S 1 , lo que tomaría tiempo, si el árbol está equilibrado.
Como la mayoría de las operaciones con cuerdas requieren árboles equilibrados, es posible que sea necesario volver a equilibrar el árbol después de la concatenación.
Separar
- Definición::
Split (i, S)
divide la cuerda S en dos nuevas cuerdas S 1 y S 2 , S 1 = C 1 ,…, C i y S 2 = C i + 1 ,…, C m . - Complejidad del tiempo:
Hay dos casos que deben tratarse:
- El punto de división está al final de una cadena (es decir, después del último carácter de un nodo hoja)
- 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 de componentes.
Por ejemplo, para dividir la cuerda de 22 caracteres que se muestra en la Figura 2.3 en dos cuerdas de componentes iguales de longitud 11, consulte el duodécimo carácter para ubicar el nodo K en el nivel inferior. Retire el enlace entre K y G . Ir a la matriz de G y restar el peso de K a partir del peso de D . Suba por el árbol y elimine los enlaces correctos a los subárboles que cubran a los personajes más allá de la posición 11, restando el peso de K de sus nodos principales (solo el nodo D y A , en este caso). Finalmente, construir los nodos recién huérfanos K y H mediante la concatenación de ellos juntos y la creación de 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 volver a equilibrar el árbol después de la división.
Borrar
- Definición::
Delete(i, j)
elimine la subcadena C i ,…, C i + j - 1 , de s para formar una nueva cadena C 1 ,…, C i - 1 , C i + j ,…, C m . - Complejidad del tiempo:.
Esta operación se puede realizar mediante dos Split()
y una Concat()
operación. Primero, divida la cuerda en tres, dividida por i -ésimo e i + j -ésimo carácter respectivamente, lo que extrae la cadena para eliminar en un nodo separado. Luego concatenar los otros dos nodos.
Informe
- Definición:
Report(i, j)
salida de la cadena C i ,…, C i + j - 1 . - Complejidad del tiempo:
Para informar la cadena C i ,…, C i + j - 1 , encuentre el nodo u que contiene C i y weight(u) >= j
, y luego atraviese 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
Operación | Soga | Cuerda |
---|---|---|
Índice [1] | O (log n) | O (1) |
Dividir [1] | O (log n) | O (1) |
Concatenar (destructivo) | O (log n) sin reequilibrio / O (n) en el peor de los casos | En) |
Concatenar (no destructivo) | En) | En) |
Repite cada carácter [1] | En) | En) |
Insertar [2] | O (log n) sin reequilibrio / O (n) en el peor de los casos | En) |
Adjuntar [2] | O (log n) sin reequilibrio / O (n) en el peor de los casos | O (1) amortizado, O (n) peor caso |
Borrar | O (log n) | En) |
Informe | O (j + log n) | O (j) |
Construir | En) | En) |
Ventajas:
- Las cuerdas permiten una inserción y eliminación de texto mucho más rápida que las matrices de cadenas monolíticas, en las que las operaciones tienen una complejidad de tiempo O (n).
- Las cuerdas no requieren O (n) memoria adicional 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 operaciones, la cuerda es una estructura de datos persistente . Para el ejemplo del programa de edición de texto, esto conduce a un soporte sencillo para múltiples niveles de deshacer .
Desventajas:
- Mayor uso general del espacio cuando no se está operando, principalmente para almacenar nodos padres. Existe una compensación entre la cantidad de memoria total que representa dicha sobrecarga y la duración de los datos que se procesan como cadenas. Las cadenas de las figuras de ejemplo anteriores son poco realistas para las arquitecturas modernas. La sobrecarga es siempre O (n), pero la constante puede hacerse arbitrariamente pequeña.
- Aumento del tiempo para administrar el almacenamiento adicional
- Mayor complejidad del código fuente; mayor riesgo de errores
Esta tabla compara los rasgos algorítmicos de las implementaciones de cuerdas y cuerdas, no su velocidad bruta . Las cadenas basadas en matrices tienen una sobrecarga más pequeña, 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 la memoria para insertar y eliminar caracteres se vuelve inaceptablemente grande. Por el contrario, una estructura de datos de cables tiene un rendimiento estable independientemente del tamaño de los datos. Además, la complejidad del espacio para cuerdas y 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 del Modelo T , una estructura de datos similar de principios de la década de 1970.
- Gap buffer , una estructura de datos comúnmente utilizada en editores de texto que permite operaciones de inserción y eliminación eficientes agrupadas cerca de la misma ubicación
- Tabla de piezas , otra estructura de datos comúnmente utilizada en editores de texto
Referencias
- ^ a b c d e Boehm, Hans-J; Atkinson, Russ; Plass, Michael (diciembre de 1995). "Cuerdas: una alternativa a las cuerdas" ( PDF ) . Software: práctica y experiencia . Nueva York, NY, EE.UU .: John Wiley & Sons, Inc. 25 (12): 1315–1330. doi : 10.1002 / spe.4380251203 . Archivado desde el original el 8 de marzo de 2020.
- ^ a b "Descripción general de la implementación de cuerdas" . www.sgi.com . Consultado el 1 de marzo de 2017 .
enlaces externos
- Implementación de "cables C" de cables 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 para JavaScript
- Cuerdas para el limbo
- cuerdas para Nim
- Cuerdas para OCaml
- piropos para Python
- Cuerdas para Smalltalk
- SwiftRope para Swift
- "Ropey" para Rust