Finite State Transducer

[BUXHO]

Hallo Leute,
ich würde mal gerne wissen wie man ein Finite State Transducer in Python programmieren kann.
Die vorhandene Daten z.B.:
Stamm1 : 'an'
SuffixeStamm1 : ['ua', 'oi', 'oin', 'oit', 'onj', 'onjsh', 'onjve', 'onjt'].

Im Internet habe einiges an Theorie gelesen (alles Theorie), aber das ganze in Python zu programmieren, habe ich keine Vorstellung. :K
Wie geht man vor?
Irgendein Code wäre super (wenn auch nur Anfang). Aber auch gerne Hinweise oder überhaupt Antwort.
Danke im Voraus

[BlackJack]

@BUXHO: Ein endlicher Transduktor ist einfach nur ein etwas modifizierter endlicher Automat. So etwas ist eigentlich recht einfach umzusetzen, allerdings braucht der dann ja auch wieder ein Programm in Form von Eingabe- und Ausgabealphabet und einer Beschreibung der Zustandsübergänge, welches er abarbeiten kann. Du musst da ja zwei Sachem programmieren -- einmal den Transduktor in Python, also so eine Art Prozessorsimulation. Und dann musst Du ein Programm für den Transduktor schreiben, der mit Deinen Daten das anstellt, was Du haben möchtest.

Ich sehe nicht so ganz was `Stamm1` und `SuffixeStamm1` sein sollen!? Du scheinst da schon eine konkrete Anwendung für einen Transduktor im Sinn zu haben, aber welche? Was bedeuten die Werte, die Du da zeigst?

[BUXHO]

Ein endlicher Transduktor ist einfach nur ein etwas modifizierter endlicher Automat.

Einfach?
Wie fängt man an? - um eine Vorstellung zu haben.

Ich sehe nicht so ganz was `Stamm1` und `SuffixeStamm1` sein sollen!? Du scheinst da schon eine konkrete Anwendung für einen Transduktor im Sinn zu haben, aber welche? Was bedeuten die Werte, die Du da zeigst?

Als Eingabe könnte man diesen Stamm1 (Stamm: 'an') und einen von den Stamm-Suffixen ['ua', 'oi', 'oin', 'oit', 'onj', 'onjsh', 'onjve', 'onjt'] z.B.: 'oit'; also das Wort: 'anoit'.
Alle Stämme sind mit Stamm1, Stamm2, Stamm3... usw. in eine TextDatei eingetragen, genauso wie die Suffixe von den Stämmen (in andere TextDatei): {SuffixStamm1:['ua', 'oi', 'oin', 'oit', 'onj', 'onjsh', 'onjve', 'onjt']}, also gleich == wie:
{'an' : ['ua', 'oi', 'oin', 'oit', 'onj', 'onjsh', 'onjve', 'onjt']}

[BlackJack]

@BUXHO: Naja man überlegt sich welche Daten man braucht um so einen Transduktor zu modellieren und wie man diese Daten dann "interpretieren" kann. Die Übergangsfunktion als Menge von Tupeln der Form (Zustand, Eingabe, Ausgabe, Folgezustand), die Menge der Endzustände, den Startzustand und das Eingabeband bräuchte man. Zustände, Ein- und Ausgabealphabet sind ja in den Tupeln der Übergangsfunktion im Grunde schon enthalten.

Dann muss man sich überlegen wie man die Übergangsfunktion am besten in einer Datenstruktur ablegt. Zum Beispiel eine Abbildung von Zustand und Eingabe auf eine Menge von Ausgaben und Folgezustände.

Danach kann man anfangen die Eingabe abzuarbeiten. Da dieser Automat nichtdeterministisch sein kann, muss man sich mehrere Zustände und mögliche Teilergebnisse für jedes zu verarbeitende Eingabzeichen merken. Am Anfang ist das nur der Startzustand und eine leere Ausgabezeichenkette. Für jedes dieser gemerkten Paare (Zustand, Teilergebnis) muss man dann die Folgezustände und Teilergebnisse ermitteln.

Das macht man solange bis die Eingabe komplett verbraucht ist. Am Ende schaut man dann welche Ergebnisse zu Endzuständen man hat.

Hier mal ein (weitgehend ungetestetes) Beispiel das den ersten Automaten auf der Wikipediaseite Transduktor (Informatik) ausführt:

Code: Alles auswählen

from collections import defaultdict


def transduce(input_iter, transitions, final_states, start_state=0):
    final_states = set(final_states)
    
    state2transitions = defaultdict(list)
    for state, input_, output, target_state in transitions:
        state2transitions[(state, input_)].append((output, target_state))
    
    states = [(start_state, '')]
    for input_ in input_iter:
        new_states = list()
        for state, result in states:
            # 
            # TODO Epsilon-Übergänge.
            # 
            for output, target_state in state2transitions[(state, input_)]:
                new_states.append((target_state, result + output))
        states = new_states
    return [result for (state, result) in states if state in final_states]


