#############################################################################
### Търсене и извличане на информация. Приложение на дълбоко машинно обучение
### Стоян Михов
### Зимен семестър 2020/2021
#############################################################################

### Домашно задание 1
###
### За да работи програмата, трябва да се свали корпус от публицистични текстове за Югоизточна Европа,
### предоставен за некомерсиално ползване от Института за български език - БАН
###
### Корпусът може да бъде свален от:
### Отидете на http://dcl.bas.bg/BulNC-registration/#feeds/page/2
### И Изберете:
###
### Корпус с новини
### Корпус от публицистични текстове за Югоизточна Европа.
### 27.07.2012 Български
###    35337  7.9M
###
### http://dcl.bas.bg/BulNC-registration/dl.php?dl=feeds/JOURNALISM.BG.zip
###
### Архивът трябва да се разархивира в директорията, в която е програмата.
###
### Преди да се стартира програмата, е необходимо да се активира съответната среда с командата:
### conda activate tii
###
### Ако все още нямате създадена среда, прочетете файла README.txt за инструкции

import model
import numpy as np

def editDistance(s1, s2):
    ### Функцията намира разстоянието на Левенщайн-Дамерау между два низа
    ### Вход:
    ###     низ: s1
    ###     низ: s2
    ### Изход: минималният брой на елементарните операции (вмъкване, изтриване, субституция и транспозиция на символи) необходими да се получи единият низ от другия
    #############################################################################
    ### Начало на Вашия код. На мястото на pass се очакват 10-25 реда

    M = np.zeros((len(s1)+1,len(s2)+1))
    for i in range(len(s1) + 1):
        M[i,0] = i
    for j in range(len(s2) + 1):
        M[0,j] = j
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i-1] == s2[j-1]:
                M[i,j] = M[i-1,j-1]
            elif i >= 2 and j >= 2 and s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1]:
                M[i,j] = 1 + min(M[i-1,j-1], M[i-1,j], M[i,j-1], M[i-2,j-2])
            else:
                M[i,j] = 1 + min(M[i-1,j-1], M[i-1,j], M[i,j-1])
    return M[len(s1),len(s2)]

    ### Край на Вашия код
    #############################################################################


def operationWeight(a, b):
    ### Функцията operationWeight връща теглото на дадена елементарна операция
    ### Тук сме реализирали функцията съвсем просто -- връщат се фиксирани тегла, които не зависят от конкретните символи. При наличие на статистика за честотата на грешките, тези тегла следва да се заменят със съответни тегла, получени след оценка на вероятността за съответната грешка, като се използва принципът за максимално правдоподобие
    ### Вход:
    ###     низ: a
    ###     низ: b
    ### Изход: теглото за операцията
    ### ВАЖНО: При изтриване и вмъкване се предполага, че празният низ е представен с None
    if a == None and len(b) == 1:
        return 3.0          # insertion
    elif b == None and len(a) == 1:
        return 3.0          # deletion
    elif a == b and len(a) == 1:
        return 0.0          # identity
    elif len(a) == 1 and len(b) == 1:
        return 2.5          # substitution
    elif len(a) == 2 and len(b) == 2 and a[0] == b[1] and a[1] == b[0]:
        return 2.25         # transposition
    else:
        print("Wrong parameters ({},{}) of primitiveWeight call encountered!".format(a,b))

def editWeight(s1, s2):
    ### Функцията editWeight намира теглото между два низа. За намиране на елеметарните тегла следва да се извиква функцията operationWeight
    ### Вход:
    ###     низ s1
    ###     низ s2
    ### Изход: минималното тегло за подравняване, за да се получи от единия низ другият
    #############################################################################
    ### Начало на Вашия код. На мястото на pass се очакват 10-25 реда
    G = np.zeros((len(s1) + 1, len(s2) + 1))
    for i in range(1, len(s1) + 1):
        G[i, 0] = G[i - 1, 0] + operationWeight(s1[i-1], None)
    for j in range(1, len(s2)+1):
        G[0, j] = G[0, j - 1] + operationWeight(s2[j-1], None)
    for i in range(0, len(s1)):
        for j in range(0, len(s2)):
            best = np.array([G[i, j] + operationWeight(s1[i], s2[j]),
                             G[i + 1, j] + operationWeight(None, s2[j]),
                             G[i, j + 1] + operationWeight(s1[i], None)]).min()

            if i >= 1 and j >= 1 and s1[i] == s2[j - 1] and s2[j] == s1[i - 1]:
                G[i + 1, j + 1] = np.array([best,
                                   G[i - 1, j - 1] + operationWeight(s1[i] + s2[j], s2[j] + s1[i])]).min()
            else:
                G[i + 1, j + 1] = best
    return G[len(s1), len(s2)]

    ### Край на Вашия код
    #############################################################################


