2017年12月

首页2017年12月
28
Dec
0

for和forEach与each

forEach是ES5中操作数组的一种方法,主要功能是遍历数组,例如:
var arr = [1,2,3,4];
arr.forEach(alert);
等价于:
var arr = [1, 2, 3, 4];
for (var k = 0, length = arr.length; k < length; k++) {
alert(array[k]);
}
forEach方法中的function回调有三个参数:第一个参数是遍历的数组内容,第二个参数是对应的数组索引,第三个参数是数组本身

因此:
[].forEach(function(value,index,array){

    //code something

  });
  

等价于:
$.each([],function(index,value,array){

   //code something

 })
  

写一个例子
var arr = [1,2,3,4];
arr.forEach(function(value,index,array){

array[index] == value;    //结果为true
sum+=value;  
});

console.log(sum); //结果为 10

map:map即是 “映射”的意思 用法与 forEach 相似,用法即:
[].map(function(value,index,array){

  //code

})

25
Dec
0

python分析工具所用勾子

line_profiler 使用PyEval_SetTrace设置回调:
看line_profiler.pyx的157行
cProfiles 使用PyEval_SetProfile设置回调:
看_lsprof.c的693行(cProfile是用Isprof实现的)

25
Dec
0
25
Dec
0

后缀树的构造方法-Ukkonen详解

三鲜 序
原来是打算翻译Sartaj Sahni的Suffix tree, 并专注地进行了一周, 连复习备考的时间也不惜占去. 我希望给国产的同好者提供更通俗易懂的资料, 在翻译的同时对原文进行了删改, 并加入了许多自己的心得. 然而后来发现了Mark Nelson的这篇文章, 相比之下更有亲和力, 于是老实地尽弃前功来翻译这篇. 更重要一个原因是, Mark Nelson介绍的是Ukkonen的构造法O(n), 它比Sartaj Sahni的构造法O(nr), r为字母表大小 在时间上更有优势. 但我们不能说Sartaj Sahni的算法慢, 因为r往往会很小, 因此实际效率也接近线性, 两种构造法在思想上均有可取之处.

本文偏重于阐述后缀树的构造过程, 而并没有直接介绍后缀树除了匹配以外还能做什么. 其实后缀树是一种功能非常强大的数据结构, 你可以去搜索引擎了解一下它还有多少功能, 当然我最希望的是你在阅读本文之后已经足以体会后缀树的妙处, 日后遇到诸多问题的时候都能随心随意地用上.

最后唠叨一句. 我所见过的各种介绍后缀树的论文都难免使初学者陷入混乱, 本文估计也好不到哪里去. 这在一定程度上说明了后缀树的原理是不太浅显的, 理解它需要在整体上把握, 建议希望读者先不要纠结于细节, 思路不清则反复阅读.

问题的来源
字符串匹配问题是程序员经常要面对的问题. 字符串匹配算法的改进可以使许多工程受益良多, 比如数据压缩和DNA排列. 这篇文章讨论的是一种相对鲜为人知的数据结构 --- 后缀树, 并介绍它是如何通过自身的特性去解决一些复杂的匹配问题.

你可以把自己想象成一名工作于DNA排列工程的程序员. 那些基因研究者们天天忙着分切病毒的基因材料, 制造出一段一段的核苷酸序列. 他们把这些序列发到你的服务器里, 指望你在基因数据库中定位. 要知道, 你的数据库里有数百种病毒的数据, 而一个特定的病毒可以有成千上万的碱基. 你的程序必须像C/S工程那样实时向博士们反馈信息, 这需要一个很好的方案.

很明显, 在这个问题上采取暴力算法是极其低效的. 这种方法需要你在基因数据库里对比每一个核苷酸, 测试一个较长的基因段基本会把你的C/S系统变成一台古老的批处理机.

直觉上的解决方法
由于基因数据库一般是不变的, 通过预处理来把搜索简化或许是个好主意. 一种预处理的方法是建立一棵Trie. 我们通过Trie引申出一种东西叫作后缀Trie. (后缀Trie离后缀树仅一步之遥.) 首先, Trie是一种n叉树, n为字母表大小, 每个节点表示从根节点到此节点所经过的所有字符组成的字符串. 而后缀Trie的 “后缀” 说明这棵Trie包含了所给字段的所有后缀 (也许正是一个病毒基因).

后缀trie

图1
2.jpg
BANANAS的后缀Trie

图1展示了文本BANANAS的后缀Trie. 关于这棵Trie有两个地方需要注意. 第一, 从根节点开始, BANANAS的每一个后缀都插入到Trie中, 包括BANANAS, ANANAS, NANAS, ANAS, NAS, AS, S. 第二, 鉴于这种结构, 你可以通过从根节点往下匹配的方式搜索到单词的任何一个子串.

