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. thumb|420px|right|Przykład analizy zależnościowej thumb|420px|right|Przykład analizy frazowej
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 jest podrzędne do słowa , a dopiero potem, czy jest nadrzędne do słowa . 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ż Analiza języka naturalnego Analiza składniowa Analiza frazowa
Bibliografia Laila Dybkjaer, Holmer Hemsen, Wolfgang Minker: Evaluation of Text and Speech Systems
Linki zewnętrzne
Kategoria:Lingwistyka komputerowa Kategoria:Składnia