我们刚刚在我的数据结构类中分配了一个新项目 - 使用马尔可夫链生成文本.
概观
给定输入文本文件,我们创建长度为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,嗨,是...... + ...,gs,s.这些节点中的每个节点都有子节点,这些子节点跟随它们.例如,Node Th将有孩子i和e.我在每个节点中维护计数,以便稍后我可以生成选择下一个字母的概率.
我的问题:
首先,完成这个项目的最有效方法是什么？我的解决方案似乎非常快,但我真的想把我的教授打掉.(在我的上一个项目编辑距离问题的一个变体,我做了A*,遗传算法,BFS和模拟退火 - 我知道问题是NP-Hard)
第二,这项任务的重点是什么？它似乎与我们课堂上所涉及的很多内容无关.我们应该学习什么？
关于这项任务与你在课堂上所涉及的内容的相关性(你的第二个问题)." 数据结构 "类的想法是让学生接触CS中经常遇到的很多结构:列表,堆栈,队列,哈希,各种类型的树,大图,各种信条和贪婪的矩阵等等.提供一些洞察他们的常见实现,他们的优点和缺点,以及他们的各种应用领域.
由于大多数游戏/谜题/问题都可以映射到这些结构的某些组合,因此不乏基于讲座和作业的主题. 你的课看起来很有趣,因为在保持对这些结构的关注的同时,你也有机会发现真正的应用.
例如,以一种伪装的方式,"猫和两只狗"的东西是对语言学应用的统计模型的介绍.你的好奇心和动力促使你与马尔可夫模型建立关系,这是一件好事,因为你很有可能在毕业前会再见到"Markov"几次;-)当然还有CS或相关领域的职业生涯.所以,是的!它可能看起来,你butterflying各地的许多应用程序等,但只要你得到什么结构和算法,在特定情况下选择的感觉,你不会浪费你的时间!
现在,在可能的办法来分配的一些提示
的线索似乎是这类问题的自然支持.也许你可以问问自己,如果你不得不索引一整本书而不是这个简短的句子,这种方法会如何扩展.它似乎主要是线性的,虽然这取决于trie中三个跃点的每个选择(对于这个二阶马尔可夫链):随着选择数量的增加,选择一条路径可能会变得效率降低.
用于构建索引的可能的替代存储是stochatisc矩阵(实际上是"普通的",如果只有稀疏矩阵,在统计收集过程中,当你规范化每一行 - 或列时 - 最终随机转换 - 取决于你设置它up)总结为一(100%).这样的矩阵大约是729 x 28,并且允许在一次操作中索引两个字母的元组及其相关的后续字母.(包括"开始"和"停止"信号,我得到28,细节......)
这种更有效的索引的成本是使用额外的空间. 在空间方面,trie是非常有效的,只有存储有效字母三元组的组合,然而矩阵浪费了一些空间(你最后赌注它将非常稀疏,甚至在索引更多的文本后,"狗/ cat"句子."
这种大小与CPU的比较是非常普遍的,尽管有些算法/结构在两个方面都比其他算法/结构更好......而且,如果问题发生了变化,矩阵方法将无法很好地扩展,大小为wize以前面说的三个字符为基础选择字母.
尽管如此,也许可以将矩阵视为替代实现.尝试各种结构并了解他们为什么/在哪里比其他人更好(在特定任务的背景下),这是本课程的精神.
你可以把一个小方行是创建一个标签云基于字母对(或三胞胎)的概率:无论是特里和矩阵包含所有必要的数据; 具有所有有趣属性的矩阵可能更适合于此.
玩得开心!