« Posts under Computer Science

统计自然语言理解的两本书

接下来会做一个跟自然语言处理(Natural Language Processing, nlp)相关的工程,因为我之前几乎没有接触过这方面的知识,而且自己的语文也实在烂得可以...(所以这次怎么也得用统计的方法来做了= =)就趁十一在家有空补点课。

作为一个超级门外汉,选几本合适的入门教材开始啃乃当务之急。一般而言,对于此类前沿技术的学习最好从理论和实践两个方面入手,一方面要了解理论知识,学习别人对于问题的解决思路和方法;另一方面,要找一些实际能够动手操作的实验资料,通过实验了解理论中存在的问题以及改进的方向。在自然语言处理方向尤为如此。英文和中文之间存在巨大差异,就我个人感觉而言,英文虽然算不上特别严谨的语言,但其语法结构相对中文要清晰很多,加上中文一词多义、一字多义的现象普遍存在,完全照搬英文语言理解的理论来处理中文是不合适的。所以,在学习他人的知识的同时必须要自己动手试试,从而才能认识到中英文之间的区别,才能知道哪些前人的知识可以沿用,哪些需要修改。

»Read More

多边形封闭区域算法

前些天在考虑一个几何算法,关于如何判断一个点是否在一个给定的多边形内部。这应该是一个比较常规的算法,我以前对几何算法了解的不多,所以既然想到了就稍微研究了一下。
查了一下相关的资料,目前有几个O(N)的算法,其中N是多边形的顶点数。

第一个叫做交替(Alternative)算法。 如下图所示

交替法

»Read More

Code Jam 2009 Qualification :: 我去打酱油

Code Jam 2009今天进入了资格赛,我算法很弱...纯粹属于打酱油去的选手...

简单说明一下资格赛的题目,一共有3道题目:

1. Alien Language (外星语)

题目大致的意思是,人类掌握了一本外星语字典,然后手头上有部分外星语的碎片看不清楚,其中某些字符可能是多个字符中的一个,要你根据已经掌握的字典计算外星语碎片上的文字共有多少种可能性。

»Read More