这篇文章是漫话中文分词算法的续篇。在这里，我们将紧接着上一篇文章的内容继续探讨下去：如果计算机可以对一句话进行自动分词，它还能进一步整理句子的结构，甚至理解句子的意思吗？这两篇文章的关系十分紧密，因此，我把前一篇文章改名为了《漫话中文自动分词和语义识别（上）》，这篇文章自然就是它的下篇。我已经在很多不同的地方做过与这个话题有关的演讲了，在这里我想把它们写下来，和更多的人一同分享。

    什么叫做句法结构呢？让我们来看一些例子。“白天鹅在水中游”，这句话是有歧义的，它可能指的是“白天有一只鹅在水中游”，也可能指的是“有一只白天鹅在水中游”。不同的分词方案，产生了不同的意义。有没有什么句子，它的分词方案是唯一的，但也会产生不同的意思呢？有。比如“门没有锁”，它可能是指的“门没有被锁上”，也有可能是指的“门上根本就没有挂锁”。这个句子虽然只能切分成“门／没有／锁”，但由于“锁”这个词既有可能是动词，也有可能是名词，因而让整句话产生了不同的意思。有没有什么句子，它的分词方案是唯一的，并且每个词的词义也都不再变化，但整个句子仍然有歧义呢？有可能。看看这句话：“咬死了猎人的狗”。这句话有可能指的是“把猎人的狗咬死了”，也有可能指的是“一只咬死了猎人的狗”。这个歧义是怎么产生的呢？仔细体会两种不同的意思后，你会发现，句子中最底层的成分可以以不同的顺序组合起来，歧义由此产生。

查看更多 »

     据说，爱出题也是 Geek 的一种特征。这几天在做语言工程课的期末大作业时，再一次见识了汉语里各种诡异的语法规则，然后突然想到了这样一种好玩的题型，于是竟然暂时放下手中的作业，花时间编了几个这样的题目来（感谢 Geek 小美女 localhost_8080 的帮助）。
    下面的每一组词中，前五个词都具有某种共同的性质，这种性质是后面五个词都不具有的。你能猜出每组词所对应的那个性质吗？

      (1) 反复、高兴、磨蹭、说笑、许多 | 地震、动静、金黄、巨大、雕刻
      (2) 鱼、路、船、裙子、短信 | 山、剑、伞、文章、水母
      (3) 锁、画、挂钩、标志、爱好 | 钟、鞋、密码、学问、照片
      (4) 腿、门、气味、鱼刺、笔记本 | 手、电、建筑、铅笔、地球仪
      (5) 车、地、桌子、屁股、筷子 | 水、胃、位置、大陆、晚餐

查看更多 »

    有一个正方形的房间，房间的四壁都是镜子。房间里有一个天使和一个恶魔。假设房间是一个单位正方形 [0, 1] × [0, 1] ，那么天使和恶魔便是这个正方形内的两个点 (a, b) 和 (c, d) 。恶魔想要在原地发射致命激光杀死天使（激光可以无限地在镜子间反射）。天使可以根据恶魔的位置，预先在房间里放置一些守卫为自己挡住激光（守卫实际上也是一个个点）。当然，天使可以在自己周围密密麻麻地放一圈守卫，围成一个封闭的圆形，从而让恶魔不管朝什么方向发射激光，最终都无法击中天使。我们的问题是，能把守卫的数量减少到可数个点吗？能把守卫的数量减少到有限个点吗？

    这是一个非常经典的问题，我已经见过不止一次了。它可以重新叙述为很多更有趣的实际问题。去年的这个时候，网友 Spark 发来邮件，分享了他在看台球比赛时想到的一个问题：最少需要摆放多少个球，才能挡住白球到目标球的所有可能的路线，迫使对手犯规？如果我们把台球也抽象成一个一个的点，问题就和前面提到的情况一样了。

    今天，我终于看到了这个问题的答案，颇为激动，在此和大家分享。

