Лабораторная работа №3. Генерация текста с помощью n-грамм

Full API

Дано

  1. Текст на английском языке (assets/Harry_Potter.txt), который загружен и сохранен в переменную text в start.py.

  2. Языковой профиль английского языка (assets/en_own.json).

Генерация текста — одна из прикладных задач обработки естественного языка (Natural Language Processing, NLP). На данный момент существует много больших языковых моделей, которые могут генерировать тексты, близкие к написанным человеком.

Задача генерации текста реализует возможность языковой модели на основе исходного текста предсказывать последующее слово и генерировать осмысленный текст.

Существуют различные алгоритмы, позволяющие генерировать последовательности. По ходу выполнения лабораторной работы Вы познакомитесь с тремя алгоритмами:

  1. Greedy Algorithm

  2. Beam Search Algorithm

  3. BackOff Algorithm

Терминология

В рамках лабораторной работы Вы будете работать с n-граммами.

N-граммы

Последовательность из n элементов, включенная в другую последовательность.

В настоящей лабораторной мы будем работать с n-граммами, состоящими из закодированных токенов текста.

Допустим, у нас есть следующий закодированный текст: (1, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0)

Каждое число в этой последовательности однозначно соответствут какому-либо токену. Тогда биграммы (n-граммы размера 2) имеют следующий вид: ((1, 2), (2, 3), (3, 0), (0, 4), (4, 1), (1, 0), (0, 2), (2, 5), (5, 6), (6, 6), (6, 7), (7, 0), (0, 2), (2, 3), (3, 0), (0, 4), (4, 1), (1, 0), (0, 2), (2, 5), (5, 6), (6, 6), (6, 7), (7, 0));

Иными словами, это все подпоследовательности длины 2, которые можно извлечь из этого текста.

Триграммы (N-граммы размера 3) имеют следующий вид: ((1, 2, 3), (2, 3, 0), (3, 0, 4), (0, 4, 1), (4, 1, 0), (1, 0, 2), (0, 2, 5), (2, 5, 6), (5, 6, 6), (6, 6, 7), (6, 7, 0), (7, 0, 2), (0, 2, 3), (2, 3, 0), (3, 0, 4), (0, 4, 1), (4, 1, 0), (1, 0, 2), (0, 2, 5), (2, 5, 6), (5, 6, 6), (6, 6, 7), (6, 7, 0))

Что необходимо сделать

Шаг 0. Начать работу над лабораторной (вместе с преподавателем на практике)

  1. Измените файлы main.py и start.py.

  2. Закоммитьте изменения и создайте новый Pull Request.

Important

Код, выполняющий все требуемые действия, должен быть написан в функции main в модуле start.py.

Для этого реализуйте функции в модуле main.py и импортируйте их в start.py. Вызов функции в файле start.py:

if __name__ == '__main__':
    main()

В рамках данной лабораторной работы нельзя использовать сторонние модули, а также стандартные модули collections и itertools.

Обратите внимание, что в файле target_score.txt необходимо выставить желаемую оценку: 4, 6, 8 или 10. Чем выше желаемая оценка, тем большее количество тестов запускается при проверке вашего Pull Request.

Шаг 1. Объявить сущность по обработке текста, кодированию и декодированию

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

Класс имеет следующие внутренние атрибуты:

  • self._end_of_word_token - это специальный символ _, обозначающий конец слова при посимвольной токенизации;

  • self._storage - словарь для хранения буквы-токена и ее идентификатора, который на данном этапе должен быть заполнен специальным символом и его идентификатором равным 0.

Important

Оба эти атрибута являются защищенными, то есть обращение к ним за пределами методов этого класса не предполагается.

Шаг 1.1. Токенизировать заданную последовательность

Реализуйте метод lab_3_generate_by_ngrams.main.TextProcessor._tokenize(), который позволяет разбить текст на токены. Текст должен быть приведен к нижнему регистру и очищен от знаков препинания и цифр. Токеном в данном случае является один буквенный символ. В качестве разделителя между словами используется end_of_word_token.

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

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

Note

Разделитель добавляется после последнего слова, если текст заканчивается пробелом или знаком препинания. В противном случае, разделитель после последнего слова не добавляется.

Например, строка 'She is happy. He is happy.' должна быть токенизирована следующим образом: ('s', 'h', 'e', '_', 'i', 's', '_', 'h', 'a', 'p', 'p', 'y', '_', 'h', 'e', '_', 'i', 's', '_', 'h', 'a', 'p', 'p', 'y', '_'),

