NLP（Natural language processing）自然语言处理一直都是比较热门的领域，现在不管是搜索，推荐神马的基本都需要和nlp打交道，而中文的nlp处理的第一步就是分词了，所以中文分词一直扮演者举足轻重的角色。当然了，分词的算法也是层出不穷，从最初的字典匹配到后来的统计模型，从HMM到CRF，分词精度都在不断提高，下面我就简单介绍下基本的分词算法。字典匹配最简单的分词就是基于字典匹配，一个句子“浅谈中文分词”，如果字典中我有这三个词“浅谈”“中文”“分词”那么我自然就可以把句子进行分词了。基于字典匹配随之而来的问题就是有多个匹配的情况，比如有“北京”“北京大学”两个词，这时来了个句子“北京大学在哪里”，应该用“北京”去匹配还是用“北京大学”去匹配，于是人们提出了很多启发式的匹配方案，比如最经典的最大匹配，就是尽可能的匹配最长的词，还有类似分词后分出的词的个数尽量少等启发规则，于是有了mmseg算法，提出了一些比较好的启发规则，而且实际应用时效果也很不错，所以应用很广泛，具体细节大家自行搜索，这里不在赘述。统计模型很快基于字典的分词还是会暴露出很多的问题，最主要的问题就是歧义的问题，比如“武汉市长江大桥”，不同的分词可能会变成“武汉/市长/江大桥”和“武汉市/长江/大桥”，显然字典匹配是不能解决这样的歧义问题的，于是有了统计的分词算法。在我的这篇文章里介绍的就是一元 ...继续阅读 (18)

最近看到flash-gear上你可以上传图片，然后自动帮你生成拼图，而且还能选择块的大小，话说，如果块很小，人力去拼图还真有些崩溃，于是本着geek的原则，打算用程序来搞一搞。首先我上传了图片生成了这个拼图，就是上面的那个图片的样子，然后我们可以看到有很多小碎片，而且是慢慢出现的，于是我就考虑是不是通过网络来请求的呢，于是用了chrome的审查元素，发现没有多与的http请求，于是我又想会不会是flash通过tcp请求来获得的呢，于是用了wireshark抓包，发现依然毫无所获，看来应该是图片都已经存储在flash文件里了。审查元素可以看到 http://three.flash-gear.com/npuz/puz.php?c=z&o=2&id=3986907&k=72291300&s=30&w=180&h=180&f_dm=three 这个请求的时间最长了，于是猜测这个应该是小碎片的flash文件，于是用下面的命令我们可以得到这个flash文件。wget "http://three.flash-gear.com/npuz/puz.php?c=z&o;=2&id;=3986907&k;=72291300&s;=30&w;=180&h;=180&f;_dm=three" -O test.swfok，文件得到了，打开看 ...继续阅读 (12)

以前一直不明白lock free是什么，后来发现原来是完全理解错了概念，lock free看到大家有的翻译为无锁，有的翻译为锁无关，其实用不用锁和lock free是不相关的，用了锁也可能是lock free，而不用锁有可能不是lock free。一个lock free的解释是一个“锁无关”的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。其实看我们那副图就是说你的各个线程不会互相阻塞，那么你的程序才能成为lock free的。像我们平常用的互斥锁，当有线程获得锁，其他线程就被阻塞掉了，这里的问题就是如果获得锁的线程挂掉了，而且锁也没有释放，那么整个程序其实就被block在那了，而如果程序是lock free的那么即使有线程挂掉，也不影响整个程序继续向下进行，也就是系统在整体上而言是一直前进的。那么，不用锁就是lock free的吗，一开始就提到了，不用锁也可能不是lock free的，举个例子while(x==0){x=1-x;}在这里如果两个线程同时执行，可能同时进入while循环，然后x两次改变值之后，依然是0，那么两个线程就会一直互相在这里阻塞掉了，所以这里虽然没有锁，依然不是lock free的。现在大家写lock free的时候一般都会使用CAS（compare and set）操作来写，因为现在很多的cpu都是支持CAS操 ...继续阅读 (21)

