China Drupal Blog

N-Gram有很多应用，但是我们只用来做相似分析。基本思路来自Grzegorz Kondrak 2005年的一篇论文。http://webdocs.cs.ualberta.ca/~kondrak/papers/spire05.pdf

最近在做Translation memory的时候用到比较字符串相似度的算法。在机器翻译或者语言识别领域之所以能使用相似度算法其实是基于一种假设，相似的词具有相似的意义。

什么是N-Gram算法？
N-Gram 模型基于这样一种假设，第n个词的出现只与前面n-1个词相关，而与其它任何词都不相关，整句的概率就是各个词出现概率的乘积。在拼写检查里即是一个字母的出现概率只和前n-1个字母的出现概率相关,并且是前n-1个字母出现概率的乘积。
如何比较2个字符串的相似度？

一般情况我们会考虑用edit distance 或者LCS。前边的论文证实了这两种算法都是N-Gram的简化版本。

在搜索引擎里一般是用来做拼写检查或者提示，比如你在百度或者google输入一个词就会有相关的词提示出来。

　近来不少的朋友问我关于 A* 算法的问题, 目的是写一个搜索最短路径的程序. 这个在鼠标控制精灵运动的游戏中(不算智冠出的那些用鼠标充当键盘方向键的弱智 RPG)大量使用,尤其是即时战略类的. 但是我个人认为 A* 算法只适合处理静态路径求解,对即时战略游戏中大量对象堵塞过道时,疏通交通很难实现(也不是不能实现, 这需要一个相当好的估价函数,且不能一次搜索路径)

　　我奇怪的是, A* 算法应该是算法课的基础知识了, 任何一个系统学习过算法的人都应该了解, 本不应该我在这里乱写一通, 大家随意翻本将计算机算法的书, 就应该看的到. (将 AI 的书了更是少不了) 不过既然许多朋友问起, 在各个讨论组, BBS 等地方也屡次见人提到, 特花一下午时间完成本文和附带的程序, 满足我们广大业余游戏制作爱好者的求知欲, 专业人士免看, 以免班门弄斧 ^_^ 不过如有错误一定指出哟.

　　如果您的上网时间很宝贵,请下载我注释过的源码(3k)离线研究

　　在介绍 A* 算法前,先提一下广度优先搜索,广度优先搜索就是每次将当前状态可能发展的策略逐层展开,比如一个地图中,对象允许向四个方向移动, 那么,就将地点处,对象向上下左右各移动一步, 将四个状态都保存在内存中, 然后再从这四个出发点向各自的四个方向再移动一步… (当然这里可以剔除不合理的移动方法,比如不准向回移动)实际上, 整个搜索好似一个圆形向外展开,直到到达目的地,很明显这样求解一定能找到最优解,但节点展开的数量是和距离成级数增加的, 真的用在游戏中, 玩家会抱怨内存128M 也不够用了 ^_^ 而且伴随待处理节点数的增加, 处理速度也会迅速减慢… 可以说这个算法并不实用

　　而 A* 算法实际是一种启发式搜索, 所谓启发式搜索,就是利用一个估价函数评估每次的的决策的价值, 决定先尝试哪一种方案. 这样可以极大的优化普通的广度优先搜索. 一般来说, 从出发点(A)到目的地(B)的最短距离是固定的,我们可以写一个函数 judge() 估计 A 到 B 的最短距离, 如果程序已经尝试着从出发点(A) 沿着某条路线移动到了 C 点, 那么我们认为这个方案的 A B 间的估计距离为 A 到 C 实际已经行走了的距离 H 加上用 judge() 估计出的 C 到 B 的距离. 如此, 无论我们的程序搜索展开到哪一步, 都会算出一个评估值, 每一次决策后, 将评估值和等待处理的方案一起排序, 然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步, 一直循环到对象移动到目的地, 或所有方案都尝试过却没有找到一条通向目的地的路径则结束. (通常在游戏里还要设置超时控制的代码,当内存消耗过大或用时过久就退出搜索)