查看更多 »

    同样是无穷集合，如果集合里的元素能够与全体正整数构成一一对应的关系，我们就说它是可数的，否则就说它是不可数的。 1874 年， Cantor 发表了一篇重要的论文，论文中证明了全体有理数甚至是全体代数数都是可数的，但全体实数却是不可数的。换句话说，同样是无穷多，实数的数量比有理数、代数数的数量都高出了一个级别。不过，当时 Cantor 证明实数集不可数的方法并不容易理解。 1891 年， Cantor 发表了另一篇论文，给出了实数集不可数的另一种证明方法。此后，这个简单到不可思议的证明不断地震撼着每一个初学集合论的人：

    事实上，实数区间 (0, 1) 就已经是一个不可数的集合了。换句话说，你绝不可能用“第一个数是某某某，第二个数是某某某”的方式把 0 到 1 之间的所有实数一个不漏地列举出来。我们大致的证明思路是，假设你把实数区间 (0, 1) 里的所有数按照某种顺序排列起来，那么我总能找到至少一个 0 到 1 之间的实数，它不在你的列表里，从而说明你的列表并不全。把你的列表上的数全写成 0 到 1 之间的无限小数（如果是有限小数，可以在其后面添加数字 0 ，把它变成无限小数）：

a₁ = 0.0147574628...
a₂ = 0.3721111111...
a₃ = 0.2323232323...
a₄ = 0.0004838211...
a₅ = 0.0516000000...
.........

    那么我就构造这么一个小数，小数点后第一位不等于 a₁ 的第一位，小数点后第二位不等于 a₂ 的第二位，总之小数点后第 i 位不等于 a_i 的第 i 位。这个数属于实数区间 (0, 1) ，但它显然不在你的列表里，因为它和你列表里的每一个数都有至少一位是不同的。这样，我们就证明了实数区间是不可数的。

查看更多 »

    有一个半径为 10 米的圆形舞台，初始时舞台上的某个地方有一头狮子。这头狮子在舞台上以折线段的方式跑了 30 千米。求证：在整个过程中，这头狮子至少转了 2998 个弧度。

    有时候，换一个角度思考，问题就会迎刃而解。

查看更多 »

    下面大家将会看到的是一个极其简单而又极其复杂的“迷宫”，这无疑是我在本年度见到的最变态的谜题：从左边入口处的 2011 进去，在迷宫里转悠，最后变成 2012 从右边出来。你可以在迷宫里转圈，可以重复之前走过的路，但不能往回退着走。

    你能成功走出来吗？

查看更多 »

    左图是一个凹多边形，而且凹得相当厉害。作为一个完美主义者，我很难容忍这么一个图形，总想着要把凹进去的部分翻出来，把它还原为一个凸多边形。不幸的是，翻折之后的结果仍然不是凸多边形，图中又产生了新的凹陷。于是，我们想继续把凹进去的部分往外翻，直到整个图形变成凸多边形为止。问题是，这个过程有完吗？换句话说，我们一定能通过有限多步翻折，把凹多边形变成凸的吗？

    这个问题有着非常纠结复杂的历史。这个问题最早可能是由数学家 Paul Erdős 正式提出的。 1935 年，他在 American Mathematical Monthly 上猜想，经过有限步翻折之后，凹多边形一定能变凸。 1939 年， Béla Szőkefalvi-Nagy 给出了一个证明。因此，这个结论又叫做 Erdős-Nagy 定理。有趣的是，这个问题是如此的自然，以至于在此之后，又有一大堆人重新提出并研究了这个问题，而且他们明显并不知道相互之间的已有研究。这事儿给我们带来的好处就是，我们有了 Erdős-Nagy 定理的好几种截然不同的证明方法。不过，这些证明或者太长，或者太高深，或者又有些漏洞。 1999 年， Godfried Toussaint 从这些证明中取长补短，给出了一个比较初等的证明。

查看更多 »

    去年年初的时候，我曾经发布过某专业课期末作业研究过程中带来的一个有趣的副产品：汉字的字义网络图。不过，当时我是直接调用的 Mathematica 的相关函数，函数几乎不能调整参数，并且也无法处理边上权重不同的情况。最近在研究引力斥力绘图算法，突然想到把当时的数据重新画一张图。于是就有了汉字地图第二版（点击小图看大图）：

查看更多 »