昨天在hacker news上看到regex golf，这里可以做几道很有趣的正则表达式的题，做题过程中有的需要用到不匹配这种匹配，比如说我需要匹配不包含某个单词的串。先来看看正则表达式的语法吧。[abc]a或b或c.任意单个字符a?零个或一个a[^abc]任意不是abc的字符\s空格a*零个或多个a[a-z]a-z的任意字符\S非空格a+一个或多个a[a-zA-Z]a-z或A-Z\d任意数字a{n}正好出现n次a^一行开头\D任意非数字a{n,}至少出现n次a$一行末尾\w任意字母数字或下划线a{n,m}出现n-m次a(...)括号用于分组\W任意非字母数字或下划线a*?零个或多个a(非贪婪)(a|b)a或b\b单词边界(a)...\1引用分组(?=a)前面有a(?!a)前面没有a\B非单词边界我们看到，正则表达式中有(?=a)和(?!a)来表示我们是否需要匹配某个东西。所以我们有需要不匹配某样东西的时候我们就可以用(?!a)了。比如说我们要匹配不含hello的字符串就可以这样写。^(?!.*hello)这里.*用来表示hello之前可能有其他的字符，为什么还要加^呢，因为如果不加的话，可能匹配到h之后的这个位置上了。我们现在就可以解决regex golf上的abba这道题了。这道题是让我们去匹配不含abba这种形式的单词，比如abba，anallagmatic就不应该匹配上。所 ...继续阅读 (21)

中文自然语言处理最首要的就是要中文分词了，现在而言效果最好的还是要算crf了，具体可以查看Stanford NLP，不过鉴于crf速度比较慢，而且咱对其还没有完全的理解，所以这里就没有比较crf算法了。这里主要比较的是最大匹配算法，隐马尔可夫，uni-gram，和一种character based generative model这四种进行比较。在52nlp上的这篇文章介绍到了Bakeoff 2005的数据。SIGHAN是国际计算语言学会（ACL）中文语言处理小组的简称，其英文全称为“Special Interest Group for Chinese Language Processing of the Association for Computational Linguistics”，而Bakeoff则是SIGHAN所主办的国际中文语言处理竞赛，然后在Bakeoff 2005的主页上，我们可以下载到用于测试的数据，数据主要是由北京大学，微软亚洲研究院，香港城市大学，台湾中央研究院提供。下载后可以看到包括doc，training，gold，scripts，testing几个文件夹，其中training中有训练用的分词好的数据，testing中有测试用的未分词的数据，gold中有用于检验的测试的分词好的数据，scripts里是包括一个最大匹配分词的脚本和一个计算分数的脚本，而且数 ...继续阅读 (22)

当时yahoo以3000万美元的价格收购了summly的消息传出来之后，貌似大家都比变的对自动摘要产生了极大的兴趣，关于自导摘要wiki这里有很详细的介绍，一般自动摘要比较常用的一个是摘取文章中的关键词，另一个则是摘取文章中的关键的句子，在这里我主要是介绍用textrank算法来搞句子的摘取。相对于textrank，摘取关键句子还有一些比较简单的算法，比如这篇，我们可以把句子分别和整篇文章做比较，相似性最大的就是关键的句子。而textrank其实就是pagerank算法扩展到句子上，来的到一些全局的信息。textrank的论文在这里。首先我们看pagerank算法，就是google用的那个网页排序的pagerank算法，首先网页之间都是有超链接链接的，如果某个网站A有指向B的超链接，说明A网站认为B网站是有价值的，于是相应的我们可以给B来提升权重，但是就像现实中，一般人的意见和专家的意见的权重是不一样的，所以如果网站A的权重比较高，那么就可以贡献更多的权重给B，反之则贡献更少的权重，然后算法经过一轮轮的迭代，所有结点的权重会收敛，就得到了最终的权重了。然后我们有pagerank的计算公式，其中d是阻尼系数。\(score(V_i)=(1-d)+d*\sum{\frac{1}{|out(V_j)|}*score(V_j)}\)换到textrank，对于pagerank而言，边是没有权 ...继续阅读 (23)

最近两周去美国东部转了转，7号北京走的，23号回到的北京，这之间去了纽约，波士顿，尼亚加拉瀑布，费城，华盛顿，玩的还是很开心的，记录一下过程，也对之后有兴趣去美国东部玩的同学有所帮助吧。去美国首要要弄好的就是护照和签证了，护照一般在户口所在地随便搞搞就好了，有效期也很长一般十多年吧，然后就是签证，需要填DS-160的表格，然后我签的是旅游签证B1，由于之前去过一次美国，所以这次是通过中信银行代签的所以很顺利，签证的有效期是1年，1年内可以随便去，一般在美国境内可以待的时间能长大6个月。然后就是机票了，机票还是要提前买才能便宜啊，我是直接在网上买的机票，往返机票而且都有一次转机，这样相对会便宜很多，机票买好了，到时直接去机场通过护照领取登机牌就可以上飞机了。于是7号坐的飞机，首先是到了旧金山，然后转了趟飞机，就飞到纽约了，值得一提的是，国际航班都是提供食物的，所以如果飞机是中午起飞一般不用吃中午饭，在飞机上吃就好了，而且是完全免费的，而美国国内的航班吃的是要花钱的。然后到了纽约就要考虑交通工具的问题了，美国有钱人比较多，大家普遍都在开车，相对的，公交车系统不是很发达，不过纽约还是不错的，地铁和公交都是挺方便的，纽约可以买一种7天的pass，这样7天内，地铁和公交都可以随便做。坐的时候一定要看清，因为很多地铁都是共用线路的，所以在一个地方回来很多不同的地铁。一般在旅馆或者一些景点都可以 ...继续阅读 (20)

