马尔可夫链生成随机文本

Posted by wyj on March 8, 2019 / Edited on April 25, 2020

这是一个老生常谈的话题了,我却是最近才听说的。很感兴趣,就随手实现了一下。

首先ubuntu读入gbk文档有困难,并且iconv不能成功转码(转出来全是乱码)。所以所有的工作都在windows下完成。windows对于中文的支持非常好,连记事本这种比gedit垃圾一万倍的东西都可以轻松转码。于是就可以施展我从Pascal遗传过来的读中文技巧:把负数的字符与之后的一个字符连接,当成一个int字符。

蒟蒻不想写trie,于是用unordered_map<uint64_t,unordered_map<int,int>>存储hash值。每一个字符根据前五个字符随机确定。

代码

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
using ull=uint64_t;
using uch=unsigned char;
using um=unordered_map<int,int>;
uniform_real_distribution<double> u(0,1);
default_random_engine e(GetTickCount());
const int k=5;
char s[1<<24];int n,t[1<<24],m;
unordered_map<ull,um> mp;
ull hsh(int l,int r){
	ull re=0;
	for(int i=l;i<=r;i++)re=re*1234567+t[i]+2333;
	return re;
}
int getop(const um&x){
	int tot=0;
	for(auto&pa:x)tot+=pa.second;
	double v=u(e),now=0;
	for(auto&pa:x)if((now+=pa.second*1./tot)>=v)
		return pa.first;
}
int main(){
	freopen("1.txt","r",stdin);
	for(char c;~(c=getchar());)
		s[++n]=c;
	for(int i=1;i<=n;)
		if(s[i]<0)
			t[++m]=(uch)s[i]<<16|(uch)s[i+1],i+=2;
		else t[++m]=(uch)s[i++];
	for(int i=k+1;i<=m;i++)
		mp[hsh(i-k,i-1)][t[i]]++;
	uniform_int_distribution<int> U(1,m-k+1);
	memmove(t+1,t+U(e),k*sizeof(int));
	for(int i=k+1;i<=1000;i++)
		assert(mp.count(hsh(i-k,i-1))),t[i]=getop(mp[hsh(i-k,i-1)]);
	for(int i=1;i<=1000;i++){
		if(t[i]>>16)printf("%c%c",t[i]>>16,t[i]&65535);
		else printf("%c",t[i]);
	}
	puts("");
	return 0;
}

生成的文本 – 使用《三体》作为输入:

 危机纪年第3年,三体舰队距太阳系4.18光年
  怎么看上去这么旧啊……
  啊不!别再去想她了,这会是一场灾难,被推翻的部分远多于被证实的,包括三体世界曾提议由速度更快的后续舰队,所以,要救援 偏航的三体舰队无疑能够做到这一点,但防卫前沿至少应前推至奥尔特星云发回可识别信号所需的天线尺寸和同位素电源的质量,总重两 至三吨吧。
不行!瓦季姆坚决地摇摇头,说她跳的不是澳大利亚。
潜藏的危机开始爆发,移民开始后有一半国家的政府也迁移至此,联合国也刚从悉尼转移到这里,军队不得不进行防守。这一次冲突造成 了重大伤亡,死了五十多万人,大部分是低矮的板房,其间有几幢两三层的欧式楼房。从画面前方那条河流和其他的地形看,这可能是他 除了长达两个世纪的利息,真正的长线投资,穷光蛋也富了,后悔当时没有多存些。”
  “这封信是你写的吗?”张主任问,同时从信封中抽出一片散发出清香的东西,形状不规则,不是纸,竟是一片白桦树皮,上面有一 台平面显示器,还有几个孩子在玩耍,最大的不超过五岁,小的刚会走路。杨母告诉汪淼,这都是邻居的孩子。
你们必须证实公主的身份。一位老者说,他身上破旧的制服打理得很整齐,也都是纯白色,几乎与白墙融为一体,之后这个融合的躯体将 发生分裂,裂解为三至五个新的幼小生命,这就是他看到的那道伸延到前方的狭长平台。回头,他看到了自己想要的东西:一个有十匹马 的马厩,因为到雪山方向散步,骑马最好;还有一个网球场这么大,这就是活性炭具有超强吸附性的原因。”
伽利略又嗤了一声,“墨子的思想仍是东方的,他不过是披着科学外衣的玄学家,从来就没有完全融入那种对每个人都照顾得无微不 至的体贴——一个老刽子手对行刑对象的那种体贴。
  然后,他面对着东方的晨光,开始了地球文明和三体文明的最后对决。
  “让您的组织保存下来。
所以,直到威慑纪元后期,宇宙对两个世界进行黑暗森林威慑系统,他们对自己的冒险可能会谨慎许多。

对于不同k值的表现

English

输入:Wikipedia上的Google词条

k=1:无意义的字母组合
k=2:看起来很像英语的非英语词汇,比如 and se Earm fores of thas orme on ithen scia.
k=3..4:由拼写错误很多的单词组成的无意义句子。
k=5:基本由正常的英文单词组成的无意义句子。
k=10:掌握了短句的语法,长句有所欠缺。
k=15:无意义句子
k=20:大量复述原文

中文

输入:地球演义1-227回

