Differences

This shows you the differences between two versions of the page.

--- treex:api-implementation [2015/12/14 03:43]
popel
+++ treex:api-implementation [2015/12/15 16:25]
popel
@@ Line 1: / Line 1: @@
-==== Uložení uzlů ====
+===== Uložení uzlů =====
 [[https://github.com/ufal/parsito/tree/master/src/tree|Parsito]] používá ''vector<node> nodes;'' a pak ''nodes.emplace_back(nodes.size(), form);''.
@@ Line 10: / Line 10: @@
 Přijde mi tedy výhodnější ukládat rovnou referenci na daný uzel (než int, který by se musel měnit, pokud bych přidal uzly na začátek věty).
-=== Sdílení klíčů ===
+==== Sdílení klíčů ====
 V Perlu a Pythonu jsou objekty implementovány jako hash table. Má-li třída Node atributy form, lemma,... a chceme milion uzlů, bylo by vhodné neukládat řetězce "form", "lemma",... do každé instance. V Perlu jsou naštěstí klíče všech hashů sdílené (stále je zde ale nějaká režie za hash, která by se odstranila použitím array-based objektů a vytvořením hashe pouze pro "wild" atributy). V Pythonu je potřeba použít [[http://tech.oyster.com/save-ram-with-python-slots/|__slots__]] nebo [[https://www.python.org/dev/peps/pep-0412/|Python > 3.3]] nebo dědit od [[https://github.com/nucleic/atom|Atom]] nebo namedtuple.
-=== Sdílení hodnot ===
+==== Sdílení hodnot ====
 Mnoho uzlů má stejné lemma, formu, formém, tag atd.
@@ Line 45: / Line 45: @@
-==== Benchmark Perlích accessorů ====
+===== Benchmark Perlích accessorů =====
 Nejdřív jsem porovnal různé implementace a měřil kolikrát za sekundu se provede zápis následovaný čtením (stejného) atributu. H=hash-based object. A=array-based object. LV=lvalue (viz níže).
   LV V::Magic H         64 759/s
@@ Line 120: / Line 120: @@
     * Na druhou stranu je otázka, zda se podaří zrychlit zbytek Treexu natolik, aby se projevil rozdíl v řádu 200 **nano**sekund na čtení jednoho atributu (pesimisticky předpokládejme, že všechny atributy mají kontrolovaný/logovaný zápis, což snad nebude pravda). Odhaduji, že na parsing (plus tagging, nebo načtení z CoNLL-U) jedné věty (20 slov) potřebuji číst tak 1000 krát číst a 100 krát zapsat nějaký atribut, tedy s lvalue ztratím 200 **mikro**sekund. Přitom samotný parsing trvá aspoň několik **mili**sekund.
-==== Identifikátory ====
+===== Identifikátory =====
 V dosavadním Treexu byly identifikátory (uzlů) považovány za nevyhnutelnou režii a byly zpracovávány (generovány, indexovány) automaticky. Je otázka, jestli je to opravdu nutné za všech okolností, popř. jestli by to nešlo nějak zjednodušit, když víme, že valná část bloků identifikátory uzlů k ničemu nepotřebuje, navíc drtivá většina referencí je uzavřených uvnitř bundlu. Pokud se podaří sloučit a-stromy a t-stromy, velká část referencí odpadne, zbývající případy budou souviset asi hlavně s alignmentem a koreferencí.
@@ Line 138: / Line 138: @@
-==== Setřídění dle ord ====
+===== 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.
@@ Line 161: / Line 161: @@
 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.
+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.
-Zatím se mi tato implementace líbí nejvíc.
+Vylepšení1:
+Při zavolání z kořene stromu by se vrátil speciální iterátor, který vůbec nekontroluje seznamy neprojektivit (takže se ušetří to if, ale hlavně procházení všech seznamů). Toto vylepšení mi přijde zcela jasně přínosné.
+Vylepšení2:
+V seznamech neprojektivit budou uzly setříděné vzestupně dle hloubky. Jakmile narazím na uzel s vyšší hloubkou než uzel, který testuji (ze kterého jsou ''descendants'' zavolané), tak skončím a neprocházím zbytek seznamu. Zde si vůbec nejsem jist, zda to má cenu, protože sice ušetřím procházení části seznamu u některých uzlů, jenže zase přibude testování hloubky (kterou bych musel mít v tom seznamu asi předpočítanou, a tedy ji aktualizovat, když se změní).
+Alternativa: atribut _leftmost (a obdobně _rightmost) by se vyplňoval pouze tehdy, pokud by se sledováním nejlevějšího dítěte nedalo dostat do nejlevějšího potomka. Tedy v projektivních stromech by se ty atributy nemusely vyplňovat vůbec (vůbec by nezabíraly místo v hash-based objektech). Editace by pak mohly být o něco rychlejší, pokud detekuji, že projektivní strom měním na projektivní. Čtení ale bude pomalejší, protože budu muset iterovat do těch nejlevějších dětí (a ještě navíc testovat, zda není v uzlech vyplněn _leftmost).

[ Back to the navigation ] [ Back to the content ]

Institute of Formal and Applied Linguistics Wiki

Differences