残阳似血的博客

在计算机图形学发展史中，真实感绘制一直是主旋律。不过从20实际90年代中期开始，非真实感图像绘制(Non-Photorealistic Rendering，NPR）逐渐成为一个研究热点。说白了，真实感绘制目标是像照片般真实地再现客观世界，而非真实感图像绘制专注于图形个性化和艺术化的表达，它主要用来表现图形的艺术特质，以及模拟艺术作品（甚至包括作品中的缺陷）。

在介绍完非真实感图像绘制之后，我们再来提及一下PIL——Python Imaging Library（官方网址）。相信使用python的朋友们都不会陌生，因为在web应用中我们常常用它来生成缩略图。从名字也可以看出，PIL主要用来处理图片，它支持多种图片格式，并提供强大的图片和图像处理能力。详细的关于PIL的内容大家可以参阅手册。

这个系列，我们就主要使用PIL来进行滤镜方面的处理，包括素描、铅笔画、油画等等滤镜效果的实现。在以后我会把代码托管出来。

PIL已经内置一些滤镜效果，详细见文档和这篇文章。

声明：这篇文章中涉及的游戏来自@陈荣峰ayuLemon的创意，文章的主要目的还是研究这个游戏其中的算法，我所写的网页版的游戏版本也仅仅是为了验证算法的正确性。说明这个是防止大家误认游戏乃我的原创。本来原作者要求我不能在他的算法出来之前发出此文，我百思不得其解。我认为这个没有先后顺序，思前想后，还是发出来了。仅讨论之用。

事情的起因是这样的，在我又度过了一个不眠之夜、正打算睡觉之时，看到@python4cn 转发了一个同学的微博，原文是这样的：

@陈荣峰ayuLemon：用python做了个小游戏，这是5*5方格。每点击上面的方格一次，就改变周围四个方格和被点击方格的颜色，对于任意n*n方格，可否通过若干次点击使方格的颜色与最初完全相反？？（3*3和4*4的都很容易~~这个5*5的似乎有困难） 大家帮忙想一想，证明行或者不行，哪些行，哪些不行~~

本来已经很困的我看到这个，又勾起了我的好奇。于是拿起纸笔，开始演算。当然首先从2×2开始，一直到4×4，确实没有什么困难。到5×5，算了很久才算出一个结果。

在分析这个问题之前，如果你想试玩，我做了一个网页版的，地址在这里。

相信大家都用过微博，我们在微博的timeline中，常常可以看到文字、音乐、视频等等的混合。所有的内容都聚合在一起显示出来。具体的实现未可知，但是在Django中，我们有比较优雅的方式。那就是使用contenttypes模块来实现。

现在我们假设对于一条微博只有三种方式（其他的很容易拓展）：文本，音乐以及视频。我们先定义三个简单的Model。（注意到Music和Video只要简单继承Tweet类即可。）

from django.db import models
from django.contrib.auth.models import User

class Tweet(models.Model):
    user = models.ForeignKey(User) # 这里就用Django自带的User
    content = models.CharField(max_length=140) # 内容，最多140字
    pic_url = models.URLField(null=True, blank=True)
    created = models.DateTimeField(auto_now_add=True)
    
    class Meta:
        ordering = ['-created',]
        
    def __unicode__(self):
        return self.content
    
class Music(Tweet):
    music_url = models.URLField(verify_exists=False)
    
class Video(Tweet):
    video_url = models.URLField(verify_exists=False)

我们的网站通常都要集成搜索服务。通常情况下，我们都使用自己的搜索后端，例如使用Django，对于Python，我们主要有两种选择，一种是Whoosh，它是纯Python写成的搜索后端；另一种则是著名的Lucene的Python扩展，PyLucene，要提醒使用PyLucene，需要安装JVM。以后的文章我会介绍他们。

不过，今天的主角显然不是它们。因为有时候，我们并不需要这么麻烦，有时我们只需要集成一个Google搜索在其中就可以了。那么，Google custom search就派上了用场。在这里，我们也有三种方案：

1. 用iframe版本的cse，使用这种方式，甚至不需要写什么代码。
2. 使用Google ajax API，使用ajax方式获取搜索结果，然后用js将结果呈现在页面上。
3. 使用Custom search API，在后端使用Python的http编程，远程获取json方式的结果，并把数据渲染到模板中。

在一切开始之前，必须先创建一个新的自定义搜索。在cse页面上，点击“Create a Custom Search Engine”，如果已经新建过了，点击下面的“manage your existing search engines”。

在英语中，一个单词常常是另一个单词的“变种”，如：happy=>happiness，这里happy叫做happiness的词干（stem）。在信息检索系统中，我们常常做的一件事，就是在Term规范化过程中，提取词干（stemming），即除去英文单词分词变换形式的结尾。

应用最为广泛的、中等复杂程度的、基于后缀剥离的词干提取算法是波特词干算法，也叫波特词干器（Porter Stemmer）。详见官方网站。比较热门的检索系统包括Lucene、Whoosh等中的词干过滤器就是采用的波特词干算法。

简单说一下历史：

马丁.波特博士（Dr. Martin Porter）于1979年，在英国剑桥大学，计算机实验室，发明了波特词干算法。
波特词干算法当时是作为一个大型IR项目的一部分被提出的。它的原始论文为：
C.J. van Rijsbergen, S.E. Robertson and M.F. Porter, 1980. New models in probabilistic information retrieval. London: British Library. (British Library Research and Development Report, no. 5587).
最初的波特词干提取算法是使用BCPL语言编写的。作者在其网站上公布了各种语言的实现版本，其中C语言的版本是作者编写的最权威的版本。
波特词干器适用于涉及到提取词干的IR研究工作，其实验结果是可重复的，言外之意是说，波特词干器的输出结果是确定性的，不是随机的。（还有基于随机的高级词干提取算法，虽然会更准确，但同时也更加复杂）。

词干提取算法无法达到100%的准确程度，因为语言单词本身的变化存在着许多例外的情况，无法概括到一般的规则中。使用词干提取算法能够帮助提高IR的性能。

波特词干算法的官方网站上，有各个语言的实现版本（其实都是C标准的各个翻译形式）。各位要应用到实际生产中可以直接下载对应的版本。本文将会分析Java语言的源码。在今后的文章中，再介绍使用Python特性优化过的版本。（Python原版几乎就是C语言版本的翻译，这也就意味着不能充分利用Python的语言特性。）