User:David Nemeskey/GSOC progress 2013 - Revision history

David Nemeskey: /* Size problems */

2013-10-29T16:27:45Z

Size problems

David Nemeskey: /* Size problems */

2013-10-29T15:08:08Z

Size problems

David Nemeskey: /* Size problems */

2013-10-29T14:29:29Z

Size problems

David Nemeskey: /* Size problems */

2013-10-29T09:52:11Z

Size problems

David Nemeskey at 09:51, 29 October 2013

2013-10-29T09:51:30Z

David Nemeskey: /* Hacky hacks */

2013-09-27T09:40:14Z

Hacky hacks

David Nemeskey: /* Size problems */

2013-09-27T07:58:14Z

Size problems

David Nemeskey: /* Size problems */

2013-09-26T12:10:21Z

Size problems

David Nemeskey: /* Size problems */

2013-09-26T12:09:54Z

Size problems

David Nemeskey: /* Size problems */

2013-09-26T12:06:04Z

Size problems

@@ Line 493: / Line 493: @@
 |-
 |apertium-sme-fin.fin-sme_cg2_l1.fst
-|23.1%
+|21%
 |4.1%
-|82.25%
+|80.47%
 |-
 |apertium-sme-fin.fin-sme_cg2_l2.fst
-|31.4%
+|32.3%
+|8.9%
-|??? (core dump)
+|72.44%
-|N/A
 |}
 </div>

@@ Line 491: / Line 491: @@
 |1.5%
 |28.57%
+|-
+|apertium-sme-fin.fin-sme_cg2_l1.fst
+|23.1%
+|4.1%
+|82.25%
+|-
+|apertium-sme-fin.fin-sme_cg2_l2.fst
+|31.4%
+|??? (core dump)
+|N/A
 |}
 </div>

@@ Line 456: / Line 456: @@
 ### There is a possibility that this change might make the rules more complicated; still, we should try it.
 ## It is not necessary to save all FSAs to disk. In case of a full binary tree with three levels, nodes 3, 5 and 7 (BFS ordering) are superfluous: if node 1 matches the sentence, but node 2 does not, it is obvious that node 3 would, and so on. The rule applier has already been built with this idea in mind, but the redundant trees are still save to file and read into memory.
-# Delete the sigma tries from the condition automata and rules.
+# <span style="color:#009000">''Delete the sigma tries from the condition automata and rules.''</span>
-## See table 6. for results on some of the rule sets. It is obvious from the data that the reduction is greater for rule sets where the condition trees are shallow; as the conditions are merged, the growth in the number of states and transitions becomes more substantial -- in the extreme case the sigma of a joined condition might not grow at all, but the size of the state space always does considerably.
+## <span style="color:#009000">''See table 6. for results on some of the rule sets. It is obvious from the data that the reduction is greater for rule sets where the condition trees are shallow; as the conditions are merged, the growth in the number of states and transitions becomes more substantial -- in the extreme case the sigma of a joined condition might not grow at all, but the size of the state space always does considerably.''</span>
 <div align="center">

@@ Line 476: / Line 476: @@
 |4.4%
 |54.16%
+|-
-|grammars/apertium-br-fr.br-fr_cg2_l1.fst
+|apertium-br-fr.br-fr_cg2_l1.fst
 |5.1%
 |1.3%

@@ Line 456: / Line 456: @@
 ### There is a possibility that this change might make the rules more complicated; still, we should try it.
 ## It is not necessary to save all FSAs to disk. In case of a full binary tree with three levels, nodes 3, 5 and 7 (BFS ordering) are superfluous: if node 1 matches the sentence, but node 2 does not, it is obvious that node 3 would, and so on. The rule applier has already been built with this idea in mind, but the redundant trees are still save to file and read into memory.
+# Delete the sigma tries from the condition automata and rules.
+## See table 6. for results on some of the rule sets. It is obvious from the data that the reduction is greater for rule sets where the condition trees are shallow; as the conditions are merged, the growth in the number of states and transitions becomes more substantial -- in the extreme case the sigma of a joined condition might not grow at all, but the size of the state space always does considerably.
+<div align="center">
+{| class="wikitable"
+|+ align="bottom" | ''Table 6. Improvements in memory usage due to removing the sigma trie from the condition and rule FSMs.<br>Memory consumption is measured as percentages of the 4GB system memory.''
+! Rule set
+! Before
+! After
+! Reduction
+|-
+|apertium-br-fr.br-fr_cg2_orig.fst
+|23.5%
+|17.8%
+|24.25%
+|-
+|apertium-br-fr.br-fr_cg2_l2.fst
+|9.6%
+|4.4%
+|54.16%
+|grammars/apertium-br-fr.br-fr_cg2_l1.fst
+|5.1%
+|1.3%
+|74.5%
+|-
+|hun_cg2_l1.fst
+|0.5%
+|0.1%
+|80%
+|-
+|hun_cg2_l3.fst
+|2.1%
+|1.5%
+|28.57%
+|}
+</div>
 ==== TODO?'s ====

