Talk:Automatically trimming a monodix - Revision history

Unhammer: /* HFST: possible to overcome compound overgeneration? */

2014-06-20T14:47:41Z

HFST: possible to overcome compound overgeneration?

Unhammer: /* HFST: possible to overcome compound overgeneration? */

2014-06-15T07:21:04Z

HFST: possible to overcome compound overgeneration?

Unhammer: /* HFST: possible to overcome compound overgeneration? */

2014-06-14T21:55:03Z

HFST: possible to overcome compound overgeneration?

Francis Tyers: /* HFST: possible to overcome compound overgeneration? */

2014-05-22T11:33:05Z

HFST: possible to overcome compound overgeneration?

Unhammer at 11:19, 22 May 2014

2014-05-22T11:19:46Z

Unhammer: /* HFST: possible to overcome compound overgeneration? */ new section

2014-05-22T09:48:19Z

HFST: possible to overcome compound overgeneration?: new section

Unhammer: /* Compounds vs trimming in HFST */

2014-02-11T08:41:50Z

Compounds vs trimming in HFST

Unhammer: /* Alternate implementation methods */

2014-02-11T08:36:29Z

Alternate implementation methods

Unhammer: /* Implementing automatic trimming in lttoolbox */

2014-02-11T08:36:15Z

Implementing automatic trimming in lttoolbox

Unhammer: /* + type multiwords */

2014-02-11T08:32:58Z

+ type multiwords

← Older revision		Revision as of 14:47, 20 June 2014
Line 27:		Line 27:

	Say we have the FST "bidix", can we create "<code>bidix [^+]* (+ bidix [^+])</code>" (where + is just the literal join symbol) and trim with that?		Say we have the FST "bidix", can we create "<code>bidix [^+]* (+ bidix [^+])</code>" (where + is just the literal join symbol) and trim with that?
			: seems to work!

← Older revision		Revision as of 07:21, 15 June 2014
Line 26:		Line 26:


	Say we have the FST "bidix" and the FST "tag", can we create "<code>bidix ~~tag~~ (+ bidix ~~tag~~)</code>" (where + is just the literal join symbol) and trim with that? ~~We'd just have to be able to exctract the tags from the lexc.~~		Say we have the FST "bidix", can we create "<code>bidix [^+]* (+ bidix [^+])</code>" (where + is just the literal join symbol) and trim with that?

@@ Line 3: / Line 3: @@
 Assuming we ''don't use flags'', we can compile an HFST transducer through [[ATT]] format to a working lttoolbox transducer.
-Now the issue is that compounds are plain transitions back into some lexicon, without the compound-only-L/compound-R tags, so even though lt-trim should trim them compounds correctly (by treating them like &lt;j/&gt; transitions), the resulting analyser will over-generate:
+Now the issue is that compounds are plain transitions back into some lexicon, without the compound-only-L/compound-R tags, so even though lt-trim should trim the compounds correctly (by treating them like &lt;j/&gt; transitions), the resulting analyser will over-generate:
 <pre>jīvitarēkha/jīvitarēkha<n><sg><nom>/jīvitaṁ<n><cmp>+rēkha<n><sg><nom></pre>
@@ Line 24: / Line 24: @@
 ::This is also an option, while we were at it I'd choose a prettier couple of symbols though ;) - [[User:Francis Tyers|Francis Tyers]] ([[User talk:Francis Tyers|talk]]) 13:33, 22 May 2014 (CEST)
+Say we have the FST "bidix" and the FST "tag*", can we create "<code>bidix tag* (+ bidix tag*)*</code>" (where + is just the literal join symbol) and trim with that? We'd just have to be able to exctract the tags from the lexc.

@@ Line 19: / Line 19: @@
 Note: this compounding method won't let you do stuff like "only allow adj adj or noun noun compounds" like you can in HFST.
+::You can do that in the morphotactics though (e.g. adjective paradigms only redirect to the adjectivestem lexicon.) - [[User:Francis Tyers|Francis Tyers]] ([[User talk:Francis Tyers|talk]]) 13:33, 22 May 2014 (CEST)
 : Uh, what happens if you simply specify compound-R and compound-only-L tags in the lexc?
