Nagao的串频统计算法.pptVIP

Company LOGO Nagao的串频统计算法 王 晨 Contents 基本概念 算法思想 复杂度分析 实现举例 今后的工作 基本概念 字符串频率(string frequency) 一个符号串在文本中的出现次数，简称串频。 射串(semi-infinite string) 有起点无终点的半无限延伸字符串。通常一个符号串是有限长的，在其后加上无穷个数的结束符，就转化为一个射串。 一个长度为n 的字符串，逻辑上包含n 个射串，第k 个射串从原始字符串的第k 各位开始往后延伸。每个射串在理论上有无限长。 算法思想 1994 年东京大学的长尾真（Makoto Nagao）提出了一种新的串频统计算法。 这种算法的核心其实就是对文本中的射串进行排序构成一个有序射串。 算法思想（1） 把汉语语料库C(包括汉字、标点、段落分隔标识、文件分隔标识等所有字符)看成一个很长的字符串读入内存，并以Unicode 编码。每个字符占2字节空间。以下用Ci 表示C 中第i 个字符。如下图所示： 算法思想（2） 构造一个长为m 的P 表(pointer table)。P 表的每一项Pi 保存一个指向C 中子串Si 的指针。 Pi 指向的子串Si 定义为从Pi 所指字符Ci 到C 中最后一个字符Cm 中的m-i+1 个字符所组成的字符串。这样S1、S2,…,Sm 的串长依次递减,最后一个子串Sm 只包括一个字符Cm。如下图所示： 算法思想（2） 算法思想（3） 接下来可以在已排序的P 表的基础上构建记录相邻子串相同最长左子串长度的L 表。L 表与P 表大小相同,其中的表项Li 记录排序后相邻子串Spi-1 和Spi 相同最长左子串长度，即从串首开始相同字符的个数(L1=0)。 算法思想（3） 算法思想（4） 在构建好P 表和L 表之后,可使用如下算法对长度为N 的统计串进行串 串频统计:输入:P 表,L 表,N。 输出:所有N 元统计串及其频次。 P1 指向的N 元串赋给X, X 的频次置为1 for i=2 to m if Li≥N X 的频次加1 else 输出X 及其频次 Pi 指向的N 元串赋给X, X 的频次置为1 输出最后的X 及其频次 复杂度分析 假设语料有m 个字符 时间复杂度 Step1 、2 、4 时间复杂度为m,step 用快速排序， 时间复杂度为O(nlogn)，所以总的复杂度为O(nlogn). 空间复杂度 语料本身需要2m 字节。如果P 表项用长为4 字节(32 位)的指针来表示,那么最多能处理含232 即 4G 字符的语料。P 表需空间为4m 字节。L 表项可用1 字节(8bit)来表示,记录的最长左子串长度可达255，能满足1-255元字串统计的需要。这对于通常的汉语研究已足够了。L 表需空间为m 字节。字节这样，语料本身、P 表和L 表共需内存2m+4m+m=7m 。 实现举例(1) 1 射串（P表） c bc cbc bcbc abcbc cabcbc bcabcbc abcabcbc 3 L表 3 0 2 2 0 1 1 2 排序后P表 abcbc abcabcbc bc bcbc bcabcbc c cbc cabcbc abcabcbc 实现举例(2) cabcbc X[5] = cabcbc countX[5] = 1 X[4] = cabcb countX[4] = 1 X[3] = cabc countX[3] = 1 X[2] = cab countX[2] = 1 X[1] = ca countX[1] = 1 X[0] = c countX[0] = 1 实现举例(3) cabcbc cbc 长度为3 L[7] = 1, L[7] – 1 = 0 X[5] = cabcbc 5 0, 5 = 3, 输出, 清空 X[4] = cabcb 4 0, 4 = 3, 输出, 清空 X[3] = cabc 3 0, 3 = 3, 输出, 清空 X[2] = cab 2 0, 2 3, 输出, 清空 X[2] = cbc countX[2] = 1; X[1] = ca 1 0, 1 3,输出, 清空 X[1] = cb countX[1] = 1 X[0] = c 0 = 0, countX[0] = 2 实现举例(4) cbc c 长度为1 L[6] = 1, L[6] – 1 = 0 X[2] = cbc 2 0, 2 = 1, 输出, 清空 X[1] = cb 1 0, 1 = 1, 输出, 清空 X[0] = c 0 = 0, countX[0] = 3 实现举例(5) c bcabcab 长度为7 L[5] =