Строка 'She is happy. He is happy' токенизируется так: ('s', 'h', 'e', '_', 'i', 's', '_', 'h', 'a', 'p', 'p', 'y', '_', 'h', 'e', '_', 'i', 's', '_', 'h', 'a', 'p', 'p', 'y')

Note

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

Шаг 1.2. Добавить букву в хранилище

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

Для этого реализуйте метод lab_3_generate_by_ngrams.main.TextProcessor._put().

Note

Идентификатор - значение, которое однозначно указывает на токен и равно длине _storage (атрибут объекта данного класса) на момент добавления буквы. Идентификатор специального символа _ принимает значение 0.

Правила корректного заполнения хранилища:

  • Идентификаторы уникальны и однозначно указывают на токен (например, при добавлении нового токена можно использовать длину хранилища _storage).

  • Для одной и той же буквы существует ровно один идентификатор;

  • Одинаковых идентификаторов у двух разных букв быть не может;

  • Если буква уже существовала в хранилище, идентификатор остается прежним;

  • Идентификатор специального символа _ должен принимать значение 0.

Например, если на вход подается буква 's', то хранилище будет выглядеть следующим образом - {'_': 0, 's': 1}.

Note

Если на вход подается некорректное значение (аргумент неправильного типа, то есть не строка, или длина строки отлична от 1), возвращается None.

Important

Данный метод является защищенным - его использование за пределами методов класса не предполагается.

Шаг 1.3. Получить идентификатор буквы

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

Для этого реализуйте метод lab_3_generate_by_ngrams.main.TextProcessor.get_id().

Например, в хранилище вида {'_': 0, 's': 1} для 's' метод вернет идентификатор 1.

Note

Если на вход подается некорректное значение аргумента (то есть тип аргумента не строка), или буква отсутствует в хранилище, возвращается None.

Шаг 1.4. Получить букву по идентификатору

Теперь сделаем обратный процесс. Для декодирования, реализуйте метод lab_3_generate_by_ngrams.main.TextProcessor.get_token(), который получает букву по заданному идентификатору.

Например, в хранилище вида {'_': 0, 's': 1} для идентификатора 1 метод вернет 's'.

Note

Если на вход подается неизвестный (отсутствует в хранилище) или некорректный (не соответствует типу данных int) идентификатор, возвращается None.

Шаг 1.5. Закодировать текст

Реализуйте метод lab_3_generate_by_ngrams.main.TextProcessor.encode(), который кодирует текст. Он обязательно должен вызывать методы lab_3_generate_by_ngrams.main.TextProcessor._tokenize(), lab_3_generate_by_ngrams.main.TextProcessor._put() и lab_3_generate_by_ngrams.main.TextProcessor.get_id().

Например, возьмем текст "She is happy. He is happy." и заполним по нему хранилище: {'_': 0, 's': 1, 'h': 2, 'e': 3, 'i': 4, 'a': 5, 'p': 6, 'y': 7}. В результате кодирования текста выше должен получиться кортеж, в котором каждый элемент соответствует идентификатору буквы из хранилища _storage:

encoded_corpus = (1, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0, 2, 3, 0, 4, 1, 0, 2, 5, 6,
                  6, 7, 0)

Note

Если на вход подаются некорректные значения (текст не является строкой или строка пустая), возвращается None. Если какой-либо из методов, который вызывается в данном методе, возвращает None, метод также должен вернуть None.

Шаг 1.6. Декодировать текст в токенизированную последовательность

Теперь, когда у нас есть выделенные токены и присвоенные им числовые идентификаторы, мы можем декодировать любую последовательность.

Реализуйте метод lab_3_generate_by_ngrams.main.TextProcessor._decode(), который позволяет преобразовать закодированный текст в кортеж, состоящий из буквенных и специальных символов. Метод обязательно должен вызывать lab_3_generate_by_ngrams.main.TextProcessor.get_token().

Например, для закодированного корпуса (1, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0) у вас должен получиться кортеж следующего вида:

decoded_corpus = ('s', 'h', 'e', '_', 'i', 's', '_', 'h', 'a', 'p', 'p', 'y', '_',
                  'h', 'e', '_', 'i', 's', '_', 'h', 'a', 'p', 'p', 'y', '_')

Note

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

Important

Данный метод является защищенным - его использование за пределами методов класса не предполагается.

Шаг 1.7. Декодировать текст в строковый формат

Реализуйте метод lab_3_generate_by_ngrams.main.TextProcessor._postprocess_decoded_text(), который позволяет перейти от токенизированного текста в формате кортежа к тексту в строковом формате.

При этом на выходе строка должна соответствовать следующим требованиям:

  1. Строка должна начинаться с заглавной буквы.

  2. В конце строки ставится ..

