| Both sides previous revision
Previous revision
Next revision
|
Previous revision
Next revision
Both sides next revision
|
treex:api-implementation [2015/12/11 13:35]
ufal |
treex:api-implementation [2015/12/14 03:43]
popel |
| |
| |
| | ==== Setřídění dle ord ==== |
| | Jak implementovat metody ''children'' a ''descendants'' (a ''siblings'', ale to je skoro jako ''node->parent->get_children()'' až na vynechání ''node'' a jiné chápání přepínačů ''add_self'', ''preceding_only'' atd.) a tedy celou datovou strukturu stromu, aby metody (rychle) vracely uzly v pořadí podle slovosledu (i u neprojektivních stromů) a přitom šlo stromy editovat, tedy přidávat a mazat uzly (i z prostředka věty), převěšovat, měnit slovosled. |
| |
| | === PRECOMP-NAIVE === |
| | Předpočítat children i descendants pro každý uzel. |
| | Čtení je tedy rychlé, editace velmi pomalá, paměťová náročnost (zbytečně) velká, implementace v celku jednoduchá. |
| | |
| | === PRECOMP-BITARRAY === |
| | Taky předpočítat, ale seznam všech potomků (a obdobně dětí) nacpat do 8 bajtů, tedy 64 bitů. Uloží se tam indexy uzlů. Pokud má věta víc než 64 slov, tak se to uloží jinam jinak. Musím tedy udržovat pole všech uzlů (dle slovosledu). Přidání jednoho uzlu znamená posunout část tohoto pole o jeden prvek a přepočítat atributy _children a _descendants v podstatě všech uzlů. Asi by se to muselo dělat v Céčku, aby ty bitové operace byly rychlé. |
| | Čtení rychlé, editace velmi pomalá, paměťová náročnost dobrá (+16 bajtů na uzel), implementace složitější. |
| | |
| | === SORTED-CHILDREN === |
| | Děti se ukládají setříděně buď do pole, nebo do spojáku (tedy každý uzel má pointer _next_node, případně i obousměrně _prev_node). Buď se ukládají pravé a levé děti zvlášť, nebo se při vracení dětí s přepínačem ''add_self'' vloží jejich rodič na správnou pozici. Metoda ''descendants'' uloží potomky do pomocného pole (klasickým průchodem do hloubky) a pak dotřídí. Perl i Python mají sort optimalizovaný na předtříděné sekvence (každý trochu jinak, Perl asi o něco lépe než pythoní timsort, který bere jen sekvence začínající na indexu 2**k, ale pro naše krátké sekvence to je asi úplně jedno). Nejde to implementovat jako iterátor bez toho pomocného pole. |
| | |
| | === SORTED-CHILDREN + ALL-NODES === |
| | Navíc se udržuje (setříděné) pole všech uzlů. Hlavní motivace je, že většina bloků cyklí přes všechny uzly (''process_anode''). Tedy je důležité zrychlit tento častý případ, kdy se ''descendants()'' volá na kořeni celého stromu. |
| | Každý uzel má atribut ''ord'' (to předpokládám ve všech zde diskutovaných implementacích, i když i to stojí za zvážení). Takže jde efektivně implementovat i metody ''prev_node'' a ''next_node'' (současná perlí implementace prochází neefektivně všechny uzly, než najde ten s ord+1). |
| | Volání ''descendants'' na nekořeni je stále pomalé, protože vyžaduje alokaci pomocného pole a dotřídění jako SORTED-CHILDREN. |
| | |
| | === PROJECTIVE-OPTIMIZED === |
| | V praxi jsou neprojektivity relativně řídký jev. |
| | Každý uzel má v atributu _leftmost a _rightmost pointer (referenci) na nejlevější/nejpravější uzel svého podstromu a v atributu _next pointer na následující uzel dle slovosledu (čili spoják). |
| | Metoda ''descendants'' tedy začne nejlevějším a iteruje až do nejpravějšího (a vynechá uzel, ze kterého to volám, pokud není ''add_self''). |
| | Problém je jen s neprojektivitami, takovéto uzly musím přeskočit. Každý uzel má tedy seznam (spoják) uzlů, v jejichž spanu (leftmost..rightmost) se slovosledně nachází a přitom není jejich potomkem. Většina uzlů je projektivních a má tedy tento seznam prázdný, takže při iteraci mám jen jeden if navíc. |
| | Zatím se mi tato implementace líbí nejvíc. |
