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

Rapid algorithm for left(right) entropy of character strings based on external sort

左右熵在自然语言处理领域有着广泛应用,但目前尚无有效方法实施大规模语料中海量模式的左右熵快速计算。提出了一种计算方法,对于某长度字串计算熵,首先按长度提取语料中的全部字串,使用外部排序和归并获取字串的出现频率,然后分别剔除首尾字符构造待计算字串的频率提供文件,最后使用文件记录频率对比来计算右熵和左熵。分析和实验表明,该方法的计算量同语料规模成线性关系,适于大规模语料中海量字串的左右熵计算。

Left（right） entropy has wide applications in natural language processing,but there is no effective algorithm to implement 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-provision 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.