Parser之外的部分参考http://swtch.com/~rsc/regexp/regexp2.html ，代码都模仿自http://code.google.com/p/re1/source/browse 。注意到正则表达式是operator-precedence grammar，可以用一个扩展的Shunting-Yard算法来解析，其中用了一些特殊构造处理后缀操作符和括号。

2012-11-02

完美迷宫生成算法

Perfect maze

Perfect maze又称standard maze，指没有回路，没有不可达区域的迷宫。用图论的语言来说，就是可以用spanning tree表示的迷宫，保证迷宫中任意两个格子间都有唯一的路径。本文旨在探讨如何随机生成棋盘状perfect maze。迷宫格子的邻居的定义采用von Neumann neighborhood，即水平竖直方向相邻的四个格子。

变形Kruskal算法

说得通俗点，就是“随机拆墙”。

2012-10-06

自然语言处理之词语抽取

多日之前看到了Matrix67的《互联网时代的社会语言学：基于SNS的文本数据挖掘》，文中提到的方法是无监管的，而且无需词典就能提取词语，要素概括起来有两点：词的凝聚力，以及左右邻字的信息熵。今天把这个方法实现了一下。

对于凝聚力，我的理解是可以用词前后两部分的pointwise mutual information来描述，比如对于“博物馆”一词，考虑“博”与“物馆”之间，以及“博物”与“馆”之间的pointwise mutual information，两者取较小值作为“博物馆”这个词的凝聚力。

2012-10-01

Force-directed算法(1)——Fruchterman-Reingold

简介

Graph drawing即根据顶点和边的拓扑关系，将这张图展现出来。很明显，表现的形式种类是非常多的，如果精确到每个顶点的座标，那么方案有无穷多种。Graph drawing 目标是画出一张美观的图的布局来。美是个见仁见智的概念，何谓美？“每个本质在于旺盛的生命力，美的形象能够感染人的情感和鼓舞人心”，展现出来的图是否美每个人的看法可能都不一样，但有一些通用的要素是大家一般共同认可的，比如边的两端不能靠得太近也不能离得太远，相交边的数目要尽量少，有对称性等等。

2012-10-01