def main():
    transitions = [
        (0, 'a', 'x', 2),
        (0, 'a', 'a', 1),
        (0, 'b', 'b', 0),
        (0, 'c', 'c', 0),
        (0, 'd', 'd', 0),
        (0, 'e', 'e', 0),
        (0, 'x', 'x', 0),
        (1, 'a', 'a', 1),
        (1, 'a', 'x', 2),
        (1, 'c', 'c', 0),
        (1, 'd', 'd', 0),
        (1, 'e', 'e', 0),
        (1, 'x', 'x', 0),
        (2, 'b', '', 0)
    ]
    test_input = 'abcdexbaaabab'
    result = transduce(test_input, transitions, [0, 1])
    print result
    assert result[0] == test_input.replace('ab', 'x')


if __name__ == '__main__':
    main()

Das ist jetzt "straight forward" implementiert, ohne Rücksicht auf Performance. Und wie der Kommentar sagt, kann die Funktion auch noch keine Epsilonübergänge, also Übergänge bei denen auch ohne Eingabe eine Ausgabe erfolgt und in einen anderen Zustand übergegangen wird. Kommt in dem Beispiel ja auch nicht vor.

[BUXHO]

erstmal Danke für die Geduld mit mir , weil ich ja kein Profi bin..., muss aber das machen...
Aber ohne Hilfe kann ich leider gar nichts machen.
Entschuldigt mir die Naiven Fragen (wenn ich welche stelle).

[quote="BlackJack"]

Code: Alles auswählen

def main():
    transitions = [
        (0, 'a', 'x', 2),
        (0, 'a', 'a', 1),
        (0, 'b', 'b', 0),
        (0, 'c', 'c', 0),
        (0, 'd', 'd', 0),
        (0, 'e', 'e', 0),
        (0, 'x', 'x', 0),
        (1, 'a', 'a', 1),
        (1, 'a', 'x', 2),
        (1, 'c', 'c', 0),
        (1, 'd', 'd', 0),
        (1, 'e', 'e', 0),
        (1, 'x', 'x', 0),
        (2, 'b', '', 0)
    ]
    test_input = 'abcdexbaaabab'
    result = transduce(test_input, transitions, [0, 1])
    print result
    assert result[0] == test_input.replace('ab', 'x')[/quote]

wie komme ich zu den Transitionen?
Das ist das grösste Problem für mich, für den Anfang - einfach mal zu verstehen...
Bei mir wäre zB. die Liste ['ua', 'oi', 'oin', 'oit', 'onj', 'onjsh', 'onjve', 'onjt']
Also (Theoretisch) wäre:
Zustand 0 auf 1 wenn man 'u' eingibt,
dann 1 auf 2-a (Endzustand) (also bis jetzt sind 'ua' eingegeben) und das Wort (hier Suffix) kann hier enden.
dann 0 auf 3 wenn man 'o' eingibt, dann 3 auf 4 wenn man 'i' eingibt (Endzustand), dann 4 auf 5-n (Endzustand), 5 auf 6-t (Endzustand)... usw., oder?
Wie Programmiere ich das?
VIELEN, VIELEN DANK IM VORAUS

[BlackJack]

@BUXHO: Die Übergangsfunktion aus dem Beispiel habe ich einfach aus dem Diagramm des Zustandsautomaten auf der Wikipediaseite abgelesen ohne weiter darüber nachzudenken.

Wie Du zu Deiner Übergangsfunktion kommst, kann ich Dir so nicht sagen. Ich habe immer noch nicht verstanden was der Transduktor da eigentlich machen soll.

Was immer der machen soll, Du musst Dir halt klar machen wie solche Automaten funktionieren und wie man Deine Problemlösung dann als Diagramm oder Übergangsfunktion ausdrücken kann. Und dann wie man systematisch aus Deinen Listen die Übergangsfunktion herleiten kann.

Eventuell müsste man das auch etwas Umfangreicher als mit der simplen Funktion aufbauen, so dass ein Automat zum Beispiel als Objektgraph von Zustandsobjekten dargestellt wird. Dann kannst Du auch Operationen auf Transduktoren implementieren wie zum Beispiel Optimierungen oder allgemein Transformationen auf einem Transduktor durchzuführen oder mehrere Transduktoren zu Neuen verknüfen. Auf Wikipedia wird ja irgendwo erwähnt, dass in der praktischen Anwendung Transduktoren für Teillösungen durch Komposition oder Konkatenation verknüpft werden.

Warum machst Du das überhaupt? Was ist der Sinn und Zweck so etwas selber zu implementieren, vor allem wenn man anscheinend so wenig Ahnung davon hat. Das ist ja schon etwas "heftiger" -- praktische Anwendung von theoretischer Informatik. Wobei "praktische" Anwendung sicher so auch nicht möglich ist, denn da wird man sich wohl etwas näher mit effizienten Implementierungen von so etwas auseindersetzen müssen, und in Python wahrscheinlich entweder nur einen Prototypen oder einen Compiler von einer Beschreibung so eines Transduktors in ein effizientes C-Programm, schreiben.