java - 马尔可夫链文本生成

Question

我们刚刚在我的数据结构类(class)中分配了一个新项目——使用马尔可夫链生成文本。

概览

给定一个输入文本文件，我们创建一个长度为 n 个字符的初始种子。我们将其添加到输出字符串中，并根据频率分析选择下一个字符。

This is the cat and there are two dogs.

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 的句子:

This is the cat and there are two dogs.

我生成节点 Th, hi, is, ... + ... , gs, s。这些节点中的每一个都有子节点，它们是跟随它们的字母。例如，节点 Th 将有 child i 和 e。我在每个节点中维护计数，以便稍后生成选择下一个字母的概率。

我的问题:

首先，完成这个项目最有效的方法是什么？我的解决方案似乎非常快，但我真的很想让我的教授大吃一惊。 (在我的上一个项目编辑距离问题的变体中，我做了一个 A*、一个遗传算法、一个 BFS 和模拟退火——我知道这个问题是 NP-Hard)

其次，这个作业的意义何在？它似乎与我们在类里面讲过的大部分内容并没有真正的关系。我们应该学习什么？

Answer 1

关于此作业与您在类里面所学内容的相关性(您的第二个问题)。 “数据结构”类(class)的理念是让学生了解 CS 中经常遇到的许多结构:列表、堆栈、队列、散列、各种类型的树、大图、各种矩阵信条和贪婪等，并提供一些关于它们的常见实现、它们的优点和缺点以及它们的各个应用领域的见解。
由于大多数游戏/谜题/问题都可以映射到这些结构中的某些集合，因此不乏可作为讲座和作业基础的主题。 你的类(class)看起来很有趣，因为在重点关注这些结构的同时，你也有机会发现真正的应用。
例如，“猫和两只狗”是对应用于语言学的统计模型的介绍。您的好奇心和动力促使您与马尔可夫模型建立联系，这是一件好事，因为您在毕业前很可能会再遇到“马尔可夫”几次；-)，而且肯定是在 CS 或相关领域的职业生涯中。所以，是的!您可能似乎在许多应用程序等方面游刃有余，但只要您了解在特定情况下选择何种结构和算法，你不是在浪费时间!

现在，关于可能的作业方法的一些提示
trie 似乎是对此类问题的自然支持。也许你可以问问自己，如果你必须索引整本书而不是这个短句，那么这种方法将如何扩展。这似乎主要是线性的，尽管这取决于在 trie 中的三个跃点上的每个选择(对于这个二阶马尔可夫链):随着选择数量的增加，选择路径的效率可能会降低。
构建索引的一种可能的替代存储是随机矩阵(实际上是一个“普通”矩阵，如果只是稀疏矩阵，在统计数据收集过程中，当您规范化每一行时最后变成随机矩阵 - 或者列 - 取决于您的设置)总和为一 (100%)。这样的矩阵大约为 729 x 28，并且允许在一次操作中对两个字母的元组及其相关的后续字母进行索引。 (我得到了 28 分，包括“开始”和“停止”信号，细节......)
这种更有效的索引的成本是使用额外的空间。 Space-wise trie 非常有效，只有效地存储字母三元组的组合，但是矩阵浪费了一些空间(你打赌最后它会非常稀疏，即使在索引很多之后比“狗/猫”句子更多的文字。)
这种大小与 CPU 的妥协 很常见，尽管某些算法/结构有时在这两个方面都比其他算法/结构更好......此外，矩阵方法不会很好地扩展，大小，如果问题已更改为基于前面三个字符的字母选择。
尽管如此，也许可以将矩阵视为替代实现。 尝试各种结构并了解为什么/哪里比其他结构更好(在特定任务的上下文中)非常符合本类(class)的精神。
您可以进行的一个小旅行是创建一个 tag cloud基于字母对(或三元组)的概率:trie 和矩阵都包含所有必要的数据；具有所有有趣属性的矩阵可能更适合这个。
玩得开心!