Kusový stůl - Piece table

A kusový stůl je datová struktura obvykle se používá k reprezentaci řady úpravy na textový dokument. Vytvoří se počáteční odkaz (nebo „rozpětí“) na celý původní soubor s následnými vložením a odstraněním, které se vytvoří jako kombinace jednoho, dvou nebo tří odkazů na oddíly původního dokumentu nebo rozpětí přidružených k dřívějším dokumentům vložky.[1]

Text původního dokumentu je obvykle uložen v jednom neměnný blok a text každé následující přílohy je uložen v nových neměnných blocích. Protože v tabulce kusů je stále obsažen i odstraněný text, je víceúrovňový nebo neomezený vrátit snadnější implementace s tabulkou kusů než s alternativními datovými strukturami, jako je a vyrovnávací paměť mezery.

Tuto datovou strukturu vynalezl J Strother Moore.[2]

Popis

Pro tento popis používáme nárazník jako neměnný blok pro uložení obsahu.

Tabulka kusů se skládá ze tří sloupců:[1]

  • Jaký nárazník
  • Spusťte index ve vyrovnávací paměti
  • Délka ve vyrovnávací paměti

Kromě tabulky se ke zpracování úprav používají dvě vyrovnávací paměti:

  • "Původní vyrovnávací paměť": Vyrovnávací paměť původního textového dokumentu. Tato vyrovnávací paměť je pouze pro čtení.
  • "Přidejte vyrovnávací paměť": Vyrovnávací paměť dočasného souboru. Tato vyrovnávací paměť je pouze pro přidání.

Operace

Index

Definice: Rejstřík (i): vrátit znak na pozici i

Chcete-li získat i-tý znak, přečte se příslušná položka v tabulce kusů.

Příklad

Vzhledem k následujícím nárazníkům a tabulce kusů:

BufferObsah
Původní souboripsum sit amet
Přidat souborLorem vymazal text dolor
Kusový stůl
KterýSpustit indexDélka
Přidat06
Originál06
Přidat185
Originál69

Pro přístup k i-tý znak, vyhledá se příslušný záznam v tabulce kusů.

Například pro získání hodnoty Rejstřík (15), načte se 3. položka tabulky kusů. Je to proto, že třetí položka popisuje znaky z indexu 12 až 16 (první položka popisuje znaky v indexu 0 až 5, další je 6 až 11). Zadání tabulky kusů dává programu pokyn, aby hledal znaky vpřidat soubor"vyrovnávací paměť, počínaje indexem 18 v této vyrovnávací paměti. Relativní index v této položce je 15-12 = 3, který se přidá k počáteční pozici položky v vyrovnávací paměti, aby se získal index písmene: 3 + 18 = 21. Hodnota Rejstřík (15) je 21. znak vyrovnávací paměti „přidat soubor“, což je znak „o“.

U vyrovnávacích pamětí a tabulky kusů uvedených výše se zobrazuje následující text:

Lorem ipsum dolor sedět

Vložit

Vkládání znaků do textu se skládá z:

  • Přidávání znaků do vyrovnávací paměti "přidat soubor" a
  • Aktualizace záznamu v tabulce kusů (rozdělení záznamu na dva nebo tři)

Vymazat

Odstranění zahrnuje pouze úpravu příslušné položky v tabulce kusů.

Používání

Několik textové editory interně používat tabulku kusů v RAM, včetně Bravo,[1] Abiword,[3][4][5] Atom[6] a Kód sady Visual Studio.[7]

Funkce "rychlé ukládání" v některých verzích aplikace Microsoft Word používá tabulkovou část pro formát souboru na disku.[2]

Reprezentace textových souborů na disku v Oberonův systém používá a kusový řetěz technika, která umožňuje částem jednoho dokumentu ukazovat na text uložený v nějakém jiném dokumentu, podobně jako transluce.[8]

Viz také

  • Lano (informatika)
  • Mezera mezery, datová struktura běžně používaná v textových editorech, která umožňuje efektivní operace vkládání a mazání seskupené poblíž stejného místa

Reference

  1. ^ A b C Crowley, Charles (10.06.1998). "Datové struktury pro textové sekvence - 6.4 Metoda tabulky kusů" (PDF). Archivovány od originál (PDF) dne 2018-02-23. Citovat deník vyžaduje | deník = (Pomoc)
  2. ^ A b David Lu.„Co bylo zpracováno pomocí Kusového stolu?“.(diskuse )
  3. ^ „AbiWord Development: Piece Table Background“.
  4. ^ James Brown. „Piece Chains: Design & Implementation of a Win32 Text Editor“.
  5. ^ Joaquin Cuenca Abela.„Zlepšení tabulky kusů AbiWord“.
  6. ^ "Atom je nová implementace vyrovnávací paměti přátelská k souběžnosti"
  7. ^ „VS Code 1.21 - poznámky k verzi (zdrojový kód )
  8. ^ Niklaus Wirth, Jürg Gutknecht.„Projekt Oberon: Návrh operačního systému a překladače“ Archivováno 12. 04. 2013 na Wayback Machine.2005.p. 90.