用 N-gram 与马尔可夫链生成文本:Programming from A to Z 第 6 讲实战解析

原创2026-10-13 21:14:111,752 阅读
文章标签:教程文档示例工程

用 N-gram 与马尔可夫链生成文本:Programming from A to Z 第 6 讲实战解析

导读

本文围绕《Programming from A to Z》(ITP 课程)第 6 讲“Intro to Session 6: Markov Chains”展开,讲解如何把“马尔可夫链(Markov Chain)”这一宽泛的概率概念落地为一种基于 n-gram 与概率的算法化文本生成技术。你会掌握 n-gram 与马尔可夫链的核心原理、纯 JavaScript(p5.js)与 Processing 两套完整可运行的实现,以及如何用同一套思路从语料生成人名、频道名等创意文本。文中所有代码均取自当前仓库的 Coding Challenge 42.1 与 Coding Challenge 42.2 实际实现,可直接复制运行。

一、课程背景与第 6 讲定位

第 6 讲隶属于《Programming from A to Z》课程系列(课程索引),该课程专注于基于文本数据的程序化分析与生成:从按统计属性评估文本,到用概率方法自动生产文本,再到文本可视化,全部使用客户端与服务器端 JavaScript 完成。

本讲是该课程的 Session 6 开篇视频(video_number: 6.1),其定位是为整个第 6 讲定下技术基调——本讲后续内容全部围绕马尔可夫链展开。与它配套的还有:

从仓库结构看,Course 的 session06 说明 也把本讲的两个 Coding Challenge 实现列为官方源码入口,可见“n-gram + 马尔可夫链”正是第 6 讲的实践主轴。

说明:原文档列出的参考链接(如 Google Ngram Viewer、Chris Harrison 的 Web Trigrams、Victor Powell 的 Markov Chains Explained 等)均为外部资源,本文不再重复输出外部链接,只以仓库内源码与文档作为事实依据。

二、核心概念:n-gram 与马尔可夫链

2.1 马尔可夫链:只依赖“当前状态”的概率过程

马尔可夫链是一个宽泛的数学概念:它描述一类随机过程,其核心特征是**“下一状态只取决于当前状态”,与更早的历史无关**(即所谓的一阶无记忆性)。

在本讲与两个 Coding Challenge 中,马尔可夫链被用作生成文本的手段,具体建模方式是:

  • 把文本切成连续的 n-gram(n 个连续字符或词组成的块)作为“状态”;
  • 统计每个状态后面可能出现哪些“下一个字符(或词)”,构成转移候选;
  • 生成时从当前状态出发,按概率随机抽取候选的下一个字符,然后把窗口向后滑动一格,形成新的当前状态,如此循环。

用 CC_042.1 的 sketch.js 中的生成循环可以直观看到这个过程:

for (var i = 0; i < 100; i++) {
  var possibilities = ngrams[currentGram];
  if (!possibilities) {
    break;
  }
  var next = random(possibilities);   // 按概率随机抽取下一字符
  result += next;
  var len = result.length;
  currentGram = result.substring(len - order, len); // 窗口滑动
}

2.2 n-gram:马尔可夫链的状态单元

n-gram 是长度为 n 的连续片段。原文档强调本讲会用 n-gram 作为生成文本的状态单元:

  • n = 1(unigram):单字符,生成的文本几乎没有结构;
  • n = 2(bigram):两个字符,代码中的默认 order = 2 即此情形;
  • n = 3(trigram):三个字符,能更好地保持拼写与局部语序;
  • n 越大,生成结果越接近原文,但越缺少“创造性”,且状态空间随之增大。

在 CC_042.1 的 sketch.js 中,构建 n-gram 字典的核心代码如下:

for (var i = 0; i <= txt.length - order; i++) {
  var gram = txt.substring(i, i + order);
  if (!ngrams[gram]) {
    ngrams[gram] = [];
  }
  ngrams[gram].push(txt.charAt(i + order));
}