Important

Специальные токены конца слова должны быть конвертированы в пробелы. При этом пробел после последнего слова в тексте ставить не нужно.

Например, для декодированного на предыдущем шаге корпуса ('s', 'h', 'e', '_', 'i', 's', '_', 'h', 'a', 'p', 'p', 'y', '_', 'h', 'e', '_', 'i', 's', '_', 'h', 'a', 'p', 'p', 'y', '_') должен получиться следующий текст: She is happy he is happy..

Note

Если на вход подаются некорректные значения (токенизированный текст не является кортежем или кортеж пустой), возвращается None.

Important

Данный метод является защищенным - его использование за пределами методов класса не предполагается.

Шаг 1.8. Декодировать текст

Наконец, применим полную логику перехода от закодированного текста к декодированному.

Реализуйте метод lab_3_generate_by_ngrams.main.TextProcessor.decode(), который преобразует закодированный текст - кортеж с идентификаторами - в текст в виде строки.

Метод обязательно должен вызывать методы lab_3_generate_by_ngrams.main.TextProcessor._decode() и lab_3_generate_by_ngrams.main.TextProcessor._postprocess_decoded_text().

Например, для закодированного корпуса (1, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0) у вас должен получиться следующий текст: She is happy he is happy..

Note

Если на вход подаются некорректные значения (закодированный текст не является кортежем или отсутствует), возвращается None. Если какой-либо из использованных методов возвращает None, необходимо так же вернуть None.

Данный метод является публичным и инкапсулирует в себе внутреннюю логику обработки текста.

Шаг 1.9. Получить специальный токен

В данном классе атрибут self._end_of_word_token является защищенным: мы не хотим допустить его изменения пользователем. Однако узнать, какой именно токен используется для разделения слов, все-таки иногда необходимо.

Для этого реализуем метод lab_3_generate_by_ngrams.main.TextProcessor.get_end_of_word_token(), который возвращает значение внутреннего атрибута self._end_of_word_token.

Шаг 1.10. Продемонстрировать результаты в start.py

Important

Выполнение Шага 1 соответствует 4 баллам.

Продемонстрируйте результат кодирования и декодирования в функции main() модуля start.py, используя текст на английском языке (переменная text). В качестве специального токена конца слова используйте строку '_'.

Шаг 2. Создать структуру для хранения и обработки n-грамм

Теперь у Вас есть все, чтобы создать свою простейшую языковую модель на основе n-грамм для решения задачи генерации текста.

Класс lab_3_generate_by_ngrams.main.NGramLanguageModel позволяет собрать n-граммы из заданного закодированного текста и сгенерировать следующую букву последовательности.

Допустим, у нас есть закодированный текст, который выглядит следующим образом: text = (1, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0).

Если нам необходимо заполнить NGramLanguageModel с N=2, то мы получим следующие биграммы: ((1, 2), (2, 3), (3, 0), (0, 4), (4, 1), (1, 0), (0, 2), (2, 5), (5, 6), (6, 6), (6, 7), (7, 0), (0, 2), (2, 3), (3, 0), (0, 4), (4, 1), (1, 0), (0, 2), (2, 5), (5, 6), (6, 6), (6, 7), (7, 0)). Если N=3, то мы получим следующие триграммы: ((1, 2, 3), (2, 3, 0), (3, 0, 4), (0, 4, 1), (4, 1, 0), (1, 0, 2), (0, 2, 5), (2, 5, 6), (5, 6, 6), (6, 6, 7), (6, 7, 0), (7, 0, 2), (0, 2, 3), (2, 3, 0), (3, 0, 4), (0, 4, 1), (4, 1, 0), (1, 0, 2), (0, 2, 5), (2, 5, 6), (5, 6, 6), (6, 6, 7), (6, 7, 0)).

Шаг 2.1. Объявить сущность языковой модели

Перейдем к реализации абстракции, которая хранит в себе языковое представление в виде n-грамм и на их основе предсказывает следующий токен.

Создайте класс lab_3_generate_by_ngrams.main.NGramLanguageModel.

Описание внутренних атрибутов:

  • self._encoded_corpus - закодированный текст;

  • self._n_gram_size - размер n–грамм, который в данном случае должен принимать значения от 2 до 5;

  • self._n_gram_frequencies - частотный словарь n–грамм, в котором ключами выступают n-граммы, а значениями - вероятность появления последнего токена данной n-граммы в контексте, задаваемом n-граммой.