+::This is also an option, while we were at it I'd choose a prettier couple of symbols though ;) - [[User:Francis Tyers|Francis Tyers]] ([[User talk:Francis Tyers|talk]]) 13:33, 22 May 2014 (CEST)

← Older revision		Revision as of 11:19, 22 May 2014
Line 18:		Line 18:

	Note: this compounding method won't let you do stuff like "only allow adj adj or noun noun compounds" like you can in HFST.		Note: this compounding method won't let you do stuff like "only allow adj adj or noun noun compounds" like you can in HFST.


			: Uh, what happens if you simply specify compound-R and compound-only-L tags in the lexc?

@@ Line 1: / Line 1: @@
+== HFST: possible to overcome compound overgeneration? ==
+Assuming we ''don't use flags'', we can compile an HFST transducer through [[ATT]] format to a working lttoolbox transducer.
+Now the issue is that compounds are plain transitions back into some lexicon, without the compound-only-L/compound-R tags, so even though lt-trim should trim them compounds correctly (by treating them like &lt;j/&gt; transitions), the resulting analyser will over-generate:
+<pre>jīvitarēkha/jīvitarēkha<n><sg><nom>/jīvitaṁ<n><cmp>+rēkha<n><sg><nom></pre>
+Ie. we will get non-lexicalised compound analyses along with the lexicalised ones.
+One way to overcome this is to first compile the analyser from the ATT, then:
+* go through it building a new version, but on seeing a +, we:
+** replace the transition with a single compound-only-L tag transitioning into final state
+** let partial=copy_until_final(the_plus_transition) and make a transition from start into partial, and we connect the final state of partial with a single tag compound-R into the final state of our new FST
+If the function copy_until_final sees a +, that transition is discarded, but a compound-only-L tag is added.
+Note: this compounding method won't let you do stuff like "only allow adj adj or noun noun compounds" like you can in HFST.

@@ Line 1: / Line 1: @@
-== Compounds vs trimming in HFST ==
-The sme.lexc can't be trimmed using the simple HFST trick, due to compounds.
-Say you have '''cake n sg''', '''cake n pl''', '''beer n pl''' and '''beer n sg''' in monodix, while bidix has '''beer n''' and '''wine n'''. The HFST method without compounding is to intersect '''(cake|beer) n (sg|pl)''' with '''(beer|wine) n .*''' to get '''beer n (sg|pl)'''.
-But HFST represents compounding as a transition from the end of the singular noun to the beginning of the (noun) transducer, so a compounding HFST actually looks like
-: '''((cake|beer) n sg)*(cake|beer) n (sg|pl)'''
-The intersection of this with
-: '''(beer|wine) n .*'''
-is
-: '''(beer n sg)*(cake|beer) n (sg|pl) | beer n pl'''
-when it should have been
-: '''(beer n sg)*(beer n (sg|pl)'''
-Lttoolbox doesn't represent compounding by extra circular transitions, but instead by a special restart symbol interpreted while analysing.
-lt-trim is able to understand compounds by simply skipping the compund tags

@@ Line 1: / Line 1: @@
-==Alternate implementation methods==
-Trimming while reading the XML file might have lower memory usage (who knows, untested), but seems like more work, since pardefs are read and turned into FST's before we get to an "initial" state and then attached at the end of regular entries.
-[[Image:Product-automaton-intersection.png|thumb|400px|right|product automaton for intersection]]
-The '''product automaton''' for intersection, marks as final only state-pairs where both parts of the state-pair are final in the original automata. Minimisation removes unreachable state-pairs. However, this quickly blows up in memory usage since it creates ''all'' possible state pairs first (cartesian product), not just the useful ones.
-https://github.com/unhammer/lttoolbox/branches has some experiments, see e.g. branches product-intersection and df-intersection (the latter is the currently used implementation)
-<br clear="all" />
 == Compounds vs trimming in HFST ==

