Repository: sinaahmadi/klpt (language: python)

Issue:
Some words aren't analysed, although they are in Apertium
Output of Python analyser:
```
('dixwî', [[]])
```
Output of Apertium:
```bash
$ echo dixwî | apertium -d ~/source/apertium/languages/apertium-kmr/ kmr-morph
^dixwî/xwarin<vblex><tv><pri><p2><sg>$
```
I will look into this. Feel free to assign it to me.


Discussion / hints:
Just noticed it, Francis. 
Sure. I assigned it to you. Please consider adding such cases to [test_stem.py](https://github.com/sinaahmadi/klpt/blob/master/tests/test_stem.py). 
Thanks!
It seems to be to do with sequences of epsilons:
```bash
fran@ipek:~/source/klpt$ hfst-txt2fst klpt/data/kmr-analyser.att | hfst-fst2strings -e '0' | grep "d0*i0*x0*w0*î"
dixw00000î00:xwarin<vblex><tv><pri><p2><sg>0
```
I see.
Do you think it has something to do with [`att_analyzer.py`](https://github.com/sinaahmadi/klpt/blob/master/klpt/att_analyze.py)? We can try with [this one](https://github.com/mhulden/foma/blob/master/foma/python/attapply.py) as you suggested before.
Yep, it's definitely in there, I'll try and play around a bit more and if I can't get it to work we can try the one that Måns wrote :)

Fix patch:
diff --git a/klpt/att_analyze.py b/klpt/att_analyze.py
index 39b3ed0..e09f51f 100644
--- a/klpt/att_analyze.py
+++ b/klpt/att_analyze.py
@@ -1,135 +1,182 @@
-#!/usr/bin/env python
 # -*- coding: utf-8 -*-
 
+"""
+Utility for reading .att format automata and transducers and doing apply up or down,
+written in Python.  Also supports weighted FSMs.  In the weighted case the apply routines
+return the strings in order cheapest first.  The apply functions work as a generator,
+yielding output strings as long as there is a valid transduction.  Input files are
+standard AT&T format, with the last column being optionally a weight.  The files can be
+compressed with gzip.  The apply generator produces tuples of (output, weight). For
+unweighted automata/transducers, the weight is always 0.0.
+
+Example usage:
+
+>>> import attapply
+>>> t = attapply.ATTFST('spanish.att.gz')  # Spanish morphological analyzer
+>>> list(t.apply(u'tuviera', dir = 'up'))  # Analyze
+[(u'tener[Subj][Imp][Form1][1P][Sg]', 0.0), (u'tener[Subj][Imp][Form1][3P][Sg]', 0.0)]
+
+>>> list(t.apply('tener[Subj][Imp][Form1][1P][Sg]')) # Generate, default dir is 'down'
+[(u'tuviera', 0.0)]
+
+Author: Mans Hulden
+License: Apache (Version 2.0)
+Last Update: 11/07/2016
+"""
+
 import json
 import sys
 import re
 sys.path.append('../klpt')
 import klpt
 
-class Analysis:
-    """
-    Utility for reading .att format automata and transducers from the Apertium project. Particuarly used to integrate the [Kurmanji part](https://github.com/apertium/apertium-kmr) in KLPT
+import codecs, gzip
+from heapq import *
 
-    Returns:
-        [str]: [output of the Apertium morphological analyzer]
-    """
-    
+class State:
+    def __init__(self):
+        self.final = False
+        self.finalweight = 0.0
+        self.transitionsin = {}
+        self.transitionsout = {}
 
-    def __init__(self, dialect="Kurmanji", script="Latin"):
+    def add_transition(self, target, input, output, weight):
+        if input not in self.transitionsin:
+            self.transitionsin[input] = []
+        if output not in self.transitionsout:
+            self.transitionsout[output] = []
+        self.transitionsin[input].append((output, target, weight))
+        self.transitionsout[output].append((input, target, weight))
+
+    def get_transitions(self, symbol, dir = 'down'):
+        if dir == 'down':
+            s = self.transitionsin
+        else:
+            s = self.transitionsout
+        if symbol in s:
+            return s[symbol]
+        else:
+            return []
+
+    def set_final(self, finalweight):
+        self.final = True
+        self.finalweight = finalweight
+
+class ATTFST:
 
-        self.eps = '@0@'
-        self.initial_state = 0;
-        self.accepting_states = set(); # finals
-        self.states = set()
-        self.transitions = {}
+    def __init__(self, attfile, epsilon_symbol = u'@0@', identity_symbol = u'@_IDENTITY_SYMBOL_@', unknown_symbol = '@_UNKNOWN_SYMBOL_@'):
+
+        """Reads an AT&T file (possibly gzipped) and inits data structures
+        to apply() can be called.  If the AT&T file contains the special symbols
+        epsilon, identity (repeat unknown) or unknown (one-sided unknown), these
+        can be specified. The defaults are what foma produces with write att."""
+
+        self.epsilon_symbol = epsilon_symbol
+        self.identity_symbol = identity_symbol
+        self.unknown_symbol = unknown_symbol
+        try:
+            lines = [line.rstrip('\n') for line in codecs.getreader('utf-8')(gzip.open(attfile), errors='replace')]
+        except:
+            lines = [line.rstrip('\n') for line in codecs.open(attfile, "r", encoding="utf-8")]
+        self.states = {}
         self.alphabet = set()
-        
-        # validate parameters
-        if dialect == "Kurmanji" and script == "Latin":
-            with open(klpt.get_data("data/kmr-Latn.att")) as analysis_file:
-                self.load(analysis_file)
+        for l in lines:
+            fields = l.split('\t')
+            if len(fields) > 3:
+                fields = l.split('\t')
+                source = int(fields[0])
+                target = int(fields[1])
+                insym = self._map_syms(fields[2])
+                outsym = self._map_syms(fields[3])
+                if len(fields) > 4:
+                    weight = float(fields[4])
+                else:
+                    weight = 0.0
+                self.alphabet.add(insym)
+                self.alphabet.add(outsym)
+                if int(source) not in self.states:
+                    nss = State()
+                    self.states[source] = nss
+                if int(target) not in self.states:
+                    nst = State()
+                    self.states[target] = nst
+                self.states[source].add_transition(target, insym, outsym, weight)
+            elif len(fields) < 3 and len(fields) > 0:
+                final = int(fields[0])
+                finalweight = 0.0
+                if len(fields) > 1:
+                    finalweight = float(fields[1])
+                if final not in self.states:
+                    nss = State()
+                    self.states[final] = nss
+                self.states[final].set_final(finalweight)
+
+    def _map_syms(self, s):
+        if s == self.epsilon_symbol:
+            return u''
+        return s
+
+    def tokenize(self, word):
+        tokens = []
+        start = 0
+        while start < len(word):
+            t = word[start]
+            for length in range(1, len(word) - start + 1):
+                if word[start:start+length] in self.alphabet:
+                    t = word[start:start+length]
+            tokens.append(t)
+            start += len(t)
+        return tokens
+
+    def apply(self, word, dir = 'down', tokenizer = None, return_joined = True):
+
+        """Main apply function. Tokenizer func can be passed to the function.
+        If no tokenizer is given, the alphabet of the FSM is used for
+        tokenization of the input string, longest-match (as in foma).
+        By default, the dir = 'down'. The output is by default joined,
+        but a list of tokens can also be produced if return_joined is
+        False."""
+
+        if tokenizer == None:
+            w = self.tokenize(word)
         else:
-            raise Exception("dialect not supported")
-        # elif dialect == "Sorani":
-        #     with open(klpt.get_data("data/ckb-analyser.att")) as analysis_file:
-        #         self.load(analysis_file)
-    
-    def load(self, analysis_file):
-        for line in analysis_file.readlines():
-            row = line.strip('\n\t').split('\t') 
-            if len(row) == 2:
-                self.accepting_states.add(int(row[0]))
-                self.states.add(int(row[0]))
-                #print(row)
-            elif len(row) == 5:
-                i_state = int(row[0])
-                o_state = int(row[1])
-                self.states.add(i_state)
-                self.states.add(o_state)
-                i_sym = row[2]
-                o_sym = row[3]                
-                self.alphabet.add(i_sym)
-                self.alphabet.add(o_sym)
-                if (i_state, i_sym) not in self.transitions:
-                    self.transitions[(i_state, i_sym)] = []
-                self.transitions[(i_state, i_sym)].append((o_sym, o_state))
-    
-    def closure(self, S, reached_states):    # Calculate epsilon closure over state S
-    
-        if S not in self.state_output_pairs:
-            self.state_output_pairs[S] = set();
-    
-        if (S, self.eps) in self.transitions:
-            for state in self.transitions[(S, self.eps)]:
-                reached_states.add(state[1]);
-    
-                if state[1] not in self.state_output_pairs:
-                    self.state_output_pairs[state[1]] = set();
-    
-                for pair in self.state_output_pairs[S]:
-                    if state[0] == self.eps:
-                        self.state_output_pairs[state[1]].add((pair[0], state[1]));
-                    else: 
-                        self.state_output_pairs[state[1]].add((pair[0] + state[0], state[1]));
-    
-                self.closure(state[1], reached_states);
-    
-        return reached_states;
-    
-    def step(self, S, c):            # Step the transducer
-        reached_states = set();
-    
-#        if S in self.accepting_states:
-#            return set([S]);
-    
-        if (S, c) in self.transitions: 
-            for state in self.transitions[(S, c)]:
-                self.closure(state[1], reached_states);
-                reached_states.add(state[1]);
-    
-                if state[1] not in self.state_output_pairs:
-                    self.state_output_pairs[state[1]] = set();
-    
-                for pair in self.state_output_pairs[S]:
-                    if state[0] == self.eps:
-                        self.state_output_pairs[state[1]].add((pair[0], state[1]));
-                    else: 
-                        self.state_output_pairs[state[1]].add((pair[0] + state[0], state[1]));
-    
-                self.closure(state[1], reached_states);
-    
-        return reached_states;
+            w = tokenizer(word)
+        heap = []
+        heappush(heap, (0.0, 0, [], 0, False)) # (cost, -pos, output, state, final_included), use negpos to serve as tiebreaker
+        while len(heap) > 0:
+            cost, negpos, output, state, final_included = heappop(heap)
+            if final_included == True:
+                if return_joined == True:
+                    yield(''.join(output), cost)
+                else:
+                    yield(output, cost)
+            else:
+                if -negpos == len(w):
+                    # only match epsilon or finaladd
+                    if final_included == False:
+                        for outsym, target, weight in self.states[state].get_transitions('', dir = dir):
+                            heappush(heap, (cost + weight, negpos, output + [outsym], target, False))
+                    if self.states[state].final == True:
+                        heappush(heap, (cost + self.states[state].finalweight, negpos, output, state, True))
+                else: # Match other symbols as well
+                    nextsym = [w[-negpos]]
+                    if w[-negpos] not in self.alphabet:
+                        nextsym = [self.unknown_symbol, self.identity_symbol]
+                    for ns in nextsym:
+                        for outsym, target, weight in self.states[state].get_transitions(ns, dir = dir):
+                            if outsym == self.identity_symbol:
+                                outsym = w[-negpos]
+                            elif outsym == self.unknown_symbol:
+                                outsym = u'?'
+                            heappush(heap, (cost + weight, negpos - 1, output + [outsym], target, False))
+                    for outsym, target, weight in self.states[state].get_transitions('', dir = dir): # Epsilons
+                        heappush(heap, (cost + weight, negpos, output + [outsym], target, False))
+
+
+class Analysis:
+    def __init__(self, dialect="Kurmanji", script="Latin"):
+        self.t = ATTFST(klpt.get_data("data/kmr-Latn.att"))
 
     def analyze(self, word):
-        self.state_output_pairs = {};           # A structure to contain the list of "alive state-output pairs" 
-        self.state_output_pairs[0] = set([(self.eps, 0)]); 
-        self.accepting_output_pairs = set();    # The set of state-output pairs that are accepting
-        self.current_states = set([self.initial_state]); # Set containing the set of current states
-        i = 0
-        while True:            # Loop until no input remains
-            reached_states = set()
-            if i == len(word):
-                for state in self.current_states:
-                    reached_states = self.closure(state, reached_states)
-                    del self.state_output_pairs[state]
-                break
-            #print(i, word[i], self.current_states, self.state_output_pairs) 
-            for state in self.current_states:
-                if state not in self.state_output_pairs:
-                    self.state_output_pairs[state] = set();
-                reached_states = reached_states.union(self.step(state, word[i]))
-                del self.state_output_pairs[state]
-        
-            self.current_states = reached_states;
-            i += 1
- 
-        accepting_output_pairs = []
-        for state in self.state_output_pairs:
-            #print(state, self.accepting_states, self.state_output_pairs[state])
-            if state in self.accepting_states:
-                accepting_output_pairs.append(list(self.state_output_pairs[state]))
-        
-       
-        return (word, accepting_output_pairs)
+        return list(self.t.apply(word, dir='down'))
 


Test patch:
diff --git a/klpt/data/test_cases_stem.json b/klpt/data/test_cases_stem.json
index 4db569c..b614730 100644
--- a/klpt/data/test_cases_stem.json
+++ b/klpt/data/test_cases_stem.json
@@ -42,6 +42,7 @@
                 "xêzikine": [{"base": "xêzik", "description": "n_f_pl_con_ind", "pos": "", "terminal_suffix": "", "formation": ""}],
                 "bêje": [],
                 "dibêjim": [{"base": "gotin", "description": "vblex_tv_pri_p1_sg", "pos": "", "terminal_suffix": "", "formation": ""}],
+                "dixwî": [{"base": "xwarin", "description": "vblex_tv_pri_p2_sg", "pos": "", "terminal_suffix": "", "formation": ""}],
                 "nonesense": []
             },
             "Arabic": {}
diff --git a/tests/test_stem.py b/tests/test_stem.py
index cd2ff0f..dc3e176 100644
--- a/tests/test_stem.py
+++ b/tests/test_stem.py
@@ -42,4 +42,4 @@ def test_analyze(self):
                     pass
 
 if __name__ == "__main__":
-    unittest.main()
\ No newline at end of file
+    unittest.main()