这里所说的第二点正是我们认为后缀Trie优秀的原因. 如果你输入一个长度为N的文本并想在其中搜索一个长度为M的串, 传统的暴力匹配需要进行N*M次字符对比, 而一些改进过的匹配技术, 比如像Boyer-Moore算法, 可以在O(N+M)的时间开销内解决问题, 平均效率更是令人满意. 然而, 后缀Trie亮出了O(M)的牌子, 彻底鄙视了其他算法的成绩, 后缀Trie对比的次数仅仅相当于被搜索串的长度!

这确实是可圈可点的威力, 这意味着你能通过仅仅7次对比便在莎士比亚所有作品中找出BANANAS. 但有一点我们可不能忘了, 构造后缀Trie也是需要时间的.

后缀Trie之所以没有家喻户晓正是因为构造它需要O(n2)的时间和空间. 平方级的开销使它在最需要它的领域 --- 长串搜索 中被拒之门外.

横空出世
直到1976年, Edward McCreigh发表了一篇论文, 咱们的后缀树问世了. 后缀Trie的困境被彻底打破.

后缀树跟后缀Trie有着一样的布局, 但它把只有一个儿子的节点给剔除了. 这个过程被称为路径压缩, 这意味着树上的某些边将表示一个序列而不是单独的字符.

trie

图2
3.jpg
BANANAS的后缀树

图2是由图1的后缀Trie转化而来的后缀树. 你会发现这树基本还是那个形状, 只是节点变少了. 在剔除了只有一个儿子的节点之后, 总节点数由23降为11. 经过证明, 在最坏情况下, 后缀树的节点数也不会超过2N (N为文本的长度). 这使构造后缀树的线性时空开销成为可能.

然而, McCreight最初的构造法是有些缺陷的, 原则上它要按逆序构造, 也就是说字符要从末端开始插入. 如此一来, 便不能作为在线算法, 它变得更加难以应用于实际问题, 如数据压缩.

20年后, 来自赫尔辛基理工大学的Esko Ukkonen把原算法作了一些改动, 把它变成了从左往右. 本文接下来的所有描述和代码都是基于Esko Ukkonen的成果.

对于所给的文本T, Esko Ukkonen的算法是由一棵空树开始, 逐步构造T的每个前缀的后缀树. 比如我们构造BANANAS的后缀树, 先由B开始, 接着是BA, 然后BAN, … . 不断更新直到构造出BANANAS的后缀树.

trie

图3
4.jpg

逐步构造后缀树

初窥门径
加入一个新的前缀需要访问树中已有的后缀. 我们从最长的一个后缀开始(图3中的BAN), 一直访问到最短的后缀(空后缀). 每个后缀会在以下三种节点的其中一种结束.

l 一个叶节点. 这个是常识了, 图4中标号为1, 2, 4, 5的就是叶节点.

l 一个显式节点. 图4中标号为0, 3的是显式节点, 它表示该节点之后至少有两条边.

l 一个隐式节点. 图4中, 前缀BO, BOO, 或者非前缀OO, 它们都在某条表示序列的边上结束, 这些位置就叫作隐式节点. 它表示后缀Trie中存在的由于路径压缩而剔除的节点. 在后缀树的构造过程中, 有时要把一些隐式节点转化为显式节点.

trie

图4
5.gif
加入BOOK之后的BOOKKEEPER

(也就是BOOK的后缀树)

如图4, 在加入BOOK之后, 树中有5个后缀(包括空后缀). 那么要构造下一个前缀BOOKK的后缀树的话, 只需要访问树中已存在的每一个后缀, 然后在它们的末尾加上K.

前4个后缀BOOK, OOK, OK和K都在叶节点上结束. 由于我们要路径压缩, 只需要在通往叶节点的边上直接加一个字符, 而不需要创建一个新节点.

在所有叶节点更新之后, 我们还需要在空后缀后面加上K. 这时候我们发现已经存在一条从0节点出发的边的首字符为K, 没必要画蛇添足了. 换句话说, 新加入的后缀K可以在0节点和2节点之间的隐式节点中找到. 最终形态见图5.

trie
6.jpg
图5加入BOOKK之后的BOOKKEEPER

相比图4, 树的结构没有发生变化

如果你是一位敏感的读者, 可能要发问了, 如果加入K我们什么都不做的话, 在查找的时候如何知道它到底是一个后缀呢还是某个后缀的一截? 如果你同时又是一位熟悉字符串算法的朋友, 心里可能马上就有答案了 --- 我们只需要在文本后面加个字母表以外的字符, 比如$或者#. 那我们查找到K$或K#的话就说明这是一个后缀了.

