[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki

• ÚFAL Wiki Home
• ÚFAL Home
• Sitemap
• RSS
• ÚFAL calendar
• Recent changes
• Login
• Hledat:

[ Back to the navigation ]

Differences

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

View differences: Side by SideInline Go

Link to this comparison view

Both sides previous revision Previous revision 2012/09/27 11:22 ufal 2012/09/27 11:21 ufal 2012/09/27 11:20 ufal 2012/09/27 11:17 ufal 2012/09/27 11:15 ufal 2012/09/27 11:12 ufal 2012/09/27 11:09 ufal 2012/09/27 11:03 ufal 2012/09/27 10:58 ufal 2012/09/27 10:54 ufal 2012/09/27 10:39 ufal 2012/09/27 10:36 ufal 2012/09/27 10:14 ufal 2012/09/27 09:41 ufal 2012/09/27 09:31 ufal 2012/09/26 13:57 ufal 2012/09/26 13:56 ufal 2012/09/26 13:49 ufal 2012/09/26 13:46 ufal vytvořeno Go Next revision		Previous revision 2012/09/27 11:22 ufal 2012/09/27 11:21 ufal 2012/09/27 11:20 ufal 2012/09/27 11:17 ufal 2012/09/27 11:15 ufal 2012/09/27 11:12 ufal 2012/09/27 11:09 ufal 2012/09/27 11:03 ufal 2012/09/27 10:58 ufal 2012/09/27 10:54 ufal 2012/09/27 10:39 ufal 2012/09/27 10:36 ufal 2012/09/27 10:14 ufal 2012/09/27 09:41 ufal 2012/09/27 09:31 ufal 2012/09/26 13:57 ufal 2012/09/26 13:56 ufal 2012/09/26 13:49 ufal 2012/09/26 13:46 ufal vytvořeno Go Next revision Both sides next revision
courses:rg:2011-report-parser [2012/09/27 10:36] ufal		courses:rg:2011-report-parser [2012/09/27 10:54] ufal
Line 37:		Line 37:
	==== Parser ====		==== Parser ====
-	* we illustrated a step of the 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 ]