63 lines
1.9 KiB
Python
63 lines
1.9 KiB
Python
|
"""
|
||
|
|
pta — Prefix-Tree Automaton (PTA) construction.
|
||
|
|
|
||
|
|
Nach Bex et al. 2008/2010: Der PTA ist der initiale Automat, der aus
|
||
|
|
den positiven Beispielsequenzen (Token-Sequenzen) konstruiert wird.
|
||
|
|
|
||
|
|
Jede Sequenz wird als Pfad im Trie abgebildet:
|
||
|
|
- Wurzel = Startzustand
|
||
|
|
- Jeder gemeinsame Prefix wird geteilt (wie im Trie)
|
||
|
|
- Der letzte Zustand jeder Sequenz wird als accept markiert
|
||
|
|
|
||
|
|
Der PTA ist deterministisch und akzeptiert genau die gegebenen Sequenzen.
|
||
|
|
Er ist der Ausgangspunkt für die SORE/CHARE-Inferenz via shrink-Rewrites.
|
||
|
|
"""
|
||
|
|
|
||
|
|
from .automaton import Automaton
|
||
|
|
|
||
|
|
|
||
|
|
def build_pta(sequences):
|
||
|
|
"""
|
||
|
|
Konstruiert den Prefix-Tree Automaton aus einer Liste von Token-Sequenzen.
|
||
|
|
|
||
|
|
Nach Bex et al. 2008/2010, Algorithmus PTA:
|
||
|
|
- Initialisiere mit Startzustand q0
|
||
|
|
- Für jede Sequenz w = a1...an:
|
||
|
|
- Starte in q0
|
||
|
|
- Für jedes ai: Folge der Kante (q, ai) falls vorhanden,
|
||
|
|
sonst erzeuge neuen Zustand q' und Kante (q, q', ai)
|
||
|
|
- Markiere Endzustand als accept
|
||
|
|
|
||
|
|
Args:
|
||
|
|
sequences: Liste von Token-Listen (jede = ein YAML-Dokument)
|
||
|
|
|
||
|
|
Returns:
|
||
|
|
Automaton: PTA für die gegebenen Sequenzen
|
||
|
|
|
||
|
|
Example:
|
||
|
|
>>> build_pta([["apt", "service"], ["apt", "template", "service"]])
|
||
|
|
Automaton(nodes=5, edges=5, start=0, accepts={3, 4})
|
||
|
|
"""
|
||
|
|
automaton = Automaton(start=0)
|
||
|
|
automaton.add_node(0)
|
||
|
|
|
||
|
|
next_id = 1
|
||
|
|
|
||
|
|
for seq in sequences:
|
||
|
|
current = 0
|
||
|
|
for token in seq:
|
||
|
|
found = False
|
||
|
|
for (to, label) in automaton.successors(current):
|
||
|
|
if label == token:
|
||
|
|
current = to
|
||
|
|
found = True
|
||
|
|
break
|
||
|
|
if not found:
|
||
|
|
new_node = next_id
|
||
|
|
next_id += 1
|
||
|
|
automaton.add_edge(current, new_node, token)
|
||
|
|
current = new_node
|
||
|
|
automaton.add_accept(current)
|
||
|
|
|
||
|
|
return automaton
|