自描述语句(Self-Descriptive Sentence),也叫做 autogram,是一种自己描述自己的语句。

我在 2004 年的时候(时光飞逝啊)看到这种句子,想了一个简单的方法来用程序生成,效果还可以,但还有很大的不足。后来也没在做什么改进,今天就把这陈年老事拿出来晒晒太阳。

介绍

先举个简单的自描述语句的例子。十年前好友 @gdh 发邮件来说在网上看到有人发了这样一个句子,号称是用来折腾 Visual Studio 2003 的,但是没有更具体的信息,就想问问我有没有什么想法。句子是这样的:

聪明的张先生生成的这个句子一共有一百一十三个字,其中有二个 “百”,三个 “有”,二个 “子”,七个 “三”,三个 “生”,十五个 “二”,二个 “先”,二个 “字”,一个 “八”,二个 “七”,一个 “四”,二个 “明”,一个 “六”,二个 “成”,一个 “零”,二个 “张”,二个 “中”,二个 “其”,二个 “共”,二个 “这”,五个 “十”,二个 “句”,十个 “一”,三十一个 “个”,三个 “的”,二个 “聪”,一个 “九”,三个 “五”。

特点很明显,不考虑标点符号的话,一数便知,这句话一共有 113 个汉字,跟句子中声明的一致。另外,句子中出现过的每一个汉字,句子自身都给出了这个汉字的总出现次数。比如“聪”字一共出现两次,第一次是句子开头“聪明的”那里,第二次是声明“聪”字个数的时候说的“二个‘聪’”。再比如“个”字,数一数,包括“三十一个‘个’”中出现的两次,确确实实总共出现了 31 次。

这样的句子就是自描述语句的一种,它自己对自己做了一番统计,表明了自身的总字数,以及所包含的每一个汉字的次数。当然如果愿意的话,还可以让它把包含的每一个标点符号也都统计出来。

再来一个例子:

你看到的这个句子一共有九十个字,其中有二个“你”,二个“看”,二个“到”,二个“的”,二个“这”,二十六个“个”,二个“句”,二个“子”,二个“共”,三个“有”,二个“字”,二个“其”,二个“中”,四个“一”,十七个“二”,二个“三”,四个“四”,一个“五”,二个“六”,二个“七”,一个“八”,二个“九”,四个“十”。

这么有意思的东西,如果你也是刚刚见到,不妨停下来自己想一想,看看有什么好的办法来构造出这样的句子。

直接的思路

当时看到这样的句子,其实我也没什么思路,开始也没想要写程序来生成,只是顺着一点儿模糊的想法在纸上打打草稿。结果因为自己的小学数学基本功太差,加加减减的时候总是会出错,越算越头疼,只好写个程序来帮我算,没想到程序就直接把结果算出来了。

这中句子的结构就是一个前缀(如“你看到的这个句子”),跟着对总字数的声明(“一共有 XX 个字”),然后是对句子中包含的每一个汉字的次数的声明。那首先就得知道可能会包含哪些汉字啊。显然前缀子句和其他句子结构中出现的汉字都在其中,另外所有的数词(零一二三等)都有可能会出现。

再想想每个字可能的次数。既不是数词也不在词频统计部分重复出现的字(如上面示例中的“个”字),它们的出现的次数应该是固定的,即除了在前缀等地方出现已知的次数外,还会在声明它的词频时再出现一次。比如上面第二个例子中的“你”字,它就应该是出现两次,一次是作为句子的成分(前缀部分)出现一次,另一次就是声明它的词频的时候。而数词的次数就没法直接确定了,明显能感觉到它们是牵一发而动其全身的。

初始化

那么先把句子模板确定下来,然后往里面套总字数和完整的词频分布。这里我对句子结构做了些简化,假设我想要生成的句子是这样的:

这一句话一共有__个字,__个“__”,__个“__”,……。

先确定可能会出现的汉字集合,显然目前能看到的有“这”、“一”、“句”、“话”、“共”、“有”、“个”、“字”。另外预计会出现的就是所有的数词了。因为字数比较少,所以暂时就不用考虑“零”、“百”、“千”等字,只要考虑“一”到“十”即可。

关于把数字用中文表示出来的方法,参见之前的博文 将整数数字转换成中文 ,非常简单的程序,这里不再重复。

如果你的心算笔算能力还不错,下面的过程用一张纸和一支笔就能搞定了。首先列出所有可能出现的汉字,并且所有字的初始计数均为 0。总字数也要记录在案,初始值也是 0。列出来就是这样的表格,其中最后一列“TC”表示总字数。

TC
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

第一次迭代

接下来对句子模板做第一次扫描,并根据情况更新相应汉字的字数和总字数。处理的方法很简单,每看到一个汉字,就要给它的计数加 1,总字数加 1。任何一个汉字,如果计数从 0 变成 1,即第一次遇到它,就要再给它的计数和总字数加 1,同时对“个”字执行同样的操作。把这个过程叫做“increase”操作,即:

