Марковская цепочка генерации текста

Question

Мы только что получили новый проект в моем классе структур данных - Генерация текста с цепями Маркова.

Обзор

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

Это кошка и две собаки.

Initial seed: "Th"
Possible next letters -- i, e, e
Therefore, probability of choosing i is 1/3, e is 2/3.

Now, say we choose i. We add "i" to the output string. Then our seed becomes
hi and the process continues.

Мое решение

У меня есть 3 класса, Node, ConcreteTrie и Driver

Конечно, класс ConcreteTrie не является традиционным пониманием Trie. Вот как это работает:

Учитывая предложение с k = 2:

Это кошка и две собаки.

Я генерирую Узлы Th, hi, is, ... + ..., gs, s. У каждого из этих узлов есть дочерние элементы, которые являются буквой, следующей за ними. Например, узел че будет иметь детей я и е. Я веду счет в каждом из этих узлов, чтобы впоследствии я мог сгенерировать вероятности для выбора следующей буквы.

Мой вопрос:

Прежде всего, каков наиболее эффективный способ завершить этот проект? Мое решение кажется очень быстрым, но я действительно хочу выбить носки моего профессора. (В моем последнем проекте «Вариант задачи« Редактировать расстояние ») я сделал A *, генетический алгоритм, BFS и имитированный отжиг - и я знаю, что проблема в NP-Hard»

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

Answer 1

О соответствии этого задания тому, что вы освещали в классе (Ваш второй вопрос). Идея класса ' структуры данных ' состоит в том, чтобы познакомить учащихся с очень многими структурами, часто встречающимися в CS: списки, стеки, очереди, хэши, деревья различных типов, графы в целом, матрицы различных вероисповеданий. жадность и т. д., а также дать представление об их общих реализациях, их сильных и слабых сторонах и, как правило, об их различных областях применения.
Поскольку почти любая игра / головоломка / проблема может быть сопоставлена ​​с некоторым набором этих структур, нет недостатка в предметах, на которых можно основывать лекции и задания. Ваш класс кажется интересным , потому что, не отвлекаясь от этих структур, вам также предоставляется возможность обнаружить реальные приложения .
Например, в «замаскированном виде» понятие «кошка и две собаки» представляет собой введение в статистические модели, применяемые в лингвистике. Ваше любопытство и мотивация побудили вас установить отношения с марковскими моделями, и это хорошо, потому что есть вероятность, что вы встретитесь с «Марковым» еще несколько раз до окончания школы ;-) и, безусловно, в профессиональной жизни в CS или смежных областях. Итак, да! может показаться тем, что вы работаете над многими приложениями и т. Д., Но пока вы чувствуете, какие структуры и алгоритмы выбрать в конкретных ситуациях, вы ' ты не тратишь время впустую!

Теперь несколько подсказок о возможных подходах к назначению
trie кажется естественной поддержкой для этого типа проблемы. Возможно, вы можете спросить себя, как бы масштабировался этот подход, если бы вам пришлось индексировать, скажем, целую книгу, а не это короткое предложение. Это кажется в основном линейным, хотя это зависит от того, как каждый выбор на трех переходах в дереве (для этой цепи Маркова 2-го порядка): с увеличением числа вариантов выбор пути может стать менее эффективным.
Возможным альтернативным хранилищем для построения индекса является матрица стохатисков (на самом деле «простая», если только разреженная матрица, в процессе сбора статистики, стала стохастической в ​​конце, когда вы нормализуете каждую строку или столбец) - в зависимости от того, как вы его настроили), чтобы суммировать до одного (100%). Такая матрица была бы примерно 729 x 28 и позволяла бы индексировать в одной операции двухбуквенный кортеж и связанную с ним следующую букву. (Я получил 28 за включение сигналов «старт» и «стоп», подробности ...)
Стоимость этой более эффективной индексации заключается в использовании дополнительного пространства. Пространственно Три очень эффективны, только эффективно сохраняя комбинации буквенных триплетов, матрица, однако, тратит некоторое пространство (вы держите пари, в конце концов, она будет очень малонаселенной, даже после индексации намного больше текст, который предложение "собака / кошка".)
Этот размер по сравнению с компромиссом ЦП очень распространен, хотя некоторые алгоритмы / структуры иногда лучше, чем другие по обоим показателям ... Более того, матричный подход не будет хорошо масштабироваться по размеру, если проблема была изменено основание для выбора букв из предыдущего, скажем, трех символов.
Тем не менее, возможно, рассмотрим матрицу как альтернативную реализацию. В духе этого класса очень важно попробовать различные структуры и понять, почему / где они лучше других (в контексте конкретной задачи).
Небольшое побочное действие, которое вы можете предпринять, - это создать облако тегов на основе вероятностей пар букв (или триплетов): и три, и матрица содержат все данные, необходимые для тот; Матрица со всеми ее интересными свойствами может быть более подходящей для этого.
Веселись!

Answer 2

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

1) С моей точки зрения у тебя все в порядке. Но, может быть, стоит попробовать немного рандомизировать выбор следующего узла? Например. выберите случайный узел из 5 самых высоких. Я имею в виду, если вы всегда выбираете узел с наибольшей вероятностью, ваша выходная строка будет слишком равномерной.

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