Bitbord

Inom datorer är en bittabell en datastruktur som vanligtvis används för att representera ett textdokument medan det redigeras i en textredigerare . Initialt skapas en referens (eller 'span') till hela originalfilen, som representerar den ännu oförändrade filen. Efterföljande infogning och borttagning ersätter ett spann med kombinationer av en, två eller tre referenser till avsnitt av antingen originaldokumentet eller till en buffert som innehåller infogat text.

Typiskt hålls texten i originaldokumentet i ett oföränderligt block, och texten för varje efterföljande infogning lagras i nya oföränderliga block. Eftersom även raderad text fortfarande finns med i stycketabellen, gör detta flernivå- eller obegränsad ångra lättare att implementera med en stycketabell än med alternativa datastrukturer som en gapbuffert .

Denna datastruktur uppfanns av J Strother Moore .

Beskrivning

För denna beskrivning använder vi buffert som det oföränderliga blocket för att hålla innehållet.

En bittabell består av tre kolumner:

Vilken buffert
Starta index i bufferten
Längd i bufferten

Förutom tabellen används två buffertar för att hantera redigeringar:

" Originalbuffert ": En buffert till originaltextdokumentet. Denna buffert är skrivskyddad.
" Lägg till buffert ": En buffert till en temporär fil. Denna buffert är endast tillägg.

Operationer

Index

Definition: Index(i) : returnera tecknet vid position i

För att hämta det i -te tecknet läses lämplig post i en pjästabell.

Exempel

Med tanke på följande buffertar och bittabell:

Buffert	Innehåll
Originalfil	`ipsum sit amet`
Lägg till fil	`Lorem raderad text dolor`

Bitbord
Som	Starta index	Längd
Lägg till	0	6
Original	0	6
Lägg till	17	6
Original	6	8

För att komma åt det i -te tecknet, letas lämplig post i pjästabellen upp.

Till exempel, för att få värdet på Index(15) hämtas den 3:e posten i pjästabellen. Detta beror på att den 3:e posten beskriver tecknen från index 12 till 16 (den första posten beskriver tecken i index 0 till 5, nästa är 6 till 11). Stycktabellsposten instruerar programmet att leta efter tecknen i " lägg till fil "-bufferten, med början vid index 18 i den bufferten. Det relativa indexet i den posten är 15-12 = 3, vilket läggs till startpositionen för posten i bufferten för att få index för bokstaven: 3+18 = 21. Värdet på Index(15) är det 21:a tecknet av bufferten "lägg till fil", som är tecknet "o".

För buffertarna och stycketabellen ovan visas följande text:

Lorem ipsum dolor sit amet

Föra in

Att infoga tecken i texten består av:

Lägga till tecken i bufferten "lägg till fil", och
Uppdatera posten i pjästabell (dela en post i två eller tre)

Radera

Radering av enstaka tecken kan vara ett av två möjliga villkor:

Raderingen sker i början eller slutet av en pjäspost, i vilket fall den lämpliga posten i pjästabellen ändras.
Borttagningen är mitt i en delpost, i vilket fall posten delas upp och sedan ändras en av efterföljande poster enligt ovan.

Användande

Flera textredigerare använder en in-RAM-bittabell internt, inklusive Bravo , Abiword , Atom och Visual Studio Code .

Funktionen "snabb spara" i vissa versioner av Microsoft Word använder en bittabell för filformatet på disken.

Representationen på disken av textfiler i Oberon-systemet använder en kedjeteknik som gör att delar av ett dokument kan peka på text som är lagrad i något annat dokument, liknande transklusion .

Se även

Rep (datavetenskap)
Gap buffer , en datastruktur som vanligtvis används i textredigerare som möjliggör effektiv infogning och borttagning i kluster nära samma plats
Enfilade , Model-T Enfilade är en bittabell med en trädbaserad implementering.