它用一个对象 ngrams 充当哈希表:键是长度为 order 的 gram,值是所有“出现在该 gram 之后”的字符数组。同一个字符在数组中出现多次,相当于该转移被重复计数——这正是概率的来源:出现越频繁的字符,被 random() 选中的概率越高。

三、完整实现一:基于单一文本的文本生成(CC 42.1)

3.1 运行环境与入口

CC_042.1 的 P5 版本 通过 CDN 引入 p5.js(https://cdn.jsdelivr.net/npm/p5@1.4.1/lib/p5.min.js),再加载 sketch.js,页面主体为空,全部交互由脚本创建:

<script language="javascript" type="text/javascript" src="https://cdn.jsdelivr.net/npm/p5@1.4.1/lib/p5.min.js"></script>
<script language="javascript" type="text/javascript" src="sketch.js"></script>

3.2 语料与参数

源码中内置了一段关于 unicorn(独角兽) 的英文百科式文本作为语料,同时声明了两个关键参数:

var txt = "The unicorn is a legendary creature ...";
var order = 2;      // n-gram 的 n,即状态长度
var ngrams = {};    // 状态 -> 后续字符数组 的映射
  • order:控制状态粒度,改大能提升连贯性,改小能增强随机性;
  • txt:语料来源,可以替换成任意文本。

3.3 三步算法流程

整个实现可以拆成三个清晰的阶段:

第一步:构建 n-gram 字典。用滑动窗口遍历全文,为每个 gram 收集其后继字符(代码见 2.2 节)。

第二步:生成文本。初始状态取文本开头的 order 个字符,然后循环 100 次执行“查表 → 随机选下一个字符 → 拼接 → 滑动窗口”。在 sketch.js 中,markovIt() 每次点击按钮都会在页面上追加一段 createP(result) 生成的新文本:

function markovIt() {
  var currentGram = txt.substring(0, order);
  var result = currentGram;
  for (var i = 0; i < 100; i++) { ... }
  createP(result);
}

第三步:交互触发。setup() 中使用 noCanvas() 关闭画布,仅创建“generate”按钮并绑定 markovIt:

function setup() {
  noCanvas();
  // ...构建 ngrams...
  button = createButton('generate');
  button.mousePressed(markovIt);
  console.log(ngrams);
}

3.4 Processing 版本的等价实现

仓库同时提供了 Processing 版本,逻辑与 JS 版完全一致,但使用 Hashtable<String, ArrayList<Character>> 替代 JS 对象:

Hashtable<String, ArrayList<Character>> ngrams;
// ...
ngrams = new Hashtable();
for (int i = 0; i < txt.length() - order; i++) {
  String gram = txt.substring(i, i + order);
  if (!ngrams.containsKey(gram)) {
    ngrams.put(gram, new ArrayList());
  }
  ngrams.get(gram).add(txt.charAt(i + order));
}

交互方式也改为 mouseClicked() 调用 markovIt(),并把结果 println(result) 输出到控制台。两个版本演示了同一算法的跨语言实现,方便读者对照学习。

四、完整实现二:基于多行语料生成名字(CC 42.2)

4.1 与 42.1 的差异:数据加载与随机起点

Coding Challenge 42.2 的目标是用观众提交的名称建议生成 YouTube 频道新名字,其数据不再是写死的单段文本,而是加载自多行文件 names.txt。相比 42.1,它引入了两个关键变化:

  1. beginnings(起点集合):记录每行文本开头的 gram,生成时从随机起点开始,而不是固定从全文开头开始;
  2. preload() + loadStrings():在 p5.js 的 preload 阶段异步加载每行一个名称的文本文件。

4.2 构建阶段:逐行处理 + 记录起点

在 CC_042.2 的 sketch.js 中,外层循环遍历每一行名称,内层滑动窗口构建 n-gram,并额外把每一行的第一个 gram 存入 beginnings:

for (var j = 0; j < names.length; j++) {
  var txt = names[j];
  for (var i = 0; i <= txt.length - order; i++) {
    var gram = txt.substring(i, i + order);
    if (i == 0) {
      beginnings.push(gram);      // 记录每行起点
    }
    if (!ngrams[gram]) {
      ngrams[gram] = [];
    }
    ngrams[gram].push(txt.charAt(i + order));
  }
}

4.3 生成阶段:随机起点 + 短循环

生成时从 random(beginnings) 随机取一个起点,再循环 20 次(比 42.1 的 100 次更短,因为频道名通常较短):

function markovIt() {
  var currentGram = random(beginnings);
  var result = currentGram;
  for (var i = 0; i < 20; i++) {
    var possibilities = ngrams[currentGram];
    if (!possibilities) {
      break;
    }
    var next = random(possibilities);
    result += next;
    var len = result.length;
    currentGram = result.substring(len - order, len);
  }
  createP(result);
}

4.4 语料与 Processing 版本

names.txt 中包含约 80 个观众提交的候选名,如 “Coding Rainbow”、“Joy of Code”、“Rainbow Laboratory” 等,混合了大写字母、点号、括号等字符,恰好能体现 n-gram 模型对“词内结构与词间拼接”的复刻能力。Processing 版本(CC_042_2_markov_chain_names.pde)则使用 loadStrings("names.txt") 加载 data/ 目录下的同名文件,逻辑与 JS 版一致。

五、算法本质与可调参数

5.1 为什么“出现次数多 = 概率高”

马尔可夫链生成的核心是:在候选数组中,一个后继字符出现多少次,它被 random() 选中的概率就是多大。以 order = 2 为例,若语料中 “co” 后面跟着 “d” 出现 5 次、跟着 “l” 出现 1 次,那么生成时 “d” 被选中的概率是 5/6。这正是“用统计属性驱动文本生成”的体现,也是本讲与课程主旨(统计性质评估文本)的直接关联。

5.2 参数调节建议

参数 位置 作用与取值建议
order 全局变量 n-gram 长度。order=1 时近乎随机拼字;order=2 是两套实现默认值;order=3 起能保持较完整局部语序,但创造性下降、字典体积增大
生成循环次数 for 循环上界 42.1 用 100,42.2 用 20;决定输出文本长度,可按需求调整
txt / names.txt 数据源 语料越长、越有风格,生成结果越多样;换成语料可让模型“学会”该语料的用词习惯
起点策略 currentGram 初值 固定开头(42.1)适合长文本;随机 beginnings(42.2)适合短名称

5.3 边界处理:候选缺失即终止

两套实现都包含关键的保护逻辑:当 ngrams[currentGram] 不存在时立即 break,避免访问未定义数组导致报错。这在处理小语料或长名称时尤其重要——滑动窗口滑到从未出现过的状态组合时,链自然结束。

六、作业方向与扩展思路

第 6 讲作业说明(6.2) 指出,本讲作业围绕 n-gram 与马尔可夫链 展开练习。结合两套实现的差异,可延伸的方向包括:

  • 换语料:把 unicorn 文本换成新闻、歌词或你自己的文章,观察生成文本风格的迁移;
  • 调 order:对比 order = 1/2/3/4 的生成质量,体会“连贯性 vs 创造性”的权衡;
  • 加词级模型:当前实现是字符级 n-gram,可改成按空格分词、以词为单位的 n-gram,输出更接近自然语言;
  • 随机起点:借鉴 42.2 的 beginnings 策略,为段落生成也引入随机开头;
  • 可视化:把 n-gram 转移关系绘制成图(如 Chris Harrison 的 Web Trigrams 思路),直观展示状态之间的转移概率。

这些练习恰好串联起本讲课程目标:先用统计属性评估文本,再用概率方法自动生产文本。

七、小结

本讲把“马尔可夫链”这一宽泛概念落到了文本生成的工程实践上:用 n-gram 切分状态、用哈希表统计转移、用概率抽样驱动生成。仓库中的两套 Coding Challenge 给出了完整可运行的参考实现(p5.js 与 Processing 双版本),从单文本生成到多行语料生成名字,覆盖了从“固定起点”到“随机起点”的两种典型场景。掌握了这套模式,你就可以把任意语料“喂”给马尔可夫链,生成风格相近的全新文本。

登录后查看全文
website-archive