funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

diff a stromy

25. 9. 2016 — k47

Minule jsem tu psal, jak dělat diffy a jak se tato zna­lost dá využít pro kom­presi dat. Teď bych chtěl jít o krok dál k di­f­fo­vání li­bo­vol­ných stromů.

Už tehdy jsem se zmínil, že jsem o tom chvíli pře­mýš­lel, ale jako vždycky jsem se ne­do­stal příliš daleko. V hlavě jsem měl jen řešení ně­ko­lika tri­vi­ál­ních pří­padů, ale žádné prin­cipy. Pak ale moje ob­se­sivní povaha pře­vzala kon­t­rolu a ten­dence všechno do­táh­nout tak daleko, jak jen to bude možné. Jako vždycky jsem po­tře­bo­val al­go­rit­mus.

Když se do­stanu do pro­blémů, měl bych vždycky se vždycky zeptat WWEKDWhat would Edward Kmett do? On má řešení mnoha pro­blémů, tak proč ne zrovna toho sou­čas­ného?

Když jsem se roz­hlí­žel po netu, zjis­til jsem, že exis­tují nějaké knihovny, jako třeba di­ff­son, které po­čí­tají diffy JSON stromů. Ty ale neumí všechno. diffson dělá diffy jen úroveň po úrovni. Zkon­t­ro­luje kořen jed­noho stromu s druhým a když se liší, začne spolu po­rov­ná­vat vno­řené uzly. Neumí uspo­ko­jivě spo­čí­tat diff pro roz­sáh­lejší změny struk­tury stromu.

Na­pří­klad mám strom

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

a chci zjis­tit jeho diff se stro­mem, 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 ma­ličký – do­slova: sem přidej jeden uzel a hotovo.

A právě tady do hry vstu­puje Edward Kmett. Vzpo­mněl jsem si totiž na jeho před­nášku, kde mluvil o suc­cinct da­to­vých struk­tu­ráchwa­ve­let stro­mech, které mají efek­tivní ope­race rankselect. Pak zmínil, že tohle všechno jde použít k práci s JSON do­ku­menty bez toho, aby je bylo nutné par­so­vat. Zmínil, že je (za pomoci suc­cint DS) možné vy­tvo­řit velice kom­paktní index, s jehož pomocí se dají efek­tivně číst data z JSON stringu bez jeho na­par­so­vání do stro­mové datové struk­tury. Hlavní in­gre­di­encí tohoto pří­stupu byly zá­vorky. Ty ur­čo­valy, kde daný pod­strom začíná a kde končí. V kom­bi­naci s rych­lým rank/select pak můžu efek­tivně najít konec pod­stromu a celý ho pře­sko­čit.

Zá­vorky jsou hlavní i pro di­f­fo­vání stromů.

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

Z dvou pří­kladů uve­de­ných výše vznik­nou ná­sle­du­jící sek­vence tokenů. Číslo je jeden token stejně jako ote­ví­rací a uza­ví­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ý­sled­kem bude něco jako:

+(+4+0             -)

A to je všechno. Diff za­hr­nuje jen ne­zbytně nutné množ­ství změn: Přidat jeden uzel na za­čá­tek s hod­no­tou 4, levý pod­strom ob­sa­huje nulu, pak ná­sle­duje zbytek stromu beze změny a na­ko­nec je nový strom ukon­čen. Změny nejsou tak snadno či­telné jako je JSON diff, ale do­ká­žou za­hr­nout slo­žité trans­for­mace a změny struk­tury.

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]

To­ke­ni­zace, LCS (nejdelší spo­lečná sub­sek­vence) 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 ob­sa­huje jen uzly 4 a 6. Všechny ostatní zů­staly na svém místě, pro­tože se ne­změ­nilo jejich re­la­tivní pořadí.

Po apli­kaci diffu už zbývá jen z nové sek­vence tokenů po­sta­vit nový strom, který ob­sa­huje apli­ko­vané změny.

Tohle všechno se dá dělat líně: Sek­venci tokenů ne­mu­sím ma­te­ri­a­li­zo­vat, můžu ji pro­du­ko­vat líně, stejně tak i patcho­vání může být líné a vý­sle­dek je zase líná sek­vence ze které líně stavím strom. Pořád je však třeba po­sta­vit zcela nový strom.

Dalším lo­gic­kým krokem je diff in­ter­pre­to­vat jako sérii trans­for­mací, kterou je možné pro­vést in-place. Ale to až někdy příště, pro­tože zatím nevím, jak to udělat.


Do­datky:

Běžný al­go­rit­mus po­čí­ta­jící LCS běží v kva­d­ra­tic­kém čase a po­tře­buje kva­d­ra­tický pro­stor. 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 ne­na­šel ve­řejně do­stup­nou pu­b­li­kaci, která by vy­svět­lila de­taily. Jiný al­go­rit­mus po­tře­buje jen li­ne­ární místo, další zas běží v čase O((n+r)log(n)), kde r je edi­tační vzdá­le­nost. Spe­ci­ální pří­pady (např. ne­o­pa­ku­jící se tokeny) se dají vy­ře­šit rych­leji. Dále exis­tují tech­niky apro­xi­mace LCS, které jsou rych­lejí než přesný vý­po­čet.

Když jsem začal hledat, jak dělat přímo diff stromů bez pře­ve­dení na sek­venci, v A survey of po­ten­tial XHTML diff/merge al­go­ri­thms jsem na­ra­zil na XyDiff. Ten běží v běží v prů­měr­ném li­ne­ár­ním čase, pro­du­kuje při­bližné (ale do­sta­tečně dobré) vý­sledky a je za­lo­žen na ha­sho­vání. Každý pod­strom je zha­sho­ván a to umož­ňuje rychle hledat od­po­ví­da­jící pod­stromy v obou vstu­pech. 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 po­tomků, uza­ví­rací zá­vorky nejsou po­třeba, pro­tože jsou im­pli­citní.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články