1
2
3
4
5
6
7
8
def increase(character c):
    if c.count == 0:
        c.count += 2
        total.count += 2
        increase('个')
    else:
        c.count += 1
        total.count += 1

比如首先看到“这”字,当前计数为 0,执行 increase 操作给它的个数加 2,总字数加 2,再对“个”字执行 increase 操作。由于“个”字此时的计数也是 0,因此它的计数直接加到 2,总字数加 2,这时注意还要再对“个”字执行一次 increase 操作。但第二次对“个”字执行 increase 操作时,由于其当前计数是 2 不是 0,所以直接给计数和总字数分别加 1 就行了。处理完第一个字“这”之后,计数情况为:2 个“这”,3 个“个”,总字数 5。

然后是“一”字,同样执行 increase 操作,计数增加 2,总字数增加 2,再对“个”字执行 increase,效果是其字数和总字数又分别加 1。完成后的计数情况为:2 个“这”,4 个“个”,2 个“一”,总字数 7。

用类似的办法把后面的“句”、“话”、“一”、“共”、“有”、“个”、和“字”都处理完,最后得到如下的计数情况:

TC
3 0 0 0 0 0 0 0 0 0 10 2 2 2 2 2 2 25

第二次迭代

下一轮就把所有的计数都翻译成中文,并统计它们所带来的计数改变。比如第一个计数是 3,就要对“三”字执行 increase 操作。然后是 10,对“十”字做 increase 操作。……。最后总字数 25,分别对“二”、“十”和“五”操作即可。处理完后得到新的一轮计数:

TC
3 8 2 0 2 0 0 0 0 3 14 2 2 2 2 2 2 44

第三次迭代

对比这两组计数,发现:

  • “一”、“这”、“句”等字的计数没有发生变化,并且这些数字对应的汉字已经全部统计过了,所以不必对它们做别的处理。
  • “二”、“三”、“十”等字,计数从没有变成了若干个,就要用跟刚才一样的方法,把这些数字翻译成中文并增加相应汉字的计数。
  • “个”字和总字数,我本来是想加入 10 和 25,但现在分别是 14 和 44,所以要把刚才加入的 10 和 25 都去掉,换成 14 和 25。比如把 10 换成 14,先对 “十”字做 decrease 操作,然后分别对“十”和“四”字执行 increase 操作。decrease 的过程如下所示,注意,由于每个字的计数都是直接从 0 涨到 2 的,所以也会直接从 2 降到 0。
1
2
3
4
5
6
7
8
def decrease(character c):
    if c.count == 2:
        c.count -= 2
        total.count -= 2
        decrease('个')
    else:
        c.count -= 1
        total.count -= 1

这样处理完后得到的新一轮计数为:

TC
3 9 3 4 0 0 0 2 0 3 15 2 2 2 2 2 2 51

周而复始

之后用同样的方法一轮一轮地迭代,结果如下(包含从初始化开始的每次迭代,第一列 ID 表示迭代次数):

ID TC
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 3 0 0 0 0 0 0 0 0 0 10 2 2 2 2 2 2 25
2 3 8 2 0 2 0 0 0 0 3 14 2 2 2 2 2 2 44
3 3 9 3 4 0 0 0 2 0 3 15 2 2 2 2 2 2 51
4 4 8 4 2 3 0 0 0 2 3 16 2 2 2 2 2 2 54
5 3 9 3 4 2 2 0 2 0 3 17 2 2 2 2 2 2 57
6 3 10 4 2 2 0 3 0 2 3 17 2 2 2 2 2 2 58
7 3 10 4 2 2 0 2 2 0 4 17 2 2 2 2 2 2 58
8 3 11 2 3 2 0 2 2 0 4 17 2 2 2 2 2 2 58
9 4 11 3 2 2 0 2 2 0 4 17 2 2 2 2 2 2 59
10 4 11 2 3 2 0 2 0 2 4 17 2 2 2 2 2 2 59
11 4 11 2 3 2 0 2 0 2 4 17 2 2 2 2 2 2 59

很高兴地发现,第十次的结果和第十一次的结果是完全一致的,这时候就没有任何操作可做了,实际上算法也就终止了。显然,通过这组数据生成的句子就是符合要求的自我统计的句子:

这一句话一共有五十九个字,四个“一”,十一个“二”,二个“三”,三个“四”,二个“五”,二个“七”,二个“九”,四个“十”,十七个“个”,二个“这”,二个“句”,二个“话”,二个“共”,二个“有”,二个“字”。

算法

