1. Заданный английский текст большого размера. Его нужно скачать и положить в папку lab_2.

Уже сделано, обратите внимание на содержимое файла main.py ближе к концу:

if __name__ == '__main__':
  with open('not_so_big_reference_text.txt', 'r') as f:
    REFERENCE_TEXT = f.read()

Заданный английский текст необходимо разбить на предложения. Таким образом, получить список из строк. В качестве разделителя использовать точку пробел и факт того, что следующее слово начинается с большой буквы. Все строки (предложения) в нижнем регистре, не содержат никаких знаков пунктуации, в том числе и замыкающую точку.

Например, для текста Mar#y wa$nted, to swim! However, she was afraid of sharks. должен получиться

[
  [
    "<s>", "mary", "wanted", "to", "swim", "</s>"
  ],
  [
    "<s>", "however", "she", "was", "afraid", "of", "sharks", "</s>"
  ]
]

Внешний интерфейс выглядит так:

def split_by_sentence(text: str) -> list:
  pass

Обратите внимание, что каждое предложение после токенизации также содержит в себе специальные символы начала ("<s>") и конца предложения ("</s>"). Вставка этих символов обязательна для корректной работы приложения в дальнейшем.

Для хранения слов и их идентефикаторов необходимо создать поле класса - storage.

Необходимо каждому слову из заданного текста присовить некоторый уникальный идентификатор (id). Это требуется для того, чтобы работать не со строками напрямую, а с числами, которые их представляют.

Например, есть слово "experience", поставим ему в соответствие некоторое уникальное число - 12345. Следующему слову "elimination" - 12346 и так далее. Эти слова необходимо поместить в хранилище (storage), ключом хранилища является слово, а значение его идентефикатор. Слова указанные выше храниться будут так:

self.storage = {..., "experience": 12345, "elimination": 12346, ...}

Выбор правила для присваивания идентификатора (счетчик, начинающийся с нуля или с заданного значения) - произвольный - на ваш выбор. Основное условие - для одного и того же слова существует ровно один идентификатор. Одинаковых идентификаторов у двух разных слов также быть не может. Внешний интефейс такой: это класс WordStorage:

class WordStorage:
    pass

Для добавления слова в хранилище, реализуйте метод put, который принимает на вход новое слово и возвращает его идентификатор.

class WordStorage:
  ...
  def put(self, word:str) -> int:
    pass

Для любого слова можно попытаться получить его id. Для этого, реализуйте метод get_id_of, который принимает на вход слово и возвращает его идентификатор. Если слово неизвестное, возвращается None.

class WordStorage:
  ...
  def get_id_of(self, word:str) -> int:
    pass

Для любого id можно попытаться получить соответствующее ему слово. Для этого, реализуйте метод get_original_by(id:int), который принимает на вход идентификатор и возвращает слово. Если идентификатор неизвестный, возвращается None.

class WordStorage:
  ...
  def get_original_by(self, id:int) -> str:
    pass

Для этого воспользуемся полученным в результате Шага №1 списком предложений и добавим все слова из него в экземпляр класса WordStorage с помощью метода from_corpus. Готовый заполненный экземпляр будем активно использовать далее.

class WordStorage:
  ...
  def from_corpus(self, corpus: tuple):
    pass

Полученный в результате Шага №1 корпус предложений необходимо кодировать с помощью заполненного экземпляра класса WordStorage. Кодирование заключается в замене слов на соответствующие им идентификаторы.

Например, корпус из одно предложения:

[
  [
    "experience", "elimination"
  ]
]

превращается в:

[
  [
    12345, 12346
  ]
]

def encode(storage_instance, corpus) -> list:
  pass

Это не опечатка в названии класса. Такое название выбрано намеренно (trie является отраслевым термином).

Для успешного предсказания следующего слова на основании заданного контекста, необходимо построить абстракцию, которая предоставляет достаточный для этого интерфейс.

Класс NGramTrie позволяет собрать Н-грамы из заданного предложения.