def generateEdits(q):
    ### Помощната функция generateEdits по зададена заявка генерира всички възможни редакции на разстояние 1 от тази заявка
    ### Вход:
    ###     низ: q, представящ заявката
    ### Изход: списък от низове на разстояние 1 по Левенщайн-Дамерау от заявката
    ### Забележка: в тази функция вероятно ще трябва да използвате азбука, която е дефинирана в model.alphabet
    #############################################################################
    ### Начало на Вашия код. На мястото на pass се очакват 10-15 реда
    res=[]
    #deletion
    for i in range(len(q)):
        res.append(q[:i] + q[i+1:])
    #insertion
    for i in range(len(q) + 1):
        for j in range(len(model.alphabet)):
            res.append(q[:i] + model.alphabet[j] + q[i:])
    #substitution
    for i in range(len(q)):
        for j in range(len(model.alphabet)):
            if model.alphabet[j] != q[i]:
                res.append(q[:i] + model.alphabet[j] + q[i+1:])
    #transposition
    for i in range(2,len(q) + 1):
        if q[i-1] != q[i-2]:
            res.append(q[:i-2] + q[i - 1] + q[i - 2] + q[i:])
    return res

    ### Край на Вашия код
    #############################################################################




def generateCandidates(query,dictionary):
    ### Функцията започва от заявката query и генерира всички низове НА РАЗСТОЯНИЕ <= 2, за да се получат кандидатите за корекция. Връщат се единствено кандидати, всички думи на които са в речника dictionary.
    ### Вход:
    ###     низ: query
    ###     речник: dictionary
    ### Изход: списък от двойки (candidate, candidateEditLogProbability), където candidate е низ-кандидат, а candidateEditLogProbability е логаритъм от вероятността за редакция, тоест минус теглото.
    
    def allWordsInDictionary(q):
        ### Помощната функция връща истина, ако всички думи в заявката са в речника
        return all(w in dictionary for w in q.split())

    #############################################################################
    ### Начало на Вашия код. На мястото на pass се очакват 10-15 реда
    allPossible = generateEdits(query)
    second = []
    for i in range(len(allPossible)):
        second.extend(generateEdits(allPossible[i]))
    allPossible.extend(second)
    candidates = []
    for i in range(len(allPossible)):
        if allWordsInDictionary(allPossible[i]) and (editDistance(query, allPossible[i]) == 1 or editDistance(query, allPossible[i]) == 2):
            candidates.append((allPossible[i], -editWeight(allPossible[i], query)))

    return candidates

    ### Край на Вашия код
    #############################################################################


def correctSpelling(r, model, mu = 1.0, alpha = 0.9):
    ### Функцията комбинира езиковия модел model с кандидатите за корекция, генерирани от generateCandidates, за намиране на най-вероятната желана заявка от дадената оригинална заявка query. Функцията, която генерира кандидати, връща и вероятността за редактиране
    ### Вход:
    ###    низ: r, представящ заявката
    ###    езиков модел: model
    ###    число: mu -- тегло на езиковия модел
    ###    число: alpha -- коефициент за интерполация на езиковия модел
    ### Изход: най-вероятната заявка

    def getScore(q,logEditProb):
        ### Функцията използва езиковия модел и вероятността за редакцията logEditProb за изчисляване на оценка за кандидата q. Използва mu като степен на тежест за Pr[q].
        ### Вход:
        ###     низ: q -- кандидат заявка
        ###     число: logEditProb -- логаритъм от вероятността за редакция на дадената заявка (т.е. log Pr[r|q], където r е оригиналната заявка)
        ### Изход: логаритъм от вероятността за кандидат заявката
        #############################################################################
        #### Начало на Вашия код. На мястото на pass се очакват 1-3 реда
        sen = q.split(" ")
        return logEditProb + (model.sentenceLogProbability(sen, alpha) ** mu)
        #### Край на Вашия код
        #############################################################################
    ###
    ###
    #############################################################################
    #### Начало на Вашия код за основното тяло на функцията correctSpelling. На мястото на pass се очакват 2-5 реда
    candidates = generateCandidates(r, model.kgrams[tuple()])
    candidates_ = sorted([(c[0], getScore(c[0], c[1])) for c in candidates], key = lambda x: x[1], reverse = True)
    return candidates_[0][0]

    #### Край на Вашия код
    #############################################################################
