马尔可夫链文本生成

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个班，节点，ConcreteTrie，和驱动程序

当然，ConcreteTrie类不是传统意义上的特里。下面是它如何工作的：

鉴于这些句子K = 2：

这是猫，还有两条狗。

我生成节点Th，嗨，是，... + ...，gs，s。 这些节点中的每一个都有跟随它们的字母的子节点。例如，节点Th将有孩子我和e。我在这些节点的每一个中保持计数，以便稍后可以生成选择下一个字母的概率。

我的问题：

首先，什么是最有效的方式来完成这个项目？我的解决方案似乎非常快，但我真的很想把我教授的袜子关掉。 （在我的最后一个项目中，编辑距离问题的变体，我做了一个A *，一个遗传算法，一个BFS和模拟退火 - 我知道这个问题是NP-Hard）。这项任务的重点？它似乎并不涉及我们在课堂上所讲的很多内容。我们应该学什么？

Answer 1

关于此作业与您在类（您的第二个问题）中涵盖的内容的相关性。 ''数据结构'类的想法是向学生展示在CS中经常遇到的很多结构：列表，堆栈，队列，哈希，各种类型的树，大图，各种信条和贪婪矩阵等并提供一些有关他们的常见实施，他们的长处和弱点以及他们各种应用领域的见解。
由于大多数任何游戏/谜题/问题都可以映射到这些结构的一些集合，所以不缺少课程和作业的主题。 您的课程似乎很有趣，因为虽然保持对这些结构的一些关注，您也有机会发现真正的应用程序。
举例来说，“猫和两只狗”是一种简单的伪装形式，是对语言学应用统计模型的介绍。你的好奇心和动机促使你与马尔科夫模型建立了联系，这是一件好事，因为在毕业前你有机会再次遇到“马尔科夫”;-)并且肯定是在CS或相关领域的职业生涯中。所以，是的！可能似乎，你butterflying各地的许多应用程序等，但只要你得到什么结构和算法，在特定情况下选择的感觉，你不会浪费你的时间！

现在，上可能的方法来分配
的特里一些提示似乎是这类问题的自然支持。也许你可以问自己，但是如果你不得不索引整本书而不是这个简短的句子，这种方法会如何扩展。它看起来大部分是线性的，尽管这取决于trie中每个选项（对于这个二阶马尔可夫链）如何选择：随着选择数量的增加，选择一条路径可能变得效率较低。
建立索引的一个可能的替代存储是stochatisc矩阵（如果只有稀疏矩阵，在统计数据收集过程中，当您将每行或列进行归一化时最终变为随机数在你设置）总结为一（100％）。这样一个矩阵大概是729 x 28，并且允许在单个操作中对两个字母的元组及其相关的下一个字母进行索引。 （我得到28包括“开始”和“停止”信号，细节...）
这种更有效的索引的成本是使用额外的空间。 空间明智线索是非常有效的，只有存储信三胞胎有效存在的组合，矩阵但浪费了一些空间（你会很不人口稀少结束打赌，即使索引更文字的“狗/猫”之句。）
这尺寸与CPU妥协是很常见的，但也有一些算法/结构在这两方面比别人更好somtimes ......此外，矩阵方法不会很好地扩展，大小wize ，如果问题改变为根据前面说的字母选择三个字符。
无论如何，也许可以查看矩阵作为替代实现。 尝试各种结构并了解为什么/他们比其他人更好（在特定任务的情况下）。
可以采取小的侧行程是基于字母对（或三元组）的概率来创建tag cloud：两个线索和基质包含所有必需的数据;具有所有有趣属性的矩阵可能更适合于此。
玩得开心！

Answer 2

您使用两字与字符的方法，但通常它应用到的话，因为输出将更有意义，如果我们只使用简单的发生器，你的情况）。

1）从我的角度来看你做得很好。但可能你应该尝试稍微随机选择下一个节点？例如。从5中选择随机节点最高。我的意思是，如果你总是选择具有最高概率的节点，你的输出字符串将会太统一。

2）我在我的大学完成了同样的作业。我认为这一点是展现给学生们马尔可夫链很强大，但没有发电机的应用程序域输出的广泛的研究将是可笑的