Пример №1. Дано предложение Mary wanted to swim. Хотим построить NGramTrie с размером грамы равным 2. Тогда получаем следующие би-грамы: ('<s>', 'mary'), ('mary', 'wanted'), ('wanted', 'to'), ('to', 'swim'), ('swim', '</s'>).

Пример №2. Дано предложение Mary wanted to swim. Хотим построить NGramTrie с размером грамы равным 3. Тогда получаем следующие три-грамы:('<s>', 'mary', 'wanted'), ('mary', 'wanted', 'to'), ('wanted', 'to', 'swim'), ('to', 'swim', '</s'>)

Символы<s>, </s> обозначают конец и начало предложения. Эти символы должны оказаться частью хранилища слов как самостоятельные слова. Попробуйте догадаться сами, зачем это необходимо и как это правильно сделать.

Создадим класс:

class NGramTrie:
  pass

Конструктор должен принимать на вход размер контекста ("N" из названия N-gram - 1 для уни-грам, 2 - для би-грам, 3 - для три-грам и т.д.). Это значение сохранется в собственном поле экземпляра класса - size.

Сами Н-грамы должны храниться в собственном поле экземпляра класса - gram_frequencies. Обязательно использовать для хранения словарь, где ключами выступают кортежи из чисел, а значения - частота возникновения соответствующего кортежа в тексте.

Например, пусть есть некоторая би-грама (1,2), которая встречалась в тексте 10 раз. Тогда в классе она будет храниться так:

self.gram_frequencies[(1,2)] = 10

Аналогично в классе хранятся и лог-вероятности, но в поле gram_log_probabilities. В одном из следующих шагов разберемся как его правильно заполнять.

Цель данного метода заполнить внутреннее содержимое класса - gram_frequencies, определенное в Шаге №4.

Заполнение происходит с помощью метода:

class NGramTrie:
  ...
  def fill_from_sentence(self, sentence: tuple) -> str:
    pass

Метод fill_from_sentence возвращает метод код в виде строки: 'OK' - если все в порядке. 'ERROR' - если произошла ошибка.

Напомним, что на самом деле на данном этапе вы уже работаете с закодироваными предложениями, полученными на Шаге №3. Текстовое описание дано для наглядности.

Для расчета би-грам воспользуемся следующей формулой:

- это количество появлений кортежа в заданном тексте (частота). - это количество появлений кортежей вида для всех w в заданном корпусе.

Идея проста: насколько часто, би-грама, начинающаяся со слова будет заканчиваться интересующим нам словом .

Выполнение би-грам обязательно для всех студентов.

Для студентов, желающих получить оценку 8 требуется реализовать три-грамы.

Реализация N-грам требуется только для студентов, желающих получить оценку 9 или 10. Больше информации в Шагах №6 и №7.

После получения относительных вероятностей (описаны выше), необходимо взять логарифим по основанию e (натуральный логарифм) от полученного отношения. В рамках текущей работы, это просто требование - оперировать лог-вероятностями.

Все значения вероятностей храним в словаре, аналогичном gram_frequencies, он должен называться gram_log_probabilities.

Интерфейс такой:

class NGramTrie:
  ...
  def calculate_log_probabilities(self):
  pass

Есть некоторый префикс, выраженный в виде списка закодированных слов. По нему мы хотим сгенерировать целое предложение.

Интерфейс данного метода следующий:

class NGramTrie:
  ...
  def predict_next_sentence(self, prefix: tuple) -> list:
    pass

В результате получаем список из закодированных слов, включая и сам префикс.

Если размер префикса не соответствует ожидаемому, функция возвращает пустой список. Ожидаемый размер префикса равен размеру грамы (би- или три-граммы) минус один. Так, для би-грамы размер префикса должен равняться единице, для три-грамы префикс состоит из двух элементов, и т.д.

Обощение до Н-грам обязательно для претендентов на оценку 9.

В Шаге 4.3 было продемострировано как посчитать лог-вероятность для би-грам.

Формула для расчета вероятности для N-грам:

Не забываем про необходимость взятия натурального логарифма от полученной вероятности.

• Полезный ресурс для пытливых умов
• Что такое лог-вероятности и зачем они нужны.

python -m unittest discover -p "*_test.py" -s .