　　完了? 没有. 怎么写这个算法中的估价函数非常的重要,如何保证一定能找到最短路径呢? 充要条件是, 你的估价函数算出的两点间的距离必须小于等于实际距离. 这个可以从数学上严格证明,有兴趣可以自己去查阅相关资料. 如果你的估价函数不满足这点, 就只能叫做 A 算法, 并不能保证最后的结果是最优的,但它可能速度非常的快. 而游戏中我们也不一定非要得到最优解的. 但无疑, 满足那个条件的 A* 算法中, 估计值越接近真实值的估价函数就做的越好, 下面给出的程序,我只使用了一个相当简单的估价函数: 求出两点中,若无障碍物的情况下的最短路径. 如果您想写出快速的寻路算法, 请自己寻找好的估价函数吧,有时间的时候,我会对此另文叙述 ;-)

—————————————————————

转贴的。
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。
　　启发中的估价是用估价函数表示的，如：

f(n) = g(n) + h(n) 

　　其中f(n) 是节点n的估价函数，g(n)实在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。如果说详细点，g(n)代表了搜索的广度的优先趋势。但是当h(n) >> g(n)时，可以省略g(n)，而提高效率。
启发式搜索其实有很多的算法，比如：局部择优搜索法、最好优先搜索法等等。当然A*也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。象局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。最好优先就聪明多了，他在搜索时，便没有舍弃节点（除非该节点是死节点），在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢？其实A*算法也是一种最好优先的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：

f’(n) = g’(n) + h’(n) 

　　这里，f’(n)是估价函数，g’(n)是起点到终点的最短路径值，h’(n)是n到目标的最断路经的启发值。由于这个f’(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g’(n)，但 g(n)>=g’(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h’(n)，但h(n)<=h’(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。
　　举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h’(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。
再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。

余弦定理和新闻的分类似乎是两件八杆子打不着的事，但是它们确有紧密的联系。具体说，新闻的分类很大程度上依靠余弦定理。

Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻，它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点，我们需要想办法用一组数字来描述一篇新闻。

我们来看看怎样找一组数字，或者说一个向量来描述一篇新闻。回忆一下我们在“如何度量网页相关性”一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有实词，我们可以计算出它们的单文本词汇频率/逆文本频率值（TF/IDF)。不难想象，和新闻主题有关的那些实词频率高，TF/IDF 值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如，词汇表有六万四千个词，分别为

单词编号 汉字词
——————
1 阿
2 啊
3 阿斗
4 阿姨
…
789 服装
….
64000 做作

在一篇新闻中，这 64,000 个词的 TF/IDF 值分别为

单词编号 TF/IDF 值
==============
1 0
2 0.0034
3 0
4 0.00052
5 0
…
789 0.034
…
64000 0.075

如果单词表中的某个次在新闻中没有出现，对应的值为零，那么这 64,000 个数，组成一个64,000维的向量。我们就用这个向量来代表这篇新闻，并成为新闻的特征向量。如果两篇新闻的特征向量相近，则对应的新闻内容相似，它们应当归在一类，反之亦然。

学过向量代数的人都知道，向量实际上是多维空间中有方向的线段。如果两个向量的方向一致，即夹角接近零，那么这两个向量就相近。而要确定两个向量方向是否一致，这就要用到余弦定理计算向量的夹角了。

余弦定理对我们每个人都不陌生，它描述了三角形中任何一个夹角和三个边的关系，换句话说，给定三角形的三条边，我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为 a, b 和 c，对应的三个角为 A, B 和 C，那么角 A 的余弦 –

如果我们将三角形的两边 b 和 c 看成是两个向量，那么上述公式等价于

其中分母表示两个向量 b 和 c 的长度，分子表示两个向量的内积。举一个具体的例子，假如新闻 X 和新闻 Y 对应向量分别是
x1,x2,…,x64000 和
y1,y2,…,y64000,
那么它们夹角的余弦等于，

当两条新闻向量夹角的余弦等于一时，这两条新闻完全重复（用这个办法可以删除重复的网页）；当夹角的余弦接近于一时，两条新闻相似，从而可以归成一类；夹角的余弦越小，两条新闻越不相关。

我们在中学学习余弦定理时，恐怕很难想象它可以用来对新闻进行分类。在这里，我们再一次看到数学工具的用途。