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

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

查看更多 »

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

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

查看更多 »

    记得第一次了解中文分词算法是在 Google 黑板报 上看到的，当初看到那个算法时我彻底被震撼住了，想不到一个看似不可能完成的任务竟然有如此神奇巧妙的算法。最近在詹卫东老师的《中文信息处理导论》课上再次学到中文分词算法，才知道这并不是中文分词算法研究的全部，前前后后还有很多故事可讲。在没有建立统计语言模型时，人们还在语言学的角度对自动分词进行研究，期间诞生了很多有意思的理论。

    中文分词的主要困难在于分词歧义。“结婚的和尚未结婚的”，应该分成“结婚／的／和／尚未／结婚／的”，还是“结婚／的／和尚／未／结婚／的”？人来判断很容易，要交给计算机来处理就麻烦了。问题的关键就是，“和尚未”里的“和尚”也是一个词，“尚未”也是一个词，从计算机的角度看上去，两者似乎都有可能。对于计算机来说，这样的分词困境就叫做“交集型歧义”。

    有时候，交集型歧义的“歧义链”有可能会更长。“中外科学名著”里，“中外”、“外科”、“科学”、“学名”、“名著”全是词，光从词库的角度来看，随便切几刀下去，得出的切分都是合理的。类似的例子数不胜数，“提高产品质量”、“鞭炮声响彻夜空”、“努力学习语法规则”等句子都有这样的现象。在这些极端例子下，分词算法谁优谁劣可谓是一试便知。

查看更多 »

有时候会觉得日文很有喜感，印象最深的就是第一次听说“努力学习”在日文中写作“一生悬命勉强”时，真把我笑得前俯后仰。今天网上闲逛，偶入一日文数学网站，惊奇地发现里面的大多数日文数学名词我都能看懂，并且依旧给人带来一种新奇的陌生感：“多边形”叫做“多角形”，“梯形”叫做“台形”，“切线”叫做“接线”，等等。于是我想到了下面这个有趣的游戏：我在日文 Wikipedia 中挑选了一些词汇，看看大家能否猜得到它们的意思。括号里的数字表明对应的汉语名词有几个字。

=== 数学篇 ===
1. 自乗 (2)
2. 確率 (2)
3. 合同 (2)
4. 二進法 (3)
5. 放物線 (3)
6. 背理法 (3)
7. 暗号理論 (3)
8. 天井関数 (5)
9. 数理論理学 (4)
10. 可付番集合 (4)
11. 鳩の巣原理 (4)
12. 半順序関係 (4)
13. 位相幾何学 (3)
14. 連続体仮説 (5)
15. 排他的論理和 (2)
16. 双子素数の予想 (6)
17. ユークリッド原論 (4)
18. 一対一上への写像 (4)
19. 平方剰余の相互法則 (5)
20. ゲーデルの不完全性定理 (8)

查看更多 »

    大家都知道，幻方是这样一种数字游戏，将 1 到 n^2 这 n^2 个数填入 n×n 的方阵中之后，每行、每列及两条对角线上的数字之和都相同。作为一个古老的数学游戏，幻方的生命力极强，直到现在数学家们还在寻找满足各种奇怪性质的幻方。更有意思的是，这神奇的数字方阵后来竟也发展成了文字游戏。人们发现，在 4×4 的方阵中填入以下字母，每行每列都是一个单词：

C A R D
A R E A
R E A R
D A R T

    这样的字母方阵就被称为“文字幻方” (word square) 。

    最近本人对文字游戏尤其感兴趣，心头开始思考起这么一个问题：是否有可能在方阵中填入汉字，让每行每列都是一个词语呢？看着电脑桌面上放着上次寻找 中文 piphilology 的词库，我就又手痒了，于是花了一下午的时间，利用 Mathematica 对汉字幻方作了一些搜索。下面和大家分享一下我得到的结果。

