Differences

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

--- courses:rg:2011-report-parser [2012/09/27 09:41]
ufal
+++ courses:rg:2011-report-parser [2012/09/27 10:54]
ufal
@@ Line 23: / Line 23: @@
     * their scheme is based on the Stanford's dependency labels
+==== Conversion process ====
+  * converting phrase trees of Penn Treebank to dependency ones
+  * it consists of 3 steps:
+      - add structure to flat NPs
+      - constituent-to-dependency converter with some head-finding rule modifications
+          * a list of rules in Figure 2 is hardly understandable without reading a paper their conversion method is related to
+          * they reduced the number of generic "dep/DEP" relation
+              * Stanford tags are hierarchical and "dep/DEP" is the top-most one
+          * 1.3% of arcs are non-projective (out of 8.1% of all non-projective arcs) because of the following conversion (agreement can be a motivation for this, i.e. in Czech):
+            {{:courses:rg:dependency-conversion.png|}}
+==== Parser ====
+  * we illustrated a step of the parser:
+{{:courses:rg:ndef_parsing.png|}}
+  * we compared time complexity of this system with other commonly used ones
+| MST parser | <latex>\mathop O(n^2)</latex> | |
+| MALT parser | <latex>\mathop O(n)</latex> | in fact slower |
+| this parser | <latex>\mathop O(n\log(n))</latex> | <latex>\mathop O(n^2)</latex> - naive implementation |
+| this parser - non-projective | <latex>\mathop O(n^2\log(n))</latex> | <latex>\mathop O(n^3)</latex> - naive implementation |
+   * implemented by a heap, it can reach <latex>\mathop O(n\log(n))</latex>; however, they don't use it because it's fast enough

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

Institute of Formal and Applied Linguistics Wiki

Differences