На момент инициализации атрибут self._n_gram_frequencies` является пустым словарем, его заполнение произойдет далее.

Шаг 2.2. Извлечь n-граммы из закодированного корпуса

Как уже упоминалось, каждый экземпляр класса NGramLanguageModel содержит языковое представление в виде n-грамм. Для этого нам необходимо извлечь из корпуса n-граммы заданного размера.

Реализуйте метод lab_3_generate_by_ngrams.main.NGramLanguageModel._extract_n_grams(), который извлекает из закодированного корпуса n-граммы, размер которых указан в атрибуте self._n_gram_size.

Например, для закодированного корпуса (1, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0) при n_gram_size = 2 метод должен вернуть следующий кортеж: ((1, 2), (2, 3), (3, 0), (0, 4), (4, 1), (1, 0), (0, 2), (2, 5), (5, 6), (6, 6), (6, 7), (7, 0), (0, 2), (2, 3), (3, 0), (0, 4), (4, 1), (1, 0), (0, 2), (2, 5), (5, 6), (6, 6), (6, 7), (7, 0)).

Note

Если на вход подаются некорректные значения (корпус не является кортежем или кортеж пустой), возвращается None.

Important

Данный метод является защищенным - его использование за пределами методов класса не предполагается.

Шаг 2.3. Создать частотный словарь n-грамм

Реализуйте метод lab_3_generate_by_ngrams.main.NGramLanguageModel.build(), который заполняет атрибут self._n_gram_frequencies, где ключом является n-грамма, а значением - вероятность появления последнего токена данной n-граммы в контексте. Метод обязательно должен вызывать lab_3_generate_by_ngrams.main.NGramLanguageModel._extract_n_grams().

В данной работе вам необходимо научиться считать вероятность появления последнего токена с учетом некоторого контекста. Давайте посмотрим на общий вид вычисления данной вероятности:

\[{P(w_{n}|w_{n−N+1}...w_{n−1})} = \frac{P(w_{n},w_{n−N+1}...w_{n−1})}{P(w_{n−N+1}...w_{n−1})}\]

Для понимания указанной формулы необходимо знать, что такое условная вероятность. Условная вероятность \({P(w_{n}|w_{n−N+1}...w_{n−1})}\) – вероятность наступления одного события (в данном случае события \(P(w_{n})\)) при условии, что другое событие (то есть событие \(P(w_{n−N+1}...w_{n−1})\)) уже произошло.

В данном случае:

  • n - длина заданной последовательности;

  • N - размер n-грамм.

Предположим, что у нас есть последовательность (4, 3, 2, 1, 7) и мы хотим узнать вероятность того, что следующий токен (5). Тогда контекст для заданной последовательности при N=3 имеет следующий вид: (1, 7). Необходимо найти \({P((5)|(1, 7))}\).

Как мы можем оценить данную вероятность?

Оценка максимального правдоподобия (MLE) - метод, который позволяет оценить вероятность. Мы получаем оценку для параметров модели n-грамм, нормализуя значения из корпуса, чтобы они находились в диапазоне от 0 до 1.

Таким образом, в общем виде формула расчёта вероятности выглядит следующим образом:

\[{P(w_{n}|w_{n−1})} = \frac{С(w_{n−1},w_{n})}{С(w_{n−1})}\]

  • \(С(w_{n−1},w_{n})\) - количество вхождений n-граммы, то есть её абсолютная частота;

  • \(С(w_{n−1})\) - сколько раз в корпусе встречаются n-граммы, имеющие такое же начало, то есть такие же первые N-1 символов.

То есть, чтобы вычислить вероятность токена (5) с учетом предыдущего контекста (1, 7), необходимо вычислить количество триграмм (1, 7, 5) и нормализовать по сумме всех триграмм, которые также начинаются с контекста (1, 7).

\[{P((5)|(1, 7))} = \frac{С((1, 7, 5))}{С((1, 7))}\]

Например, дан следующий набор триграмм:

n_grams = (
     (1, 2, 3), (2, 3, 0), (3, 0, 4), (0, 4, 1), (4, 1, 0),
     (1, 0, 2), (0, 2, 5), (2, 5, 6), (5, 6, 6), (6, 6, 7),
     (6, 7, 0), (7, 0, 2), (0, 2, 3), (2, 3, 0), (3, 0, 4),
     (0, 4, 1), (4, 1, 0), (1, 0, 2), (0, 2, 5), (2, 5, 6),
     (5, 6, 6), (6, 6, 7), (6, 7, 0))

Тогда, для триграммы (0, 2, 5) значение \(P(w_{1},w_{2})\) равно 2, так как данная n-грамма встретилась только один раз в кортеже со всеми n-граммами. Значение \(P(w_{1})\) равно 3, так как именно столько раз n-грамма (0, 2), имеющая такое же начало, встретилась среди всех n-грамм, содержащих первые N-1 символов.

Следовательно, для n-граммы (0, 2, 5) частотный словарь будет заполнен следующем образом:

frequencies = {
     (0, 2, 5): 0.6666666666666666}

Например, для закодированного корпуса (1, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0, 2, 3, 0, 4, 1, 0, 2, 5, 6, 6, 7, 0) при n_gram_size = 3 должен получиться частотный словарь вида:

frequencies = {
     (1, 2, 3): 1.0,
     (2, 3, 0): 1.0,
     (3, 0, 4): 1.0,
     (0, 4, 1): 1.0,
     (4, 1, 0): 1.0,
     (1, 0, 2): 1.0,
     (0, 2, 5): 0.6666666666666666,
     (2, 5, 6): 1.0,
     (5, 6, 6): 1.0,
     (6, 6, 7): 1.0,
     (6, 7, 0): 1.0,
     (7, 0, 2): 1.0,
     (0, 2, 3): 0.3333333333333333}

Note

Если метод принимает на вход закодированный текст не в виде кортежа или если кортеж пустой, а также, если некорректно извлекаются n-граммы, то возвращается 1, если происходит корректное заполнение частотного словаря, метод возвращает 0.

Продемонстрируйте результат работы данного метода в функции main() модуля start.py.

Шаг 2.4. Получить размер n-грамм

В данном классе атрибут self._n_gram_size является защищенным: мы не хотим допустить его изменения пользователем. Однако узнать, какой именно токен используется для разделения слов, все-таки иногда необходимо.

Реализуйте метод lab_3_generate_by_ngrams.main.NGramLanguageModel.get_n_gram_size(), который возвращает значение внутреннего атрибута self._n_gram_size.

Шаг 2.5. Сгенерировать следующий токен

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

Реализуйте метод lab_3_generate_by_ngrams.main.NGramLanguageModel.generate_next_token().

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

Например, для n-граммы (1, 2, 3, 0), контекстом является (2, 3, 0).

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

Например, метод принимает на вход следующую последовательность: (7, 5, 6, 6). Для данной последовательности при n_gram_size = 3 контекстом является (6, 6).

Пусть мы имеем частотный словарь следующего вида:

frequencies = {
     (1, 2, 3): 1.0,
     (2, 3, 0): 1.0,
     (3, 0, 4): 1.0,
     (0, 4, 1): 1.0,
     (4, 1, 0): 1.0,
     (1, 0, 2): 1.0,
     (0, 2, 5): 0.6666666666666666,
     (2, 5, 6): 1.0,
     (5, 6, 6): 1.0,
     (6, 6, 7): 1.0,
     (6, 7, 0): 1.0,
     (7, 0, 2): 1.0,
     (0, 2, 3): 0.3333333333333333}

Тогда, у нас есть только одна n-грамма, а именно (6, 6, 7), с частотой 1.0, в которой присутствует контекст (6, 6).

Метод должен вернуть следующий словарь: {7: 1.0}, в котором ключ - буква, найденная по контексту (6, 6), а значение - частота n-граммы (6, 6, 7).

В словаре таких пар ключ-значение может быть несколько, поэтому необходимо произвести двойную сортировку пар: по значению и по ключу в порядке убывания.

Note

Если введенная последовательность не является кортежем, кортеж пустой или неправильная длина последовательности (длина последовательности меньше, чем длина контекста), возвращается None.

Шаг 3. Создать жадный генератор текста

Шаг 3.1. Объявить сущность генератора

Теперь мы полностью готовы к реализации генерации текста. Начнем с самого простого принципа генерации.

Жадный алгоритм - это алгоритм генерации, в котором следующим токеном всегда выбирается наиболее вероятный элемент, предполагая, что конечное решение также будет наиболее вероятный.

Для того, чтобы сгенерировать последовательности заданной длины, создайте класс lab_3_generate_by_ngrams.main.GreedyTextGenerator.

Описание внутренних атрибутов:

  • self._model - экземпляр класса NGramLanguageModel;

  • self._text_processor - экземпляр класса TextProcessor.

Шаг 3.2. Сгенерировать последовательность

Реализуйте метод lab_3_generate_by_ngrams.main.GreedyTextGenerator.run(), который генерирует последовательность указанной длины.

Прежде чем создать жадный алгоритм генерации, необходимо сделать несколько подготовительных преобразований:

  • Закодировать заданную последовательность (prompt). Для этого используйте экземпляр класса TextProcessor, который хранится в соответствующем атрибуте;

  • Получить из языковой модели контекст для генерации. Напоминаем, что длина контекста зависит от размера n-грамм.

Алгоритм создания жадного генератора:

  1. Получить все буквы-кандидаты по контексту. Используйте уже реализованный метод класса NGramLanguageModel.

  2. Сгенерировать указанное количество букв, каждый раз выбирая кандидата с наибольшей частотой из словаря и добавляя его к последовательности.

Следует учесть, что:

  1. В случае, если буквы-кандидаты не были найдены, то генерация прекращается, чтобы избежать процесса зацикливания.

  2. С добавлением новой буквы к исходной последовательности, контекст изменяется, так как меняется последовательность.

Метод возвращает сгенерированный текст в виде строки.

Note

Если на вход подаются некорректные значения (длина последовательности не типа int, заданная последовательность не является строкой или последовательность пустая), если вызываемые методы возвращают значение None, метод возвращает значение None.

В данном методе необходимо использовать методы lab_3_generate_by_ngrams.main.TextProcessor.encode() и lab_3_generate_by_ngrams.main.TextProcessor.decode(), а также методы lab_3_generate_by_ngrams.main.NGramLanguageModel.get_n_gram_size() и lab_3_generate_by_ngrams.main.NGramLanguageModel.generate_next_token().

Например, при следующих значениях:

seq_len = 6
prompt = 'She is'

метод возвращает следующий результат 'She is happy.'.

Шаг 3.3. Продемонстрировать результаты в start.py

Important

Выполнение Шагов 2 и 3 соответствует 6 баллам.

Продемонстрируйте результат работы жадного алгоритма генерации текста в функции main() модуля start.py. Попробуйте в качестве затравки использовать ‘Vernon’. Пусть размер n-грамм будет равен 7, а длина последовательности - 51 .

Шаг 5. Создать генератор текста на основе алгоритма Beam Search

Шаг 5.1. Объявить сущность генератора

Теперь у Вас есть все, чтобы создать генератор. Для этого создайте класс lab_3_generate_by_ngrams.main.BeamSearchTextGenerator.

Описание внутренних атрибутов класса:

  • self._text_processor - экземпляр класса TextProcessor;

  • self._beam_width - ширина луча;

  • self.beam_searchers - экземпляр класса BeamSearcher. В качестве аргументов экземпляр класса принимает значение атрибута self._beam_width и языковую модель.

Important

Экземпляры инициализируются в __init__.

Шаг 5.2. Получить следующий токен

Ваша задача - создать генератор на основе алгоритма Beam Search.

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

Реализуйте метод lab_3_generate_by_ngrams.main.BeamSearchTextGenerator._get_next_token(). Он обязательно должен использовать метод lab_3_generate_by_ngrams.main.BeamSearcher.get_next_token().

Note

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

Шаг 5.3. Сгенерировать последовательность

Реализуйте метод lab_3_generate_by_ngrams.main.BeamSearchTextGenerator.run(), который принимает на вход количество букв для генерации и начало последовательности в строковом виде. Данный метод позволяет получить готовый сгенерированный текст.

Создание генератора:

  1. Создайте словарь с последовательностями-кандидатами, ключом которого изначально является закодированное начало последовательности, а значением - частота закодированной последовательности, принимающая значение 0.0.

  2. Получите топ-n (где n - ширина луча) букв-кандидатов для продолжения текущей последовательности.

  3. Получите все вариантов последовательностей для дальнейшей генерации. Используйте для реализации данного пункта экземпляр класса BeamSearcher.

  4. Фильтрация последовательностей, то есть удаление всех тех последовательностей, которые не являются топ-n (где n - ширина луча). Теперь это новые последовательности-кандидаты. Используйте для реализации данного пункта нулевой экземпляр класса BeamSearcher.

  5. Повторяйте шаги 3-5 до тех пор, пока не будет достигнута желаемая длина сгенерированной последовательности.

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

  7. Декодируйте наилучшую последовательность в текст.

В данном методе необходимо использовать методы lab_3_generate_by_ngrams.main.TextProcessor.encode() и lab_3_generate_by_ngrams.main.TextProcessor.decode(), а также методы lab_3_generate_by_ngrams.main.BeamSearcher.get_next_token(), lab_3_generate_by_ngrams.main.BeamSearcher.continue_sequence() и lab_3_generate_by_ngrams.main.BeamSearcher.prune_sequence_candidates().

Note

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

Например, метод принимает на вход длину генерируемой последовательности равную 1 и начало последовательности 'She i'.

Мы имеем частотный словарь для триграмм и значение ширины луча:

frequencies = {
     (1, 2, 3): 1.0,
     (2, 3, 0): 1.0,
     (3, 0, 4): 1.0,
     (0, 4, 1): 1.0,
     (4, 1, 0): 1.0,
     (1, 0, 2): 1.0,
     (0, 2, 5): 0.6666666666666666,
     (2, 5, 6): 1.0,
     (5, 6, 6): 1.0,
     (6, 6, 7): 1.0,
     (6, 7, 0): 1.0,
     (7, 0, 2): 1.0,
     (0, 2, 3): 0.3333333333333333}
beam_width = 3

Закодированная начальная последовательность имеет следующий вид: (1, 2, 3, 0, 4). Следовательно, модель должна выявить следующий контекст: (0, 4).

Из частотного словаря получаем, что кандидат, чтобы продолжить последовательность, у нас один: [(1, 1.0)].

В таком случае, текущим кандидатом является последовательность (1, 2, 3, 0, 4, 1). Так как кандидат один, то нет кандидатов для удаления (в случае, если кандидатов было четыре, то после их сортировки необходимо было оставить количество, заданное шириной луча).

Метод возвращает следующий результат 'She is.'.

Шаг 5.4. Продемонстрировать результаты в start.py

Important

Выполнение Шагов 4 и 5 соответствует 8 баллам.

Продемонстрируйте результат работы алгоритма лучевого поиска в функции main() модуля start.py. Попробуйте в качестве затравки использовать 'Vernon'. Пусть размер n-грамм будет равен 7, а длина последовательности - 56.

Шаг 6. Заполнить хранилище новыми n-граммами

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

Вам необходимо расширить класс TextProcessor новым методом lab_3_generate_by_ngrams.main.TextProcessor.fill_from_ngrams().

Получая на вход словарь из файла с языковым профилем английского языка, вам необходимо:

  1. Отобрать только те n-граммы, длина которых равна 1.

  2. Если n-грамма является буквой, то необходимо этой буквой пополнить хранилище _storage.

В данном методе необходимо использовать метод lab_3_generate_by_ngrams.main.TextProcessor._put()

Note

Если на вход подается некорректное значение (аргумент неправильного типа, то есть не словарь, или словарь пустой), возвращается None.

Например, если метод принимает на вход следующий словарь:

content = {
     "freq": {
             "h ap": 8629,
             " ape": 3042,
             "apex": 624}}

то в результате должно получиться хранилище, заполненное следующим образом:

storage = {'_': 0, 'h': 1, 'a': 2, 'p': 3, 'e': 4, 'x': 5}

Шаг 7. Установить значение атрибута self._n_gram_frequencies

Вам необходимо расширить класс NGramLanguageModel новым методом lab_3_generate_by_ngrams.main.NGramLanguageModel.set_n_grams().

Данный метод позволяет присвоить атрибуту self._n_gram_frequencies получаемое на вход значение.

Note

Если на вход подается некорректное значение (аргумент неправильного типа, то есть не словарь, или словарь пустой), возвращается None.

Шаг 8. Создать генератор текста на основе алгоритма BackOff

Теперь у Вас есть все, чтобы реализовать последний в рамках данной лабораторной алгоритм генерации текста, а именно алгоритм BackOff.

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

Шаг 8.1. Объявить сущность по расширению языковой модели на основе n-грамм

Создайте класс lab_3_generate_by_ngrams.main.NGramLanguageModelReader.

Описание внутренних атрибутов класса:

  • self._json_path - путь к файлу с расширением .json, который содержит языковой профиль английского языка (en_own.json);

  • self._eow_token - специальный символ конца слова в формате строки;

  • self._content - содержимое файла с расширением .json. Для чтения и сохранения файлов данного типа используйте стандартный модуль json;

  • self._text_processor - экземпляр класса TextProcessor.

На данном шаге Вам также необходимо заполнить хранилище _storage, используя содержимое файла с расширением .json, которое хранится в атрибуте self._content.

Шаг 8.1.1 Получить экземпляр класса NGramLanguageModel

Реализуйте метод lab_3_generate_by_ngrams.main.NGramLanguageModelReader.load(), который позволяет получить языковую модель для определенного размера n-грамм.

Во-первых, необходимо каждую n-грамму, полученную из файла .json, привести к определенному формату:

  • Заменить пробельные символы на специальный символ конца слова;

  • Выбрать только те токены в n-грамме, которые являются буквой или специальным символом;

  • Привести к нижнему регистру.

Если заданный размер n-грамм соотносится с длиной n-грамм из файла, то необходимо кодировать n-грамму из языкового профиля.

Создайте частотный словарь с n-граммами из файла и вероятностями появления последнего токена данной n-граммы в контексте, задаваемом n-граммой. Воспользуйтесь формулой условной вероятности:

\[\frac{P(w_{1},w_{2})}{P(w_{1})}\]

  • \(P(w_{1},w_{2})\) - количество вхождений n-граммы, то есть её абсолютная частота;

  • \(P(w_{1})\) - сколько раз в корпусе встречаются n-граммы, имеющие такое же начало, то есть такие же первые N-1 символов.

Создайте экземпляр класса NGramLanguageModel со следующими аргументами:

  • Закодированный текст, который принимает значение None;

  • Размер n-грамм.

Установите значение защищенного атрибута self._n_gram_frequencies класса NGramLanguageModel

Note

Если на вход подается некорректное значение размера n-грамм (значение не относится к типу int, аргумент не содержит никакого значения или размер находится за пределами от 2 до 5), то метод возвращает None.

Метод обязательно должен вызывать методы lab_3_generate_by_ngrams.main.TextProcessor.get_id() и lab_3_generate_by_ngrams.main.NGramLanguageModel.set_n_grams().

Шаг 8.1.2 Получить экземпляр класса TextProcessor

В данном классе атрибут self._text_processor является защищенным: мы не хотим допустить его изменения пользователем. Однако узнать, какой именно токен используется для разделения слов, все-таки иногда необходимо.

Для этого реализуем метод lab_3_generate_by_ngrams.main.NGramLanguageModelReader.get_text_processor(), который возвращает значение внутреннего атрибута self._text_processor. Метод не принимает никаких аргументов.

Шаг 8.2. Объявить сущность по созданию BackOff генератора

Создайте класс lab_3_generate_by_ngrams.main.BackOffGenerator.

Описание внутренних атрибутов класса:

  • self._language_models - словарь, ключом которого является размер n–грамм, а значением - экземпляр класса NGramLanguageModel. Экземпляр класса вы можете получить из списка language_models;

  • self._text_processor - экземпляр класса TextProcessor.

Шаг 8.2.1 Получить буквы-кандидаты для генерации

Реализуйте метод lab_3_generate_by_ngrams.main.BackOffGenerator._get_next_token(), который возвращает словарь, ключами которого являются буквы-кандидаты, а значениями - частоты n-грамм, из которых данная буква была выявлена по контексту. В данном методе необходимо использовать методы lab_3_generate_by_ngrams.main.NGramLanguageModel.get_n_gram_size() и lab_3_generate_by_ngrams.main.NGramLanguageModel.generate_next_token().

Вам необходимо:

  1. Получить все возможные размеры n–грамм, используя внутренний атрибут данного класса, и отсортировать его в порядке убывания N–грамм.

  2. Для каждой n–граммы получить экземпляр класса NGramLanguageModel.

  3. Получить контекст c помощью языковой модели для дальнейшей генерации буквы-кандидата.

  4. Получить все буквы-кандидаты для генерации в виде словаря.

  5. Перейти к n–грамме меньшего размера и повторить шаги 2-4.

Note

Если на вход подается некорректное значение аргумента (аргумента не является кортежем или кортеж пустой), то метод возвращает None. Если список размеров N–грамм пустой или вызываемые методы возвращают None, то метод также возвращает None

Important

Данный метод является защищенным - его использование за пределами методов класса не предполагается.

Шаг 8.2.2 Генерация последовательности

Important

Выполнение Шагов 6-8 соответствует 10 баллам.

Реализуйте метод lab_3_generate_by_ngrams.main.BackOffGenerator.run(), который принимает на вход длину последовательности для генерации и начало последовательности в строковом виде. В данном методе необходимо использовать методы lab_3_generate_by_ngrams.main.TextProcessor.encode() и lab_3_generate_by_ngrams.main.TextProcessor.decode(), а также метод lab_3_generate_by_ngrams.main.BackOffGenerator._get_next_token().

Перед тем как непосредственно приступить к генерации, необходимо закодировать заданную последовательность (prompt).

Вам следует:

  1. Получить все буквы-кандидаты для генерации. Используйте уже реализованный метод класса BackOffGenerator.

  2. Сгенерировать указанное количество букв, каждый раз выбирая кандидата с наибольшей вероятностью из словаря и добавляя его к последовательности.

Следует учесть, что в случае если буквы-кандидаты не были найдены, то генерация прекращается. Метод возвращает сгенерированный текст в виде строки.

Note

Если на вход подаются некорректные значения (длина последовательности не типа int, заданная последовательность не является строкой или последовательность пустая), если вызываемые методы возвращают значение None, возвращается None.

Полезные ссылки