查看更多 »

    语言统计分析期末大作业要求我们统计全唐诗中的对偶字，并用所得到的统计结果反过来评判出对仗最工整的诗句。我在数据处理过程中突然想到，鉴于互成对偶的两个字之间有一定的语义联系，我们便有了一个庞大的汉字语义关联库；如果把所有汉字之间的关联画成一张图会是什么样子呢？于是我用 Mathematica 7 提出了全唐诗中处在对偶位置上的所有字对，得到了 464448 个可能的对偶关系；再利用一些算法得到了最稳定、最常用的 2000 个对偶关系，把它们都描绘在一张大图上，于是便有了上面的这个图。点击这里查看高清无码大图，1600x1600 像素。可以看到，有语义关联的汉字自动地聚合到了一起。

查看更多 »

    在翻看现代汉语笔记时，我突然惊奇地发现，在语言文字中大量使用“他妈的”能够非常有效地避免歧义现象，提高语言交际的效率。
    让我们来看看这个句子：“今年的考题跟去年一样”。假设你想要在这句话里面加一个“他妈的”，在通常情况下（不强调句中的任何成份时），你应该加在哪里？嗯，不错，大家通常都会说，“今年的考题跟去年他妈的一样”。但是，再看看这个句子：“他很狡猾，跟狐狸一样”。同样在这里插入一句“他妈的”，你又会加在哪里呢？相信大多数人都会说，“他很狡猾，跟他妈的狐狸一样”。同样是“跟……一样”的结构，为什么“他妈的”插入的位置就不一样呢？其根本原因就在于，两个句子看似相同，但具体结构是不一样的。当表示A和B完全相同时，说“跟B一样”指的是“和B是一个样”，其结构是“跟B”加上“一样”；当表示A与B具有相似性时，说“跟B一样”指的是“好像B的样子”，其结构是“跟”加上“B一样”。因此，在这两个划分不同的结构间插入“他妈的”，位置也理所当然的不一样了。当“A跟B一样”表示相同时，我们往往说“A跟B他妈的一样”，重音在“一样”上；但当“A跟B一样”表示相似时，我们往往说“A跟他妈的B一样”，重音在B上。
    现在，考虑这个句子：“今年的考题跟作业题一样”。这就有歧义了——是说今年的考题真的用了作业里的题呢，还是仅仅是比喻这次考题简单得像作业题？这时，“他妈的”就派上用场了。我们可以在句子间加入“他妈的”来区别：

      今年的考题跟作业题他妈的一样 （指与作业题相同）
      今年的考题跟他妈的作业题一样 （暗指考题太简单）

查看更多 »

    在计算机复杂度理论中，P问题指的是能够在多项式的时间里得到解决的问题，NP问题指的是能够在多项式的时间里验证一个解是否正确的问题。虽然人们大多相信P问题不等于NP问题，但人们目前既不能证明它，也不能推翻它。P是否等于NP是计算机科学领域中最突出的问题，在千禧年七大难题中排在首位。科学家们普遍认为P≠NP是有原因的。让我们来看一看，如果哪一天科学家证明了P=NP，寻找一个解和验证一个解变得同样容易，那这个世界将会变得怎样？

 
    已知的NPC难题将全部获解，这将瞬间给各个科学领域都带来革命性的进展。整数规划、01规划、背包问题全部获解，运筹学将登上一个全新的高度；数据库的串行化、多处理器调度等问题也随之解决，大大提高了计算机的性能。同时，空当接龙、扫雷、数独等经典游戏也由于获得了多项式的算法而在很大程度上失去了意义。
    算法研究方向将发生全面转移。对算法的研究可能会转向围棋等NP-Hard问题。算法设计的学问与“NP问题统一解”的关系正如小学应用题与列方程解题的关系一样，将成为一种纯粹锻炼思维的游戏。

    一些新型的自动编程语言将出现，并将逐渐取代传统的编程语言。这种新型编程语言扮演着一个“判定性/最优化问题万能解决器”的角色。在新的编程语言中，你只需要用代码指明输入数据与输出数据的关系，而无需关心计算输出数据的步骤。只要这种关系是多项式时间内可计算的，编译器将自动找到解法。在新型编程语言的支持下，人们唯一需要考虑的是，如何把实际问题转化成数学模型。

查看更多 »