k=1:无意义的词语组合。如吸收和双颚齿分之交配合游泳也得不知道
k=2..3:无意义的短语组合。如卵能够修复完成交配,受到了石炭纪的软体动物的先驱终究无法
k=4..5:无意义的完整句子。
k=10:大量复述原文

一年多之后的更新

我突发奇想,打算使用平时听的网易云音乐歌词缓存作为输入,看看这个搞笑的程序能写出来什么样的“歌”。

首先是修改了一下代码,让生成的文章不必从原文的开头开始。然后是准备输入数据。首先把所有的歌词缓存写进同一个文件里,然后使用vim写了一堆奇怪的正则表达式删除了无用的JSON,最后手动删除了每首歌头部的作者信息等等无关内容。很明显这个操作肯定是不能用vim自动完成的。剩下的文本大概有600KB。

调整了一下$k$的值。发现歌词和之前使用过的所有文本差别很大,当$k=5$时几乎就是在大段复述原文歌词了。$k=3$时还勉强可以看看,尽管几乎就是歌词大接龙

走出迷途从此我心有依赖 夜从哪里来 带给我宁静 是因为你在乎 若贻笑千古因为爱得执迷又糊涂 也不在乎这结果 想说的话都没有跳 动过 看自己(的)时候 当狂风暴雨来临的时候当天空阴霾的时候 镜子里有熟悉的声音啊梦中的神奇 感觉 当我再次两手空空 只有慢慢慢慢等(慢慢的慢慢的慢慢的 你变成他们了 时光似水冲刷我的心情 背上行囊 卢中强脚步丈量远方 饮一盏岁月留香 唱一曲往事飞扬 甜蜜又感伤 那就让我 来次透彻心扉的痛 都拿走 让我再一次响起 左右俩河岸。 黑夜过去到黎明 像飞鸟呻吟 我没有推 我不知该何去 何从 指缝中滑过 像吹在旷野里的风 映入慌乱的耳际 那年冬天 乡音未变 只少了心心念 一晃又一眼 北辙到南辕 来时路 在提灯而来的夜 新的人间化妆舞会 早已经忘了什么吗 如果夏天 你让我作吧 你去想象 生命的霞光融化了征途的风霜 就让我 来次透彻心扉的痛 都 拿走 让我总不快乐 世界已经拥有这美丽的姑娘 胖胖的她 路过沙漠去看青海 金色的麦浪 就在那多愁善感而初次 感觉如此靠近在这一 瞬间有一百万个可能 窝进棉被或面对寒冷 暖这冬心或面对寒冷 该向前走,就想走 就算你会 我却没有因此怨天尤人自暴自弃 你知不知道 迷失在黑夜里的眼睛 给我再去相信的勇气 即使越来越冷没有叶子的树依然坚持心中的伤口 如过眼的云烟初次感觉心就像天空般晴朗我看到在你眼中 天真是一种罪 在你离去的心海 你曾说恋爱是两个小伙子心中最美的旋律 问自己 最后剩我 还有怎样的情景 会不会将 你 再次映着我那不安的心 ?让我充满幻想和期盼在遥远的地方 我像每个恋爱的人却反目错过了幸福 谁又为你在乎 有谁能帮帮我把十字架解脱 人们都出来了 我们路过森林路过沙漠 路过一个女人的温暖和眼泪路过生命中遇见你 又过了一年我走过海岸边 熟悉的你 却一直在努力祈祷 别再财迷心窍 我们相互温暖 我坐在我身旁 今夜 你还在听岛屿 的电台 不动情的咳嗽 至少我现在已经规定好的路上每一 个夜里生长我的每次飞翔 麦克你再度回到这城市的寂静处 让一切都交给她吧 把一切都随风散落 在天边在眼前 摇曳着 摇曳着 摇曳着 摇曳着 化为永恒的哀愁 不管经历多少次,也无法为你喝彩 请你等待 我的心伤害美人呀世界变得太快你的美丽星空 好象天空般晴朗 我看见你也依然在路上 注定落西山道路艰险 世道的阴影里 不知天高地厚的 全都变了我们都已经开始了等待

我可以识别出来《圣洁之光》《依然在路上》《千古》《燕归巢》《额尔古纳》《理想三旬》《旅途》《No fear in my heart》《猎户星座》《火车开往落日》《慢慢的》《故乡》《青鸟》《美人》《光阴的故事》《春夏秋冬的你》《夜空中最亮的星》等等很多歌。然而“你曾说恋爱是两个小伙子心中最美的旋律”是什么鬼啊。。。。。

然后又去用很久以前照着Matrix67的博文写的分词程序分了一下词,得到歌词中的高频词语(即出现超过50次)为:

世界 啦啦 什么 自己 温暖 瞬间
知道 等待 遥远 岁月 感觉 依然
自由 青春 美丽 孤独 时候 沉默
歌唱 因为 姑娘 如果 达列 妈妈
希望 寂寞 北京 回忆 快乐 夕阳
城市 开始 悲伤 …… 咿呀 欢乐
灿烂 故事 幸福 简单 朋友 赛哩赛
哩赛 思念 告诉 忧伤 漫长 此刻
哭泣 笑容 眼睛 寻找 社会 小屋
身旁 温柔 飘荡 双眼 悄然 清晨

(乱入的“达列”“赛哩赛”“哩赛”三个词是因为《快乐节》和《来者摩羯》)