基于外部排序的字串左右熵快速计算方法.pdf

18 2011 ，47 （19） Computer Engineering and Applications 计算机工程与应用 基于外部排序的字串左右熵快速计算方法 1，2 1 1 张海军 ，彭 成 ，栾 静 1，2 1 1 ZHANG Haijun ，PENG Cheng ，LUAN Jing 1.新疆师范大学 计算机科学技术学院，乌鲁木齐 830054 2.中国科技大学 计算机科学技术学院，合肥 230027 1.School of Computer Science and Technology ，Xinjiang Normal University ，Urumqi 830054 ，China 2.School of Computer Science and Technology ，University of Science and Technology of China ，Hefei 230027 ，China ZHANG Haijun ，PENG Cheng ，LUAN Jing.Rapid algorithm for left （right）entropy of character strings based on exter- nal sort.Computer Engineering and Applications ，2011 ，47 （19）：18-20. Abstract ：Left （right ）entropy has wide applications in natural language processing ，but there is no effective algorithm to im- plement rapid calculation of them for lots of strings in large-scalce corpus.This paper puts forward a rapid method for left （right ）entropy.For calculating entropy of distinct length of strings ，extracting all strings with fixed length in corpus is the first step ，and these extracted strings are sorted and merged by external sort method.Then the files of string frequency-provi- sion are constructed by removing the suffix or prefix of each string respectively.At last ，the left （right ）entropy is calculated by employing frequency comparison of strings in files.According to analyses and experiments ，the computational burden of this method has a linear relationship with the size of corpus and it is suitable for the calculations of huge amount of strings in large-scale corpus. Key words ：natrual language processing ；left（right ）entropy ；statistical feature ；new words detection 摘 要：左右熵在自然语言处理领域有着广泛应用，但目前尚无有效方法实施大规模语料中海量模式的左右熵快速计算。提出 了一种计算方法，对于某长度字串计算熵，首先按长度提取语料中的全部字串，使用外部排序和归并获取字串的出现频率，然后 分别剔除首尾字符构造待计算字串的频率提供文件，最后使用文件记录频率对比来计算右熵和左熵。分析和实验表明，该方法 的计算量同语料规模成线性关系，适于大规模语料中海量字串的左右熵计算。 关键词：自然语言处理；左右熵；统计特征；新词检测 DOI ：10.3778/j.issn. 1002-8