最近看到这个网站http://gurmeet.net/puzzles/很不错啊，有很多有意思的谜题，而且还有详细的答案，最下面还给了些其他的谜题网站，然后今天终于把所有题看完了，有一些经常见到的题，也有一些第一次见的题，我挑出几道有意思的和大家分享一下。1、有红，绿，黄三种颜色的球各两个，每种球都分为轻球和重球，三个轻球一样重，三个重球一样重，天平称两次，找到三个重球。2、三个人每人带了一个白帽子或者黑帽子，三个人要同时，每人都要么声明自己帽子的颜色要么是什么都不说，如果有人声明，并且所有的声明都是正确的，他们可以赢得游戏，如何实现决定一种策略使得赢的概率大于二分之一。3、有两条路，一条通往正确的地方，一条是错误的，路前有两个人，一个总是说真话，一个总是说谎话，如何只问一个问题找到正确的路；假设现在有三个人，一个总说真话，一个总说假话，第三个人有时说真话有时说假话，如何问两个问题找到正确的路。4、Alice想了一个1-1000范围内的一个整数，Bob可以询问一个数，Alice会告诉Bob正确的数比Bob的询问大了还是小了，如果Bob询问的数大了，Alice会等概率的在1-1000内重新选择一个数，Bob应该采取什么样的策略来猜数。5、一直一个多项式f(x)所有系数都是非负整数，如何选择两个数x1，x2从f(x1)，f(x2)来推断出多项式。6、有n个人，每人头上写了一个0~n-1的 ...继续阅读 (23)

因为c++没有拉圾回收的机制，所以，c++程序经常出现各种内存泄漏，一般而言，指针的new和delete需要对应，不然就会出现很严重的问题。而智能指针就是帮助我们自动管理指针的一种方式，比较常用的就是利用引用计数的方式，实现，当变量出了作用域时自动删除，当还有其他变量持有指针时不会删除。智能指针有很多实现方式，stl和boost库里都有实现，为了，便于理解和应用，我们来看看如何自己实现一个简单的智能指针。我这里要说的实现方式，是通过一个辅助类，来记录引用计数来操作的。看了很多其他人写的关于智能指针的内容，都没有说明为什么要这么实现。要自己想清楚智能指针的实现，首要的就是要去理解c++的内存分配和管理的方式。像很多c++书中说的那样，c++的内存存储主要分为两部分，栈和堆。我们声明的各种非指针的类型，比如int，char，类等都是分配在栈中的，这里面的内存是自动管理，我们不需要操心的，所以当这些内容超出了它的作用域时就会被自动回收。int*test1(){intx=2;int*xp=&x;returnxp;}voidtest2(){int*xp=test1();*xp=3;}像这样的调用是有问题的，xp的指针是指向x的内存地址的，当出了test1函数的作用域时x会被回收，再对这个地址操作就是有问题 ...继续阅读 (17)

Clojure是运行在java虚拟机上的一种lisp的方言。说道lisp的话最先想到的应该是函数式编程，括号之类的词语，话说大家在读了《黑客与画家》这本书后肯定都会觉得lisp很厉害，都想来试试。而clojure作为lisp的一种方言，当然是包含了lisp的各种强大特点，而lisp的很强大很灵活的一个原因要归功于他的宏。说道宏的话，c里也是有宏的概念的，而lisp的宏其实本质和c里的宏都是一样的，都是做代码替换，但是lisp的宏应用起来更加强大。先来感受下clojure宏的方便之处。比如有很多地方我们需要print代码和变量内容来差错，于是我们可以写这样一个宏。(defmacrodbg[x]`(let[x# ~x](println '~x"="x#)x#))当我们需要检查这段代码的时候(defn tt[x](+x1))我们可以这样写(defn tt[x](dbg(+x1)))当我们运行代码的时候我们能得到相应的显示结果user=> (tt 1)(+ x 1) = 22看到我们用defmacro定义了一个dbg的宏，这个宏的作用就是现实代码段和代码执行的结果，并将结果返回回去。在clojure的 ...继续阅读 (12)