2014-04-05阅读(11802)评论(0)

3.1 基本概念 3.1.1 图 无向图、有向图、连通图和回路。 3.1.2 树 森林：无回路无向图。 树：无回路连通无向图。 根树：有根节点的树。 3.1.3 字符串 Σ：是字符表。 字符串：由Σ中字符相连而成的有限序列被称之为Σ 上的字...

2014-04-05阅读(7753)评论(1)

春暖花开，踏青时节，我看完了形式语言与自动机这一章这一章提到字符串编辑距离，于是动手实现了几个。编辑距离主要用于拼写纠错，貌似Google 2013的校招笔试题里就有这个。 常见的编辑距离定义 通过插入删除或替换使得一个字符串变为另一个字符...

2014-04-03阅读(17828)评论(26)

看过很多书，也走过很多弯路，干脆自己写了本《自然语言处理入门》，应该算是入门的最短路径。 最近买了一系列自然语言处理的书，块头大，内容深奥。如果单纯地看一遍的话，估计如同流水无痕。不如也发扬烂笔头（烂键盘）的优良传统，将重点简明扼要地记下来...

2014-03-26阅读(33775)评论(39)

谈起自动摘要算法，常见的并且最易实现的当属TF-IDF，但是感觉TF-IDF效果一般，不如TextRank好。 TextRank是在Google的PageRank算法启发下，针对文本里的句子设计的权重算法，目标是自动摘要。它利用投票的原理，...

2014-03-22阅读(11639)评论(8)

很久之前写的东西，有不少谬误。维特比算法应该特指定义在栅格网络上的动态规划算法，其在分词中的应用请参考维特比算法。 在维特比算法通俗理解中，记录了我对维特比算法的粗浅理解，这里结合Ansj中文分词的源码，记录一下维特比算法在分词中的应用。 ...

2014-03-22阅读(17780)评论(5)

维特比算法说白了就是动态规划实现最短路径，只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法 维特比算法是一个特殊但应用最广的动态规划算法，利用动态规划，可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆...

2014-03-19阅读(9065)评论(4)

事实上，ansj实现的双数组没有通用性，你也无法往里面加入自己的词语，或者删除任何词语。我实现了一个通用的双数组trie树，提供更灵活的接口，更高的速度：http://www.hankcs.com/nlp/hanlp.html。 array...

2014-03-18阅读(39303)评论(65)

双数组Trie树(DoubleArrayTrie)是一种空间复杂度低的Trie树，应用于字符区间大的语言（如中文、日文等）分词领域。 双数组Trie (Double-Array Trie)结构由日本人JUN-ICHI AOE于1989年提出...