Czy parser Earleya można przekształcić w rozmyty parser podobny do Levenshtein Automata Algo dla DFA?

Istnieje sposób wykonywania rozmytego parsowania (akceptuje ciągi nawet w literówkach do określonej odległości edycji), z DFA i skonstruowanymi w czasie wykonywania automatami Levenshtein słowa wejściowego. Czy coś podobnego można zrobić z parserem Earley? Trudno mi zrozumieć algorytm, a co dopiero odpowiedzieć na to pytanie.

— EnjoysMath
źródło

Cóż, PDA są zamknięte na wiele operacji z NFA, więc powinno to być w zasadzie możliwe. Dostosowanie Earleya wydaje się być ćwiczeniem na pamięć, ponieważ możemy używać liczników w przedmiotach. Czy coś brakuje?

— Raphael

@Raphael Tak To jest ogólny pomysł. Moja odpowiedź jest dłuższa, ponieważ trudno jest ocenić, co użytkownicy wiedzą lub nie wiedzą.

— babou

plz cytują ref / szkic defn dla „Levenshtein Automata”. znasz takiego, który może się kwalifikować, ale do którego masz na myśli?

— vzn

Odpowiedź brzmi tak. Nie zrobiłbym tego jednak z parserem Earley, ponieważ są prostsze z tymi samymi możliwościami.

Zasadniczo, parser Earley należy do rodziny ogólnych parserów bezkontekstowych, które produkują wszystkie możliwe analizy dla danego łańcucha, gdy gramatyka jest niejednoznaczna.

Istnieją dwa sposoby (przynajmniej) zrozumienia tych parserów:

jako dynamiczna interpretacja programowania automatu odpychającego odpowiadającego gramatyce ciągu wejściowego;
jako konstrukcja przecięcia gramatyki z automatem skończonym.

$w$ $|w|+1$ $A$ $G$ $F$ $\mathcal L(A)\cap\mathcal L(G)$ $F$ $G$ , aż do zmiany nazw terminali innych niż terminale (z powodu różnych produktów).

$A$ $F$ $\mathcal L(G)$ $\emptyset$ $G$

$F$

Ale, jak widzisz, uogólnia to na analizowanie całego regularnego zestawu, jeśli ktoś jest tego zainteresowany.

$w$ $w$

$G$ $F$

Jeśli jest to pożądane, można to wykorzystać do zachowania tylko łańcuchów przy minimalnej odległości.

Można to jednak nieco poprawić, ponieważ kompozycja za pomocą automatów skończonych jest asocjacyjna.

$G$ $w$ $\Sigma^*$

Łatwo byłoby przycinać tę konstrukcję, aby uzyskać ten sam wynik jak poprzednio, ale najlepszym sposobem jest bardziej kontrolowana konstrukcja skrzyżowania, taka jak dynamiczna organizacja programowania używana przez większość parserów w literaturze, w tym Earleya, i używaj jej, aby uniknąć generowania niepotrzebna reguła, obliczając odległości i przerywając dowolną ścieżkę obliczeniową, gdy przekroczy ona pożądany próg. Programowania dynamicznego można również użyć do bezpośredniego obliczenia parsowania lasu (lub parsowania drzewa) dla ciągu, który ma najkrótszą odległość od danych wejściowych.

— Babou
źródło

myślę, że jest to pomocne, ale może też „wczytujesz zbyt wiele” w pytanie, więc powiedzenie czegoś w rodzaju „to jest dokładnie twoje pytanie” nie może być naprawdę dokładne. podjąłeś raczej niejasne pytanie, które nie zostało ściśle sformalizowane, i (próbowałeś?) sformalizować je samodzielnie. istnieje prawdopodobnie więcej niż jeden sposób sformalizowania pierwotnego, niejasnego pomysłu. sądzisz, że pomocne może być 1. dokładne zdefiniowanie tego, co robią konstrukcje Levenshtein DFA (istnieją pewne znane / badane, ale o których mówimy?), a następnie wyjaśnienie, w jaki sposób tę koncepcję można uogólnić na świetlówki kompaktowe.

— vzn

Daję różne formalizacje, które się uzupełniają. Są subtelności, do których nie dotarłem, takie jak dokładne użycie ciężarów w procesie, które zależy od dokładnego wyniku, jaki chcesz uzyskać. Moim celem jest nie tylko udzielenie odpowiedzi, która nie jest zainteresowana moim zdaniem, ale także szersze zrozumienie problemu. Wybór zastosowanej odległości edycji jest nieistotny, działa na wszystko, co można wyrazić za pomocą ważonego przetwornika skończonego stanu.

— babou