diff a stromy

Minule jsem tu psal, jak dělat diffy a jak se tato znalost dá využít pro kompresi dat. Teď bych chtěl jít o krok dál k diffování libovolných stromů.

Už tehdy jsem se zmínil, že jsem o tom chvíli přemýšlel, ale jako vždycky jsem se nedostal příliš daleko. V hlavě jsem měl jen řešení několika triviálních případů, ale žádné principy. Pak ale moje obsesivní povaha převzala kontrolu a tendence všechno dotáhnout tak daleko, jak jen to bude možné. Jako vždycky jsem potřeboval algoritmus.

Když se dostanu do problémů, měl bych vždycky se vždycky zeptat WWEKD – What would Edward Kmett do? On má řešení mnoha problémů, tak proč ne zrovna toho současného?

Když jsem se rozhlížel po netu, zjistil jsem, že existují nějaké knihovny, jako třeba diffson, které počítají diffy JSON stromů. Ty ale neumí všechno. diffson dělá diffy jen úroveň po úrovni. Zkontroluje kořen jednoho stromu s druhým a když se liší, začne spolu porovnávat vnořené uzly. Neumí uspokojivě spočítat diff pro rozsáhlejší změny struktury stromu.

Například mám strom

        (5)
       /   \
    (2)     [6]
   /   \
[1]     [3]

a chci zjistit jeho diff se stromem, který jen jinak zcela schodný, ale má jen jednu úroveň navíc.

    (4)
   /   \
[0]     (5)
       /   \
    (2)     [6]
   /   \
[1]     [3]

Výsledný diff by měl být maličký – doslova: sem přidej jeden uzel a hotovo.

A právě tady do hry vstupuje Edward Kmett. Vzpomněl jsem si totiž na jeho přednášku, kde mluvil o succinct datových strukturách a wavelet stromech, které mají efektivní operace rank a select. Pak zmínil, že tohle všechno jde použít k práci s JSON dokumenty bez toho, aby je bylo nutné parsovat. Zmínil, že je (za pomoci succint DS) možné vytvořit velice kompaktní index, s jehož pomocí se dají efektivně číst data z JSON stringu bez jeho naparsování do stromové datové struktury. Hlavní ingrediencí tohoto přístupu byly závorky. Ty určovaly, kde daný podstrom začíná a kde končí. V kombinaci s rychlým rank/select pak můžu efektivně najít konec podstromu a celý ho přeskočit.

Závorky jsou hlavní i pro diffování stromů.

Nejdřív musím strom převést na lineární formu, kde závorky udávají začátek a konec každého z podstromů1.

Z dvou příkladů uvedených výše vzniknou následující sekvence tokenů. Číslo je jeden token stejně jako otevírací a uzavírací závorka.

      (5 (2 1 3) 6)
( 4 0 (5 (2 1 3) 6))

Teď když mám dva stringy, můžu spočítat jejich diff přesně tak, jsem to psal minule. Výsledkem bude něco jako:

+(+4+0             -)

A to je všechno. Diff zahrnuje jen nezbytně nutné množství změn: Přidat jeden uzel na začátek s hodnotou 4, levý podstrom obsahuje nulu, pak následuje zbytek stromu beze změny a nakonec je nový strom ukončen. Změny nejsou tak snadno čitelné jako je JSON diff, ale dokážou zahrnout složité transformace a změny struktury.

Ukážu příklad s rotací stromu. Strom před rotací:

        (6)
       /   \
    (2)     [7]
   /   \
[1]     (4)
       /   \
    [3]     [5]

Po rotaci:

      (4)
     /   \
  (2)     (6)
  / \     / \
[1] [3] [5] [7]

Tokenizace, LCS (nejdelší společná subsekvence) a diff:

A:      (  6 (2 1 ( 4 3       5 ) ) 7)
B:      (4   (2 1     3 ) ( 6 5     7))
LCS:    (    (2 1     3       5     7)
diff:   +4-6     -(-4) +)+(+6  -)-)  +)

Je vidět, že diff obsahuje jen uzly 4 a 6. Všechny ostatní zůstaly na svém místě, protože se nezměnilo jejich relativní pořadí.

Po aplikaci diffu už zbývá jen z nové sekvence tokenů postavit nový strom, který obsahuje aplikované změny.

Tohle všechno se dá dělat líně: Sekvenci tokenů nemusím materializovat, můžu ji produkovat líně, stejně tak i patchování může být líné a výsledek je zase líná sekvence ze které líně stavím strom. Pořád je však třeba postavit zcela nový strom.

Dalším logickým krokem je diff interpretovat jako sérii transformací, kterou je možné provést in-place. Ale to až někdy příště, protože zatím nevím, jak to udělat.


Dodatky:

Běžný algoritmus počítající LCS běží v kvadratickém čase a potřebuje kvadratický prostor. Pomocí metody čtyř rusů se dá dostat na čas O(n2 / log(n)). Tedy tak se to aspoň všude píše, ale nikde jsem nenašel veřejně dostupnou publikaci, která by vysvětlila detaily. Jiný algoritmus potřebuje jen lineární místo, další zas běží v čase O((n+r)log(n)), kde r je editační vzdálenost. Speciální případy (např. neopakující se tokeny) se dají vyřešit rychleji. Dále existují techniky aproximace LCS, které jsou rychlejí než přesný výpočet.

Když jsem začal hledat, jak dělat přímo diff stromů bez převedení na sekvenci, v A survey of potential XHTML diff/merge algorithms jsem narazil na XyDiff. Ten běží v běží v průměrném lineárním čase, produkuje přibližné (ale dostatečně dobré) výsledky a je založen na hashování. Každý podstrom je zhashován a to umožňuje rychle hledat odpovídající podstromy v obou vstupech. Tohle by se dalo použít pro snížení počtu tokenů i v mém přístupu.

Kód tady.


  1. Když jde o strom, který má fixní počet potomků, uzavírací závorky nejsou potřeba, protože jsou implicitní.

Flattr this!

This entry was posted in Algo. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *