Tabla de piezas

En informática , una tabla de fragmentos es una estructura de datos que se utiliza normalmente para representar un documento de texto mientras se edita en un editor de texto . Inicialmente, se crea una referencia (o "span") a todo el archivo original, que representa el archivo aún sin cambios. Las inserciones y eliminaciones posteriores reemplazan un span por combinaciones de una, dos o tres referencias a secciones del documento original o a un búfer que contiene el texto insertado. ^[1]

Normalmente, el texto del documento original se guarda en un bloque inmutable y el texto de cada inserción posterior se almacena en nuevos bloques inmutables. Debido a que incluso el texto eliminado sigue incluido en la tabla de fragmentos, esto hace que la deshacer ilimitada o de varios niveles sea más fácil de implementar con una tabla de fragmentos que con estructuras de datos alternativas, como un búfer de espacios .

Esta estructura de datos fue inventada por J Strother Moore . ^[2]

Para esta descripción, utilizamos el buffer como el bloque inmutable para almacenar el contenido.

Una tabla de piezas consta de tres columnas: ^[1]

• ¿Qué buffer?
• Índice de inicio en el buffer
• Longitud en el buffer

Además de la tabla, se utilizan dos buffers para gestionar las ediciones:

• " Buffer original ": un buffer del documento de texto original. Este buffer es de solo lectura.
• " Agregar búfer ": un búfer a un archivo temporal. Este búfer es solo para agregar.

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

Para recuperar el i -ésimo carácter, se lee la entrada apropiada en una tabla de piezas.

Dados los siguientes buffers y tabla de piezas:

Para acceder al carácter i -ésimo, se busca la entrada apropiada en la tabla de piezas.

Por ejemplo, para obtener el valor de Index(15), se recupera la tercera entrada de la tabla de piezas. Esto se debe a que la tercera entrada describe los caracteres del índice 11 al 16 (la primera entrada describe los caracteres del índice 0 al 5, la siguiente es del 6 al 10). La entrada de la tabla de piezas indica al programa que busque los caracteres en el búfer " agregar archivo ", comenzando en el índice 17 de ese búfer. El índice relativo en esa entrada es 15-11 = 4, que se suma a la posición inicial de la entrada en el búfer para obtener el índice de la letra: 4+17 = 21. El valor de Index(15)es el carácter número 21 del búfer "agregar archivo", que es el carácter "o".

Para los buffers y la tabla de piezas dados arriba, se muestra el siguiente texto:

Lorem ipsum dolor sentado amet

La inserción de caracteres al texto consiste en:

• Agregar caracteres al búfer de "agregar archivo" y
• Actualización de la entrada en la tabla de piezas (dividir una entrada en dos o tres)

La eliminación de un solo carácter puede deberse a una de dos posibles condiciones:

• La eliminación se produce al inicio o al final de una entrada de pieza, en cuyo caso se modifica la entrada correspondiente en la tabla de piezas.
• La eliminación se produce en medio de una entrada de una pieza, en cuyo caso la entrada se divide y luego se modifica una de las entradas sucesoras como se indicó anteriormente.

Varios editores de texto utilizan una tabla de fragmentos en RAM internamente, incluidos Bravo , ^[1] Abiword , ^{[3] [4] [5]} Atom ^[6] y Visual Studio Code . ^[7]

La función de "guardado rápido" en algunas versiones de Microsoft Word utiliza una tabla de piezas para el formato de archivo en disco. ^[2]

La representación en disco de archivos de texto en el Sistema Oberon utiliza una técnica de cadena de piezas que permite que partes de un documento apunten a texto almacenado en algún otro documento, de forma similar a la transclusión . ^[8]

• Cuerda (informática)
• Buffer de espacio , 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
• Enfilade , el Modelo T Enfilade es una tabla de piezas con una implementación basada en árboles.