# PJN - Ćwiczenia 4, 11 stycznia 2021 r.

## Zadanie 4.1

CYK - dynamiczny algorytm parsowania zdania w języku przedstawiony na wykładzie.
PRZYPOMNIENIE:


Pomysł na znalezienie oryginalnego zdania na podstawie ciągu zbiór słów.
Odpalmy algorytm CYK z dostępną gramatyką dla zbioru słów, a nie dla pojedynczych słów:

- W pierwszym etapie, w którym próbujemy znaleźć wyprowadzenie słowa w nieterminal na podstawie jakiejś projekcji iterujemy się po wyprowadzeniach i znajdujemy wszystkie słowa pasujące do danej projekcji. Inne usuwamy. Jeżeli kilka projekcji pasuje do naszego zbioru słów to kopiujemy nasz algorytm i rozważamy wszystkie projekcje jednocześnie.
- Pozostałe kroki wykonujemy podobnie do poprzedniego z tym, że jeżeli nie da się na którymś etapie znaleźć poprawnego wyprowadzenia to kończymy tę instancję programu z niepowodzeniem.
- Po zakończeniu dostajemy (jeden dla każdej zakończonej pozytywnie instanji algorytmu) ciąg zbiorów słów. Jeżeli teraz stworzymy iloczyn kartezjański tych ciągów to na pewno dostaniemy prawdziwe zdanie jako jedno z wynikowych.

Uwagi:
- Jeżeli założymy, że z dostępnych zbiorów słów da się wyprowadzić tylko jedno sensowne zdanie (i jest to szukane zdanie) to ostatni punkt uprości się.
- Z każdą kolejną iteracji naszych instancji programu będzie coraz mniej, a ostatecznych wyników nie będzie zbyt wiele. Z czasem więc nasz algorytm będzie przyspieszał.

## Zadanie 4.2

Stwórzmy nowe ukryte znaczniki, które bedziemy stawiać między słowami, które tagujemy:
0 - Dwa słowa nie tworzą razem frazy
$B_c$ - Słowo po lewej i po prawej tworzą frazę
$L_c$ - Słowo po lewej jest jednowyrazową frazą niełączącą się ze słowem po prawej stronie

np.
Jan (Bp) Kowalski (0) pojechał (0) do (0) Jeleniej (Bc) Góry (0) i (0) Wałbrzycha (Lc) autobusem (0) .

## Zadanie 4.3
Byte pair encoding
aabdsxxaa -> AbdsxxA
alamakota -> ABC
A = ala
B = ma
C = kota

def most_popular_bigram(corp):
    res = dict()
    for sentence in corp:
        sent = sentence.split()
        for i in range(len(sent) - 1):
            key = (sent[i], sent[i+1])
            res[key] += count(sentence)
    return max(res, key=lambda x : res[x])
    # p(freqs)/(p(freq[0])*p(freq[1])) <- wordpiece
    
def make_new_letter(corp, bigram):
    new_corp = dict()
    for sentence in corp:
        new_sentence = sentence
        if bigram in sentence:
            new_sentence.replace(bigram, new_bigram)
        new_corp[new_sentence] = corp[sentence]
    return new_corp

while True:
    bigram = most_popular_bigram(corp)
    corp = make_new_letter(corp, bigram)

## Zadanie 4.4

oysteóeursuątyśhceszkupowakwięcec_nnpźpzieizdziej
możetenprzepadekoaszraszkannychkłusoźyiyówcdterpprołeeeru

_oysteóeursuątyśhceszkupowakwięcec_nnpźpzieizdziej_
_możetenprzepadekoaszraszkannychkłusoźyiyówcdterpprołeeeru_

1. Liczymy n-gramy literowe(4,5,6,7)
2. Dla każdego słowa testowego , dopisujemy na początku i na końcu spację i rozważamy najdłuższym statystkami najdłuższego ngramu możliwego dla słowa.

## Zadanie 4.5

krytyczna decyzja <- przymiotnik, rzeczownik
silnik spalinowy <- rzeczownik, przymiotnik
nowoczesny silnik spalinowy <- przymiotnik, rzeczownik, przymiotnik
wczorajsza awaria modułu napędowego autobusu elektrycznego
\-\-\-
przymiotnik, rzeczownik, rzeczownik, przymiotnik, rzeczownik, przymiotnik

S <- symbol startowy
Z <- zdanie
P <- przymiotnik/inna część mowy określająca rzeczownik
R <- rzeczownik

S $\to$ Z
Z $\to$ ZZ | PRP
R $\to$ rzeczownik
P $\to$ przymiotnik | $\varepsilon$

Ujednoznacznienie (Rozwijanie w lewo):

S $\to$ Z
Z $\to$ ZZ' | Z'
Z' $\to$ PRP
R $\to$ rzeczownik
P $\to$ przymiotnik | $\varepsilon$

Ujednoznacznienie 2 (Rozwijanie w lewo):

S $\to$ Z P
Z $\to$ ZZ' | Z'
Z' $\to$ PR
R $\to$ rzeczownik
P $\to$ PP' | $\varepsilon$
P' $\to$ przymiotnik
## Zadanie 4.6
Kolokacja:
$$PPMI(w_1,w_2) = max\left(0, log\left(\frac{P(w_1w_2)}{P(w_1)\cdot P(w_2)}\right)\right)$$

Jeżeli $PPMI(w_1, w_2) > \alpha$ to ok gdzie $\alpha \in [0,c]$. Wybór $c$ eksperymentalnie.

--