稍微麻烦一点的事情
从图4到图5这个更新过程是相对简单的, 其中我们执行了两种更新: 一种是将某条边延长, 另一种是啥都不做. 但接下来往图5继续加入BOOKKE, 我们则会遇到另外两种更新:

  1. 创建一个新节点来割开某一隐式节点所处的边, 并在其后加一条新边.
  1. 在显式节点后加一条新边.

trie

图6
7.jpg
先分割, 再添加

当我们往图5的树中加入BOOKKE的时候, 我们是从已存在的最长后缀BOOKK开始, 一直操作到最短的后缀空后缀. 更新最长的后缀必然是更新叶节点, 之前提到了, 非常简单. 除此之外, 图5中结束在叶节点上的后缀还有OOKK, OKK, KK. 图6的第一棵树展示了这一类节点的更新.

图5中首个不是结束在叶节点上的后缀是K. 这里我们先引入一个定义:

在每次更新后缀树的过程中, 第一个非叶节点称为激活节点. 它有以下性质:

  1. 所有比激活节点长的后缀都在叶节点上结束.
  1. 所有在激活节点之后加入的后缀都不在叶节点上结束.

后缀K在边KKE上的隐式节点结束. 在后缀树中我们要判断一个节点是不是非叶节点需要看它是否有跟待加入字符相同的儿子, 即本例中的E.

一眼可以看出, KKE中的第一个K只有一个儿子: K. 所以它是非叶节点(这里同时也是激活节点), 我们要给他加一个儿子来表示E. 这个过程有两个步骤:

  1. 在第一个K和第二个K之间把边分割开, 于是第一个K(隐式节点)成了一个显式节点, 如图6第二棵树.
  1. 在刚刚变身而来的显式节点后加一个新节点表示E, 如图6第三棵树. 由此我们又多了一个叶节点.

后缀K更新之后, 别忘了还有空后缀. 空后缀在根节点(节点0)结束, 显然此时根节点是一个显式节点. 我们看一下它后面有没有以E开头的边---没有, 那么加入一个新的叶节点(如果存在以E开头的边, 则不用任何操作). 最终如图7.

trie

图7
8.jpg

归纳, 反思, 优化
借助后缀树的特性, 我们可以做出一个相当有效的算法. 首先一个重要的特性是: 一朝为叶, 终生为叶. 一个叶节点自诞生以后绝不会有子孙. 更重要的是, 每当我们往树上加入一个新的前缀, 每一条通往叶节点的边都会延长一个字符(新前缀的最后一个字符). 这使得处理通往叶节点的边变得异常简单, 我们完全可以在创建叶节点的时候就把当前字符到文本末的所有字符一股脑塞进去. 是的, 我们不需要知道后面的字符是啥, 但我们知道它们最终都要被加进去. 因此, 一个叶节点诞生的时候, 也正是它可以被我们遗忘的时候. 你可能会担心通往叶节点的边被分割了怎么办, 那也不要紧, 分割之后只是起点变了, 尾部该怎么着还是怎么着.

如此一来, 我们只需要关心显式节点和隐式节点上的更新.

还要提到一个节约时间的方法. 当我们遍历所有后缀时, 如果某个后缀的某个儿子跟待加字符(新前缀最后一个字符)相同, 那么我们当前前缀的所有更新就可以停止了. 如果你理解了后缀树的本质, 你会知道一旦待加字符跟某个后缀的某个儿子相同, 那么更短的后缀必然也有这个儿子. 我们不妨把首个这样的节点定义为结束节点. 比结束节点长的后缀必然是叶节点, 这一点很好解释, 要么本来就是叶节点, 要么就是新创建的节点(新创建的必然是叶节点). 这意味着, 每一个前缀更新完之后, 当前的结束节点将成为下一轮更新的激活节点.

好了, 现在我们可以把后缀树的更新限制在激活节点和结束节点之间, 效率有了很大的改善. 整理成伪代码如下:

PLAIN TEXT

