新词发现，从文本中找出未登录词。本文主要参考互联网时代的社会语言学：基于SNS的文本数据挖掘 实现，实现的技术主要包括互信息、左右信息熵、n-gram。 另外为了方便提取新词，设计了一个评分函数，评分越高成词可能性越高。
左右信息熵
左右信息熵用来衡量该词语所处语境的丰富程度，信息熵是用来衡量随机变量不确定度的一种度量，不确定程度越高，信息熵越高，越难以预测。 对于一个随机变量X，它的熵可以表示成以下形式：
其中 $p(x)$ 代表随机变量 $x$ 出现的概率，在新词发现中，可以通过计算一个候选词左边和右边的信息熵来反映一个词是否有丰富的左右搭配，如果达到一定阈值则我们认为两个片段可以成为一个新词。例如（该例子来源于互联网时代的社会语言学：基于SNS的文本数据挖掘）
> 考虑这么一句话 “吃葡萄不吐葡萄皮不吃葡萄倒吐葡萄皮”，“葡萄”一词出现了四次，其中左邻字分别为 {吃, 吐, 吃, 吐} ，右邻字分别为 {不, 皮, 倒, 皮} 。根据公式，“葡萄”一词的左邻字的信息熵为 – (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 。可见，在这个句子中，“葡萄”一词的右邻字更加丰富一些。
因此，如果一个词所处的语境越丰富（不确定程度越高），则表明这个词与周围的字成词概率越低，该词独立性越好。
# 点间互信息
互信息(mutual information)，表示的是两个随机变量X,Y共享的信息量。 或者说，互信息代表着知道了任意一个变量之后对另一个变量不确定性的减少。
计算公式为：
点间互信息或称 内部聚合度、凝固度，相对于互信息，点间互信息仅计算了两个随机变量之间的互信息，两者相关性越大，点间互信息越大。例子参考文章互联网时代的社会语言学：基于SNS的文本数据挖掘中“电影院”的例子
n-gram
n-gram 是将文本分成多个片段比较常用的方法，这里采用的是k-gram，其中 $k=2,…,n,n+1$ ，这里n为指定最大切词长度， $n+1$ 是为了计算词的左右信息熵。以词语“新词发现算法”为例，如果设定最大切词长度为3，则所有的切词片段为：新词、词发、发现、现算、算法、新词发、词发现、发现算、现算法、新词发现、词发现算、发现算法
评分函数
为了能够方便地评估一个词语的成词程度，设计公式：(词最小互信息 - 累计字信息熵 + 词最小左右信息熵) * 词频 对成词进行评分，分数越高成词效果越好。
算法流程
具体算法实现流程如下：
- 输入：一个长文本字符串string
- 输出：新词 及 成词score
- 设定成词最大长度n；最小凝固度，最小自由度
- 将空格、逗号、分号等符号统一转换成换行符；
- 分别对每个句子、反转句子进行 $1,2,..,n,n+1-gram$ 分词；
- 将分好的词插入tire树中。并统计每个词的词频；
- 计算每个词的互信息，过滤掉不满足最小凝固度的词语；
- 计算每个词、反转词的左右信息熵，过滤掉不满足最小信息熵的词语；
- 计算每个字的左右信息熵，取最小值；
- 累计每个词的字信息熵；
- 计算词的成词score:(词最小互信息 - 累计字信息熵 + 词最小左右信息熵) * 词频
效果
下面是针对一些文本的抽取结果：
西游记：
通信行业会话数据：
红楼梦：
宝玉, 什么, 凤姐, 黛玉, 姑娘, 贾母, 宝钗, 怎么, 太太, 笑道, 告诉, 丫头, 贾政, 自己, 东西, 鸳鸯, 奶奶, 紫鹃, 贾琏, 咱们, 晴雯, 袭人, 媳妇, 如今, 知道, 老爷, 探春, 李纨, 姨妈, 尤氏, 我们, 老太太, 湘云, 姐姐, 薛姨妈, 丫鬟, 刘姥姥, 薛蟠, 这样, 吩咐, 薛姨, 姊妹, 姥姥, 答应, 你们, 妹妹, 夫人, 香菱, 两个, 那里, 贾珍, 听见, 平儿, 周瑞, 屋里, 麝月, 二爷, 糊涂, 预备, 雨村, 林黛玉, 雪雁, 一个, 他们, 兄弟, 惜春, 所以, 贾赦, 伏侍, 只管, 不敢, 小厮, 贾蓉, 姨娘, 如此, 收拾, 那边, 哥哥, 嬷嬷, 悄悄, 喜欢