总的看来,一轮一轮迭代的处理方法是这样的:

  1. 所有汉字的计数和总字数均初始化为 0;
  2. 遍历句子模板中的每一个汉字,对其计数做“increase”操作,得到一组新的计数;
  3. 比较当前计数数组与前一轮计数数组中的每一项:
    1. 如果二者一致,无操作;
    2. 否则,对前一轮的数值对应的每个汉字执行 decrease 操作(0 除外),对当前数值对应的每个汉字执行 increase 操作(0 除外);
  4. 重复步骤 3,直到相邻两轮计数数组完全一致。

其中 increase 和 decrease 操作均如前所述,不再重复了。

初遇困境

问题

换一个例子看看,把上面的句子模板开头的“这一句话”换成“新的一句话”,即:

新的一句话一共有__个字,__个“__”,__个“__”,……。

按照同样的算法一轮一轮迭代处理,却永远都无法终止。仔细看了看,发现计数数组会在几组值之间不断地反复,却怎么都无法收敛。具体的数据就不列出来了。

想想也是,上面的算法只是保证了,如果收敛,得到的一定是满足条件的解,却完全无法保证收敛。

解决

想到一个比较简单的变通方法就是修改之前的 decrease 操作。本来一个汉字如果是第一次出现,计数就直接从 0 涨到 2,如果要去掉,也直接从 2 回到 0。这样避免了出现“一个 XX”的情况。这其实不是必须的,如果把条件放宽,允许出现“一个 XX”(仍然符合自我统计的要求,只是显得有点儿多余),可以让 decrease 操作把计数从 2 降到 1。写出来大概是这样:

1
2
3
def decrease(character c):
    c.count -= 1
    total.count -= 1

根据这个规则重新迭代计算,结果如下表示,发现到第 9 次迭代后就收敛完毕。

ID TC
1 3 0 0 0 0 0 0 0 0 0 11 2 2 2 2 2 2 2 28
2 4 9 2 0 0 0 0 2 0 3 15 2 2 2 2 2 2 2 49
3 3 10 2 3 2 0 0 1 3 3 18 2 2 2 2 2 2 2 59
4 4 10 5 1 2 0 0 2 2 4 18 2 2 2 2 2 2 2 62
5 4 12 1 3 2 2 0 2 1 4 19 2 2 2 2 2 2 2 64
6 5 12 2 4 1 2 0 1 2 4 19 2 2 2 2 2 2 2 66
7 5 12 1 3 2 3 0 1 2 4 19 2 2 2 2 2 2 2 66
8 5 11 3 2 2 3 0 1 2 4 19 2 2 2 2 2 2 2 66
9 5 11 3 2 2 3 0 1 2 4 19 2 2 2 2 2 2 2 66

这样得到的自统计句子是:

新的一句话一共有六十六个字,五个“一”,十一个“二”,三个“三”,二个“四”,二个“五”,三个“六”,一个“八”,二个“九”,四个“十”,十九个“个”,二个“新”,二个“的”,二个“句”,二个“话”,二个“共”,二个“有”,二个“字”。

其中比较特殊的就是“一个‘八’”,句子中确实只有这个地方出现了 1 个“八”字,其他字的个数和总字数也都没错,但这个“一个‘八’”没有什么实际的意义。不引入这种“一个 XX”能否找到符合这个模板的解呢?目前我还没有明确的答案。

再遇困境

问题

很快就又遇到了新的麻烦,比如把句子模板开头换成“这句话”,即:

这句话一共有__个字,__个“__”,__个“__”,……。

算一下就会发现,不论是像开始那样直接从 2 减到 0,还是像刚才那样从 2 减到 1,全都会陷入无法终止的迭代。

实际上随便想一个句子模板出来,十有八九会是这样的,能像前两个例子那样收敛出结果的非常少。这可怎么办呢?

解决

想了一个简单粗暴的办法,效果还不错。前面提到 decrease 操作有两个方案,区别在于对于计数 2 做 decrease 的时候,要么直接减到 0,要么减到 1。那么一个直接的想法就是不要那么死板,让这个抉择可以随机的使用,即有一半的概率会直接减到 0,另一半的概率是减到 1。这个不确定性因素实际上是给迭代过程带来了一点儿干扰。如果按照某个确定的方案,迭代过程很容易陷入无穷尽的震荡,这时候如果引入一下随机的干扰,就有可能打破稳定的震荡,使得迭代过程偏离当前的动态平衡点,或许就刚好落在一个收敛的位置上了。

改造后的 decrease 操作大致是这样的:

1
2
3
4
5
6
7
8
def decrease(character c):
    if c.count == 2 and random.choice(0, 1) == 0:
        c.count -= 2
        total.count -= 2
        decrease('个')
    else:
        c.count -= 1
        total.count -= 1

用上面遇到问题的模板来说,以 3 作为随机数种子时可以得到这样的迭代过程,其中第 9 次和第 10 次的结果一致,是一个可行解。

