Analiza zależnościowa

Analiza zależnościowa – podobnie jak analiza frazowa, typ analizy języka naturalnego, w którym struktura badanego zdania determinowana jest poprzez relacje zachodzące pomiędzy wyrazami znaczącymi a im podrzędnymi. Cechą charakterystyczną analizy zależnościowej jest to, że nie wymaga ona ścisłego szyku zdania do określenia jego struktury. W omawianym modelu analizy zależności grupowane są według podziału na części mowy.

Cechy analizy zależnościowej

w drzewie zależności, będącym wynikiem analizy zależnościowej jeden węzeł odpowiada jednemu wyrazowi
podczas analizy zależnościowej w kolejnych krokach analizuje się kolejne wyrazy

Algorytm

Drzewa zależności

Każde zdanie języka polskiego można przedstawić w formie drzewa zależności. Węzły takiego grafu odpowiadają słowom przedstawianego zdania natomiast krawędzie pomiędzy dwoma węzłami występują wtedy, gdy któryś z pary węzłów reprezentuje słowo zależne od drugiego.

Założenia algorytmu parsingu zależnościowego

jedność - wynikiem procesu parsowania jest pojedyncze drzewo, składające się ze wszystkich słów podanych na wejściu
unikalność - każde słowo ma tylko jedno słowo nadrzędne
jednorazowe przejście parsowanego zdania
"skwapliwość" - parser przyporządkowuje dwóm węzłom krawędź tak wcześnie, jak to tylko możliwe

Przykłady algorytmów

Algorytm siłowy - polega na badaniu każdej pary słów należących do zdania oraz łączenie ich w zależności, jeśli gramatyka na to pozwala
Algorytm ESH (Exhaustive left-to-right search, heads first) – dla każdego kolejnego słowa ze zdania wejściowego badane są możliwe zależności ze słowami poprzedzającymi. Wariacją powyższego algorytmu jest algorytm ESD (Exhaustive left-to-right search, dependents first) czyli taki, który najpierw sprawdza, czy słowo j jest podrzędne do słowa i a dopiero potem, czy j jest nadrzędne do słowa i. Różnica w pseudokodzie jest niewielka, linijki [5-6] i [7-8] są zamienione ze sobą miejscami.

Pseudokod algorytmu ESH:

1. for i:=1 to n
2. begin
3.	for j:=i-1 downto 1 do
4.	begin
5.		if(zgodne z gramatyka)
6.			polacz slowo j jako nadrzedne do slowa i
7.		if(zgodne z gramatyka)
8.			polacz slowo j jako podrzedne do slowa i
9.	end
10. end

Algorytm LSUP (List-based search with uniqueness and projectivity) – zapewnia unikalność oraz "przyleganie"

Pseudokod algorytmu LSUP:

1.Headlist := [];        (słowa bez słów nadrzędnych)
2.Wordlist := [];         (wszystkie dotychczas napotkane słowa)
3.repeat
4.	(Odbierz słowo z listy argumentów algorytmu i dodaj je do headlist)
5.	W := następne słowo do sparsowania
6.	Wordlist := W + Wordlist;
7.	(Szukaj słów podrzędnych słowu W; mogą nimi być kolejne słowa listy headlist poczynając od ostatnio dodanego)
8.	for D := każdy element z HEADLIST zaczynając od pierwszego
9.	begin
10.		if (D może zależeć od W) then
11.		begin
12.			połącz D jako zależny od W;
13.			usuń D z HEADLIST;
14.		end
15.		else
16.			break;
17.		end;
18.	(Szukaj słów nadrzędnych słowu W; musi ono mieścić w sobie słowo poprzedzające W)
19.	H := słowo bezpośrednio poprzedzające W w ciągu wejściowym;
20.	loop
21.		if (W może zależeć od H) then
22.		begin
23.			połącz W jako zależące od H;                   
24.			zakończ pętlę;
25.		end;                                           
26.		if (H nie posiada słowa nadrzędnego) then 
27.		begin
28.			zakończ pętlę;
29.		end;
30.		H := the head of H                                
31.	end loop;
32.	if (słowo nadrzędne dla W nie zostało znalezione)
33.	begin
34.		Headlist := W + Headlist;                         
35.	end;
36.until (wszystkie słowa zostały sparsowane)

Zobacz też

Bibliografia

Laila Dybkjaer, Holmer Hemsen, Wolfgang Minker: Evaluation of Text and Speech Systems

Linki zewnętrzne

AndrzejA. Zaborowski AndrzejA., Wizualizacja wyników analizy składniowej zdań języka naturalnego [online], Wydział Matematyki, Informatyki i Mechaniki UW [dostęp 2018-03-25] .
Michael A.M.A. Covington Michael A.M.A., A Fundamental Algorithm for Dependency Parsing [online], Artificial Intelligence Center, The University of Georgia (ang.).