@@ Line 413: / Line 413: @@
 |-
 |Hungarian
-|6.5MB
+|7.1MB
 |0.721s
 |0.238s
-|7.1MB
+|6.5MB
 |0.658s
 |0.232s

@@ Line 445: / Line 445: @@
 ### Huet reports huge savings; for example, the Sanskrit morphological analyser, an FSA of 200,000 states, could be represented by a trie of 7,500 nodes.
 ### Then again, FSAs derived from word lists have a structure that gives them naturally to tries. Whether the method fares similarly well on generic FSAs is yet to be seen.
+## Implementation
+### <span style="color:#009000">''I have translated the caml code to Python. If it seems promising, I'll be rewriting it in C++.''</span>
 ## Evaluation
-### I fed the vocabulary of the Longman dictionary (more specifically, the strangely short variant that we have) to it. From the 47,051 tokens (words, numbers, g@rb@ge), the trie builder built a raw trie (with only forward sharing) of 150,222 nodes. Running the sharing algorithm (2/p9) on it reduced the number of nodes to 42,540 -- a 71.68% percent reduction.
+### <span style="color:#009000">''I fed the vocabulary of the Longman dictionary (more specifically, the strangely short variant that we have) to it. From the 47,051 tokens (words, numbers, g@rb@ge), the trie builder built a raw trie (with only forward sharing) of 150,222 nodes. Running the sharing algorithm (2/p9) on it reduced the number of nodes to 42,540 -- a 71.68% percent reduction.''</span>
-### Of course, due to how the trie is built (there is an empty node at the end of each path), about 47050 of those nodes are trivial to merge; this decreases the reduction to a more humble '''58.77%'''.
+### <span style="color:#009000">''Of course, due to how the trie is built (there is an empty node at the end of each path), about 47050 of those nodes are trivial to merge; this decreases the reduction to a more humble '''58.77%'''.''</span>
-### Collapsing nonaccepting, nonbranching trie paths (not described in the papers) results in a further reduction of '''54.8%''', bringing down the number of nodes to 19,213. However, I don't see a way to decrease this number further, and the compression level is not nearly the same as the one reported for the Sanskrit analyzer.
+### <span style="color:#009000">''Collapsing nonaccepting, nonbranching trie paths (not described in the papers) results in a further reduction of '''54.8%''', bringing down the number of nodes to 19,213. However, I don't see a way to decrease this number further, and the compression level is not nearly the same as the one reported for the Sanskrit analyzer.''</span>
-### At the same time, foma creates an 42,540-state automaton from the same word list, which hints at the not very surprising fact that "sharing" is basically the same as minimising a deterministic automaton. As such, the only advantage AM can boast of is that states can be collapsed, but I am not sure that we are better off, due to the additional bookkeeping required (sequence of letters on arcs).
+### <span style="color:#009000">''At the same time, foma creates an 42,540-state automaton from the same word list, which hints at the not very surprising fact that "sharing" is basically the same as minimising a deterministic automaton. As such, the only advantage AM can boast of is that states can be collapsed, but I am not sure that we are better off, due to the additional bookkeeping required (sequence of letters on arcs).''</span>
 # Decrease the alphabet
 ## We cannot hope for large savings from this one, but <code>| </code> seems to be completely superfluous: the end of a reading is clearly marked by the beginning of the next one (<code>#0# </code>) or the end of the cohort (<code>#EOC# </code>).
-## There is a possibility that this change might make the rules more complicated; still, we should try it.
+### There is a possibility that this change might make the rules more complicated; still, we should try it.
+## It is not necessary to save all FSAs to disk. In case of a full binary tree with three levels, nodes 3, 5 and 7 (BFS ordering) are superfluous: if node 1 matches the sentence, but node 2 does not, it is obvious that node 3 would, and so on. The rule applier has already been built with this idea in mind, but the redundant trees are still save to file and read into memory.
 ==== TODO?'s ====