ID TC
1 2 0 0 0 0 0 0 0 0 0 10 2 2 2 2 2 2 24
2 2 9 0 2 0 0 0 0 0 3 13 2 2 2 2 2 2 41
3 3 9 3 2 0 0 0 0 2 3 15 2 2 2 2 2 2 49
4 2 9 4 2 2 0 0 0 3 3 16 2 2 2 2 2 2 53
5 2 10 4 2 2 2 0 0 2 3 17 2 2 2 2 2 2 56
6 2 12 2 2 2 2 2 0 1 4 18 2 2 2 2 2 2 59
7 3 14 1 2 2 0 0 2 2 4 17 2 2 2 2 2 2 59
8 3 11 2 3 2 0 2 0 2 4 17 2 2 2 2 2 2 58
9 3 11 3 2 2 0 2 2 0 4 17 2 2 2 2 2 2 58
10 3 11 3 2 2 0 2 2 0 4 17 2 2 2 2 2 2 58

把计数结果带入到模板中,得到一个自统计句子:

这句话一共有五十八个字,三个“一”,十一个“二”,三个“三”,二个“四”,二个“五”,二个“七”,二个“八”,四个“十”,十七个“个”,二个“这”,二个“句”,二个“话”,二个“共”,二个“有”,二个“字”。

思考一下随机干扰对迭代收敛的作用,可以想见,这个随机选择进行的越频繁,迭代过程就越不稳定,遇到收敛点的概率相对也就越大。但如果迭代已经陷入到一个稳定震荡的状态,在整个振荡周期内却始终没有用到这个随机干扰,那还是没有办法跳出死循环。所以实际的程序会通过某种方式(最简单的就是设置最大迭代次数)判断是否陷入死循环并强制终止当前的迭代过程,从头开始重新走一遍。由于早期计数比较小,很容易遇到需要从 2 减到 0 或 1 的情况,大量的随机干扰可能会使得整个迭代过程完全变样,有可能会得到收敛的解。

三碗不过岗

引入随机扰动后,大部分问题都能搞定了。但对于过于复杂的模板依旧无能为力,模板复杂之后,能够遇到从 2 减到 0 或 1 的次数很少,很难跳出死循环。

有时候很简单的模板也无法得到结果,比如

一三五七一共有__个字,__个 “__”,__个 “__”,……。

这里可能有两个问题,一个是我的算法只能保证收敛得到的结果是正确的,无法保证一定收敛。加入随机干扰可能在一定程度上加大收敛的概率,却也没有本质的提升。另一个是任意给定一个模板,是否一定有解?这方面也还没有太多的思路。

相关的程序 在 github 上,目前除了可以生成中文的句子,还可以生成基于数字的句子。比如:

1 employs 11 digits, 4 1's, 3 2's, 2 3's, 2 4's.

以后可能会在两个方面做改进,一是模板化,一是迭代算法。现在是按照语言分的,其实语言只是模板的一个因素。模板化之后可以用同样的方法构造出更多更有趣的句子来。迭代算法方面,目前想到的是利用遗传算法,不过具体怎么操作还没有太多的想法。

后记

说来也巧,刚才无意间又找到了十年前我所看到的文章,原来是 @zee 在 2004 年 8 月的一篇博文 《以前玩出来的几个句子,怀旧一下》。摘录原文如下。

一年多前写程序生成的,当时好像 VS2K3 刚出来,写这个程序的主要目的是为了玩弄 2K3

聪明的张先生生成的这个句子一共有一百一十三个字其中有二个百三个有二个子七个三三个生十五个二二个先二个字一个八二个七一个四二个明一个六二个成一个零二个张二个中二个其二个共二个这五个十二个句十个一三十一个个三个的二个聪一个九三个五

你看到的这个句子一共有九十个字。其中有:二个“你”,二个“看”,二个“到”,二个“的”,二个“这”,二十六个“个”,二个“句”,二个“子”,二个“共”,三个“有”,二个“字”,二个“其”,二个“中”,四个“一”,十七个“二”,二个“三”,四个“四”,一个“五”,二个“六”,二个“七”,一个“八”,二个“九”,四个“十”。

这个句子一共有七十五个字。其中有四个“十”;二个“子”;四个“三”;十二个“二”;二个“字”;一个“八”;三个“四”;一个“六”;二个“七”;二个“中”;二个“其”;二个“共”;二个“这”;二个“句”;五个“一”;二十二个“个”;三个“有”;一个“九”;三个“五”。

现在是既没有心情也没有时间玩这些东东了............

谨以此纪念逝去的岁月。

Like this post? Share on: TwitterFacebookEmail

Comments

So what do you think? Did I miss something? Is any part unclear? Leave your comments below.

comments powered by Disqus

Keep Reading


Published

Category

算法

Tags

Stay in Touch