@@ Line 1: / Line 1: @@
+==Alternate implementation methods==
-==Implementing automatic trimming in lttoolbox==
+Trimming while reading the XML file might have lower memory usage (who knows, untested), but seems like more work, since pardefs are read and turned into FST's before we get to an "initial" state and then attached at the end of regular entries.
-The current method: compile the analyser in the normal way, then lt-trim loads it and loops through all its states, trying to do the same steps in parallel with the compiled bidix:
-<pre>
-trim(current_a, current_b):
-  for symbol, next_a in analyser.transitions[current_a]:
-    found = false
-    for s, next_b in bidix.transitions[current_b]:
-      if s==symbol:
-         trim(next_a, next_b)
-         found = true
-    if seen tags:
-      found = true
-    if !found && !current_b.isFinal():
-      delete symbol from analyser.transitions[current_a]
-    // else: all transitions from this point on will just be carried over unchanged by bidix
-trim(analyser.initial, bidix.initial)
-</pre>
 [[Image:Product-automaton-intersection.png|thumb|400px|right|product automaton for intersection]]
+The '''product automaton''' for intersection, marks as final only state-pairs where both parts of the state-pair are final in the original automata. Minimisation removes unreachable state-pairs. However, this quickly blows up in memory usage since it creates ''all'' possible state pairs first (cartesian product), not just the useful ones.
+https://github.com/unhammer/lttoolbox/branches has some experiments, see e.g. branches product-intersection and df-intersection (the latter is the currently used implementation)
-Trimming while reading the XML file might have lower memory usage, but seems like more work, since pardefs are read before we get to an "initial" state.
-A slightly different approach is to create the '''product automaton''' for intersection, marking as final only state-pairs where both parts of the state-pair are final in the original automata. Minimisation should remove unreachable state-pairs. However, this quickly blows up in memory usage since it creates ''all'' possible state pairs first (cartesian product), not just the useful ones.
-https://github.com/unhammer/lttoolbox/branches has some experiments, see e.g. branches product-intersection and df-intersection
 <br clear="all" />
-===TODO===
-* Would it make things faster if we first clear out the right-sides of the bidix and minimize that?
-* remove all those ifdef DEBUG's and wcerr's
-* more tests?
-* if no objections: git svn dcommit
 == Compounds vs trimming in HFST ==

@@ Line 39: / Line 39: @@
 * more tests?
 * if no objections: git svn dcommit
-== + type multiwords ==
-join (&lt;j&gt;) is handled by setting the next trimmer (bidix) target state to be trimmer.initial, so we simply skip to the start.
-=== + and # together ===
-''However'', if we have a + followed by a # in monodix, we need to get back to where we were after reading the + part. An example:
-<pre>monodix, one entry:
-foo<n><ind>+bar<pr># fie
-bidix, two entries:
-foo# fie<n>
-bar<pr>
-preprocessed (prefixed+lemq-moved) bidix, two entries:
-foo<n>[<n>|<ind>|<pr>]*# fie
-bar<pr>[<n>|<ind>|<pr>]*
-</pre>
-We start by matching on these paths: <pre>
-monodix string  foo<n><ind> + bar<pr> # fie
-monodix states g           i j       k
-  bidix string  foo<n>[<n>|<ind>|<pr>]* # fie
-  bidix states l                       m
-</pre>
-and get as far as state pair (i,m), having consumed <pre>foo<n><ind></pre> before seeing a +.
-Now, the next SearchState records both the next monodix state (j, the state after +), the next bidix state (l, the bidix initial state), and the bidix state we were in when we saw the plus (m, at the end of the bidix tag list). So in the code SearchState next = (this_trg, trimmer.initial, trimmer_src).
-At (i,l,m) we've consumed <pre>foo<n><ind></pre> and have <pre>bar<pr># fie</pre> left, and can read from bidix initial l:<pre>
-monodix string  bar<pr> # fie
-monodix states j       k
-  bidix string  bar<n>[<n>|<ind>|<pr>]*
-  bidix states l                       n
-</pre>
-We match all of <pre>bar<pr></pre> and then see a # in monodix, giving SearchState (k,n,m). Since both the third part of SearchState is set to state m (where m!=n), and we've seen a #, we jump back to that state m, from where we can match <code># fie</code>, and we're done.
 == Compounds vs trimming in HFST ==