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

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (19): 18-20.

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

张海军1，2，彭成1，栾静1

1.新疆师范大学计算机科学技术学院，乌鲁木齐 830054
2.中国科技大学计算机科学技术学院，合肥 230027

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-01 发布日期:2011-07-01

Rapid algorithm for left（right） entropy of character strings based on external sort

ZHANG Haijun1，2，PENG Cheng1，LUAN Jing1

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

Received:1900-01-01 Revised:1900-01-01 Online:2011-07-01 Published:2011-07-01

摘要/Abstract

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

关键词: 自然语言处理, 左右熵, 统计特征, 新词检测

Abstract: 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.

Key words: natrual language processing, left（right） entropy, statistical feature, new words detection

张海军1，2，彭成1，栾静1. 基于外部排序的字串左右熵快速计算方法[J]. 计算机工程与应用, 2011, 47(19): 18-20.

ZHANG Haijun1，2，PENG Cheng1，LUAN Jing1. Rapid algorithm for left（right） entropy of character strings based on external sort[J]. Computer Engineering and Applications, 2011, 47(19): 18-20.

[1]	刘博闻，范春晓. 基于位置感知能力胶囊网络的实体关系提取[J]. 计算机工程与应用, 2021, 57(6): 101-107.
[2]	廖文雄，曾碧，徐雅芸. 结合一维扩展卷积与Attention机制的NLP模型[J]. 计算机工程与应用, 2021, 57(4): 114-119.
[3]	江洋洋，金伯，张宝昌. 深度学习在自然语言处理领域的研究进展[J]. 计算机工程与应用, 2021, 57(22): 1-14.
[4]	袁勋，刘蓉，刘明. 融合多层注意力的方面级情感分析模型[J]. 计算机工程与应用, 2021, 57(22): 147-152.
[5]	杨泉. N1+N2结构语法关系判定的SVM算法[J]. 计算机工程与应用, 2021, 57(20): 104-108.
[6]	焦凯楠，李欣，朱容辰. 中文领域命名实体识别综述[J]. 计算机工程与应用, 2021, 57(16): 1-15.
[7]	刘畅，阿布都克力木·阿布力孜，姚登峰，哈里旦木·阿布都克里木. 维吾尔语形态分析研究综述[J]. 计算机工程与应用, 2021, 57(15): 42-61.
[8]	李智，王震，杨赋庚，奚雪峰. 基于表格的自动问答研究与展望[J]. 计算机工程与应用, 2021, 57(13): 67-76.
[9]	包玥，李艳玲，林民. 抽取式机器阅读理解研究综述[J]. 计算机工程与应用, 2021, 57(12): 25-36.
[10]	何玉洁，杜方，史英杰，宋丽娟. 基于深度学习的命名实体识别研究综述[J]. 计算机工程与应用, 2021, 57(11): 21-36.
[11]	孙凌浩. 利用翻译模型的跨语言中文命名实体识别[J]. 计算机工程与应用, 2021, 57(10): 94-100.
[12]	郝超，裘杭萍，孙毅，张超然. 多标签文本分类研究进展[J]. 计算机工程与应用, 2021, 57(10): 48-56.
[13]	余同瑞，金冉，韩晓臻，李家辉，郁婷. 自然语言处理预训练模型的研究综述[J]. 计算机工程与应用, 2020, 56(23): 12-22.
[14]	吴呈，王朝坤，王沐贤. 基于文本化简的实体属性抽取方法[J]. 计算机工程与应用, 2020, 56(21): 115-122.
[15]	涂文博，袁贞明，俞凯. 无池化层卷积神经网络的中文分词方法[J]. 计算机工程与应用, 2020, 56(2): 120-126.