Table de pièces
En informatique, une table de pièces est une structure de données généralement utilisée pour représenter un document texte pendant qu'il est édité dans un éditeur de texte. Dans un premier temps, une référence à l'ensemble du fichier d'origine est créée, qui représente le fichier encore inchangé. Les insertions et suppressions ultérieures remplacent une référence par des combinaisons d'une, deux ou trois références à des sections du document d'origine ou à une mémoire tampon contenant du texte inséré[1].
La mise en forme de cet article est à améliorer ().
La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».
En règle générale, le texte du document original est conservé dans un bloc immuable et le texte de chaque insertion ultérieure est stocké dans de nouveaux blocs immuables. Étant donné que même le texte supprimé est toujours inclus dans la table des pièces, cela rend l'annulation répétée (possiblement indéfiniment) plus facile à mettre en œuvre avec une table des pièces qu'avec des structures de données alternatives telles qu'un tampon d'espacement.
Cette structure de données a été inventée par J Strother Moore[2].
Description
modifierPour cette description, nous utilisons un tampon comme bloc immuable pour stocker le contenu du texte.
Un tableau de pièces se compose de trois colonnes pour chaque tampon[1] :
- Référence vers le tampon
- Index de départ dans le tampon
- Longueur dans le tampon
En plus de la table, deux tampons sont utilisés pour gérer les modifications :
- « Tampon d'origine » : un tampon vers le document texte d'origine. Ce tampon est en lecture seule.
- « Tampon d'ajouts » : un tampon vers un fichier temporaire. Il s'agit d'un tampon d'écriture
Opérations
modifierIndexation
modifierDéfinition :
Index(i): renvoie le i-ème caractère du texte
Pour récupérer le i-ème caractère, l'entrée appropriée dans une table de pièces est lue.
Exemple
modifierÉtant donné les tampons et la table de pièces suivants :
| Tampon | Contenu |
|---|---|
| Fichier originel | ipsum sit amet
|
| Fichier d'ajout | Lorem deletedtext dolor
|
| Lequel | Index de départ | Longueur |
|---|---|---|
| Ajout | 0 | 6 |
| Originel | 0 | 5 |
| Ajout | 17 | 6 |
| Originel | 5 | 9 |
Pour accéder au i-ème caractère, l'entrée appropriée dans la table des pièces est recherchée.
Par exemple, pour obtenir la valeur de Index(15), la 3ème entrée de la table des pièces est récupérée. C'est parce que la 3ème entrée décrit les caractères de l'index 11 à 16 (la première entrée décrit les caractères de l'index 0 à 5, la suivante de 6 à 10). L'entrée de la table des pièces indique au programme de rechercher les caractères dans le tampon « Fichier d'ajout », en commençant à l'index 17 dans ce tampon. L'index relatif dans cette entrée est 15-11 = 4, qui est ajouté à la position de départ de l'entrée dans le tampon pour obtenir l'index de la lettre : 4+17 = 21. La valeur de Index(15) est le 21ème caractère du tampon « ajouter un fichier », qui est le caractère « o ».
Pour les tampons et le tableau des pièces donnés ci-dessus, le texte suivant est affiché :
Lorem ipsum dolor si amet
Insertion
modifierL'insertion de caractères dans le texte consiste à :
- Ajouter des caractères au tampon d'ajout
- Mettre à jour l'entrée dans la table des pièces (diviser une entrée en deux ou trois)
Suppression
modifierLa suppression d'un seul caractère peut suivre deux scénarios possibles :
- La suppression s'effectue au début ou à la fin d'une entrée de pièce, auquel cas l'entrée appropriée dans la table des pièces est modifiée.
- La suppression s'effectue au milieu d'une entrée de pièce, auquel cas l'entrée est divisée puis l'une des entrées successeurs est modifiée comme ci-dessus.
Usage
modifierPlusieurs éditeurs de texte utilisent en interne une table de pièces en RAM, notamment Bravo, [1] Abiword, [3],[4],[5] Atom [6] et Visual Studio Code[7].
La fonction « Sauvegarde rapide » de certaines versions de Microsoft Word utilise un tableau de pièces pour le format de fichier sur disque[2].
La représentation sur disque des fichiers texte dans le système Oberon utilise une technique de chaîne morcelé qui permet à des morceaux d'un document de pointer vers du texte stocké dans un autre document, de manière similaire à la transclusion.
Voir aussi
modifier- Corde (informatique)
- Tampon d'espacement, une structure de données couramment utilisée dans les éditeurs de texte qui permet des opérations d'insertion et de suppression efficaces regroupées à proximité du même emplacement
- Enfilade, les enfilades sont des tables de pièces avec une implémentation basée sur des arbres.
Références
modifier- Crowley, « Data Structures for Text Sequences - 6.4 The piece table method » [archive du ], www.cs.unm.edu, (consulté le )
- David Lu. "What's been wrought using the Piece Table?". (discussion)
- "AbiWord Development: Piece Table Background".
- James Brown. "Piece Chains: Design & Implementation of a Win32 Text Editor".
- Joaquin Cuenca Abela. "Improving the AbiWord's Piece Table".
- nathansobo, « Atom’s new concurrency-friendly buffer implementation », Atom Blog, (consulté le )
- "VS Code 1.21 Release Notes (source code)