C:

  1. Update( 新前缀 )
  2. {
  3. 当前后缀 = 激活节点
  4. 待加字符 = 新前缀最后一个字符
  5. done = false;
  6. while ( !done ) {
  7. if ( 当前后缀在显式节点结束 ) {
  8. if ( 当前节点后没有以待加字符开始的边 )
  9. 在当前节点后创建一个新的叶节点
  10. else
  11. done = true;
  12. } else {
  13. if ( 当前隐式节点的下一个字符不是待加字符 ) {
  14. 从隐式节点后分割此边
  15. 在分割处创建一个新的叶节点
  16. } else
  17. done = true;
  18. if ( 当前后缀是空后缀 )
  19. done = true;
  20. else
  21. 当前后缀 = 下一个更短的后缀
  22. }
  23. 激活节点 = 当前后缀
  24. }

后缀指针
上面的伪代码看上去很完美, 但它掩盖了一个问题. 注意到第21行, “下一个更短的后缀”, 如果呆板地沿着树枝去搜索我们想要的后缀, 那这种算法就不是线性的了. 要解决此问题, 我们得附加一种指针: 后缀指针. 后缀指针存在于每个结束在非叶节点的后缀上, 它指向“下一个更短的后缀”. 即, 如果一个后缀表示文本的第0到第N个字符, 那么它的后缀指针指向的节点表示文本的第1到第N个字符.

图8是文本ABABABC的后缀树. 第一个后缀指针在表示ABAB的节点上. ABAB的后缀指针指向表示BAB的节点. 同样地, BAB也有它的后缀指针, 指向AB. 如此这般.

http://img166.ph.126.net/_G1wwOmH9eeAiH1WhW3LNQ==/2189593843833692898.jpg

图8
9.jpg
加上后缀指针(虚线)的ABABABC的后缀树

介绍一下如何创建后缀指针. 后缀指针的创建是跟后缀树的更新同步的. 随着我们从激活节点移动到结束节点, 我把每个新的叶节点的父亲的路径保存下来. 每当创建一条新边, 我同时也在上一个叶节点的父亲那儿创建一个后缀指针来指向当前新边开始的节点. (显然, 我们不能在第一条新边上做这样的操作, 但除此之外都可以这么做.)

有了后缀指针, 就可以方便地一个后缀跳到另一个后缀. 这个关键性的附加品使得算法的时间上限成功降为O(N).

25
Dec
0

基于信息熵的无字典分词算法

这几天在研究如何用统计方法来发现新词,扩充自己的词典。看到了几篇很有想法的文章,作者阐述了一下思路。文章里面的数据,我计算了一下,发现文有很多数据不够严谨,最主要的问题,并没有给出很详细的理论方面的说明。结合作者的思路,我进行了如下数学模型的构建和算法的实现。

一、概念介绍

1、词语分片

设一个文档集 。其中,为一个文本,。

设 为文档的分片集合。其中,为文档的一个词语分片,分片就是按step步长对文档进行分割的词语单位。这里说的词语分片可以是一个字、一个词或者一个长词。

譬如:中国队,

按step=1进行切分 S={中,国,队}

按step=2进行切分 S={中,国,队,中国,国队}

按step=3进行切分 S={中,国,队,中国,国队,中国队}。

当然,这个定义可以推广到有字典的情况:

譬如 字典 {中国}

"中国国家队"的词语分片为{中国,国,家,队,中国国,国家,家队,中国国家,国家队,中国国家队}。

这样来看,一个文本分若干段落;一个段落通过标点符号进行分割,分割成若干短句,我们成为语义单元;一个语义单元按step步长进行切分成若干个词语切片。我们把所有切片合并成一个大集合。

2、分片属性

为了解决上面的问题,对于分片S我们从分片概率、分片频度、自由度、凝固程度等属性去考虑。这些属性都是概率变量。

这样,一个分片s用6个属性去进行描述

参数说明

f: 文档唯一标识

w: 分片的频度,表示分片在一种切分过程中出现的次数

s: 分片

co: 分片的凝固度

fr: 分片的自由度

st: 分片的概率

3、词语分片的概率

分片的概率,如果一个字串S长度为L,按stepN进行切分,切分出来的集合为M,为每个分片的频度。那么每一个分片的概率可以用下面公式表示:

----------------------------------------------------------(1)

S="中国国家的中国队",长度N = 8 按step=2进行切分,切分为

M={中,国,家,的,队,中国,国国,国家,家的,的中,国队}。

分片 中 国 家 的 队 中国 国国 国家 家的 的中 国队
频次 2 3 1 1 1 2 1 1 1 1 1 15 P
总计 2/15 3/15 1/15 1/15 1/15 2/15 1/15 1/15 1/15 1/15 1/15 100%

4、分片的凝固度

要想从一段文本中抽出词来,我们的第一个问题就是,怎样的文本片段才算一个词?大家想到的第一个标准或许是,看这个文本片段出现的次数是否足够多。我们可以把所有出现频数超过某个阈值的片段提取出来,作为该语料中的词汇输出。不过,光是出现频数高还不够,一个经常出现的文本片段有可能不是一个词,而是多个词构成的词组。通过我们的数据分析,"的电影"出现了 389 次,"电影院"只出现了 175 次,然而我们却更倾向于把"电影院"当作一个词,因为直觉上看,"电影"和"院"凝固得更紧一些。

为了描述这个属性,我们用一下公式:

---------------------------------(2)

为分片的概率,分片对应的子分片的概率。

 分片"电影院"的概率P(电影院)=0.0005 电影院对应的子分片 {电影,院} 和{电,影院},

"的电影"的凝合程度则是 p(的电影) 分别除以 p(的) · p(电影) 和 p(的电) · p(影) 所得的商的较小值。

光看文本片段内部的凝合程度还不够,我们还需要从整体来看它在外部的表现。考虑"被子"和"辈子"这两个片段。我们可以说"买被子"、"盖被子"、"进被子"、"好被子"、"这被子"等等,在"被子"前面加各种字;但"辈子"的用法却非常固定,除了"一辈子"、"这辈子"、"上辈子"、"下辈子",基本上"辈子"前面不能加别的字了。"辈子"这个文本片段左边可以出现的字太有限,以至于直觉上我们可能会认为,"辈子"并不单独成词,真正成词的其实是"一辈子"、"这辈子"之类的整体。可见,文本片段的自由运用程度也是判断它是否成词的重要标准。如果一个文本片段能够算作一个词的话,它应该能够灵活地出现在各种不同的环境中,具有非常丰富的左邻字集合和右邻字集合。

二、信息熵和自由度

"信息熵"是一个非常神奇的概念,它能够反映知道一个事件的结果后平均会给你带来多大的信息量。如果某个结果的发生概率为 p ,当你知道它确实发生了,你得到的信息量就被定义为 - log(p) 。 p 越小,你得到的信息量就越大。

设U1…Ui…Un,对应概率为:P1…Pi…Pn,且各种符号的出现彼此独立。这时,信源的平均不确定性应当为单个符号不确定性-logPi的统计平均值(E),可称为信息熵,即

----------------------------------------------(3)

式中对数一般取2为底,单位为比特。

我们用信息熵来衡量一个文本片段的左邻字集合和右邻字集合有多随机。考虑这么一句话"吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮","葡萄"一词出现了四次,其中左邻字分别为 {吃, 吐, 吃, 吐} ,右邻字分别为 {不, 皮, 倒, 皮} 。根据公式,"葡萄"一词的左邻字的信息熵为 - (1/2) · log(1/2) - (1/2) · log(1/2) ≈ 0.693 ,它的右邻字的信息熵则为 - (1/2) · log(1/2) - (1/4) · log(1/4) - (1/4) · log(1/4) ≈ 1.04 。可见,在这个句子中,"葡萄"一词的右邻字更加丰富一些。

我们不妨就把一个文本片段的自由运用程度定义为它的左邻字信息熵和右邻字信息熵中的较小值。

------------------------------------------(4)

通过信息熵算法,可以很好的区分一些专有名词像玫瑰、蝙蝠等,一些地名像新西兰、伦敦等,这些自由度较低的词汇的。

三、算法的构建

在实际运用中你会发现,文本片段的凝固程度和自由程度,两种判断标准缺一不可。只看凝固程度的话,程序会找出"巧克"、"俄罗"、"颜六色"、"柴可夫"等实际上是"半个词"的片段;只看自由程度的话,程序则会把"吃了一顿"、"看了一遍"、"睡了一晚"、"去了一趟"中的"了一"提取出来,因为它的左右邻字都太丰富了。
无词典分词法的基本步骤:

  1. 输入阀值参数 出现频数w、凝固程度co、自由程度fr和最大切片stepN,词典集合的大小N;
  2. 对文档集进行预处理,包括:编码转换、全半角 处理、字符转换,再将停用词、英文字母、数学运算符等其它非汉字字符用占位符替代;
  3. 从文档集里取一个文档D,按1,2,...,stepN进行切片形成切片集合S;
  4. 通过公式(1)计算切片集合S的每一个切片的频数W和概率P,通过给定频数阀值过滤;
  5. 结果4 中的长度>1的词语切片,通过公式(2)计算凝固程度,并通过给定的阀值参数过滤。
  6. 结果5 中的词语切片,通过公式(3)计算左邻右邻的信息熵,通过公式(4),得出词语切片的自由度,并通过给定的阀值参数过滤。
  7. 对于结果6,按照分片的频数倒排序,取前N个,就产生了我们需要的词典。

四、参考

《基于SNS的文本数据挖掘》http://www.matrix67.com/blog/archives/5044