初涉自然语言处理(二):统计词频

昨天那篇文章是根据需求一步步向上反推的,真正开始时应该是从第五步开始一步步到第一步。由于我已经在网上找到了勉强足够的语料(143,347,023 words,in 1,508 files),所以就直接从统计词频开始讲了。

先来说说为什么要统计词频。

语言模型的本质就是根据已经出现的单词来预测下一个可能出现的单词。

例如: I want to eat Chinese food

这一句,在用户已经输入 I want to eat Chinese 时,下一个单词是 food 的概率其实就是求条件概率(conditional probability)

$P(food|I,want,to,eat,Chinese)$

根据贝叶斯公式,有

$P(food | I, want, to, eat, Chinese) = \frac{P(I, want, to, eat, Chinese, food)}{P(I, want, to, eat, Chinese)}$

所以理论上我们只要统计出足够多的单词组合的频率,就能推出他们出现的概率,也就能计算出任意单词在一个给定词语或短语后出现的概率。即:

$P(food | I, want, to, eat, Chinese) = \frac{Count(I, want, to, eat, Chinese, food)}{Count(I, want, to, eat, Chinese)}$

但是显然,我们很难去统计出 I want to eat Chinese food 的频率,因为可能的单词组合太多了。所以我们退而求其次,根据 Andrei Markov 提出的以下假设:

$P(food \:|\: I, want, to, eat, Chinese)\approx P(food | Chinese)$

$Or$

$P(food \:|\: I, want, to, eat, Chinese)\approx P(food | eat, Chinese)$

这样我们只需要统计出任意两个或三个单词的组合频率就可以了。

事实上,统计两个单词组合出现频率的模型叫 Bigram,三个的叫 Trigram, Google 拥有 5-gram 的数据。很显然,模型的维数越高,计算所得出来的结果就越精确,所需要的数据也就越多。

而只统计单个词频的模型叫 Unigram,这种模型只是简单地将一个句子中的每个单词相乘,即将每个单词的出现看做相对独立事件,这显然是非常不精确的。

在本项目中,我选择 Bigram 模型,即需要统计任意单词出现的频率和任意两个单词同时出现的频率。


说完了理论部分,我们来看看具体怎么操作。

首先统计单个单词出现的频率。我选用 C# 来处理文本,没别的原因,就是因为封装比较好,容易使用。

第一步先要获得一个词典,思路是先不管用什么方法弄个差不多的,然后在统计的时候如果遇到词典中没有的再视情况补进去。此外,因为英语中的人名、地名、专有名词、缩写等都是需要大写的,所以需要准备两个字典,一个大小写敏感,另一个不敏感。

我从 Search for all words.txt拿到了一个将近 11 万词的字典,看了看基本上挺全的,起码名词的复数都有,自己补充了一些不常见的之后就可以作为大小写不敏感的词库使用了。

至于大小写敏感的词库,我也是从网上找了许多人名、地名的集合,去重后做成了一个 3000 词左右的词典。

但是这里有个问题,有的单词(比如 turkey)是既大小写不敏感(火鸡)又大小写敏感(土耳其)的。我看了一下两个词典重叠的有一千多个单词,暂时没比较好的办法,把这些词全从敏感字典里剔除了,即默认他们全都大小写不敏感。

第二步需要把收集到的文本进行格式化,用正则去掉所有不需要的部分。由于此阶段只需统计词频而无需分句,所以正则可以大胆地写。(代码比较长我放在文章末尾了,点此查看

第三步需要设计一个数据结构把这些词载入到内存。与此同时这些词应该被记录的属性是:出现频次、出现频率。由于写 JavaScript 写习惯了,脑子一热就弄了个类出来,这是我踩的第一个坑:

class:WordFrequency
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// ctor and getter or setter were omitted
public class WordFrequency : IComparable<WordFrequency>
{
private string word;
private int time;
private double frequency;
public int CompareTo(WordFrequency wf)
{
return wf.Time.CompareTo(this.Time) == 0 ? this.Word.CompareTo(wf.Word) : wf.Time.CompareTo(this.Time);
}
override public string ToString()
{
return Word + "," + Time + "," + Frequency;
}
}

time 是出现次数,frequency 是出现频率。重写了 ToString() 并实现了 IComparable 的接口。建立一个List<WordFrequency>存进去,这样就可以在后面直接用 list.sort() 来排序了,这样排出来是先按照频次再按照字母顺序。

后来统计的时候,速度是这样的:

大约每秒 500 ~ 600 词。后来算了算觉得这样实在太慢,虽然没有 profile 不过我猜大部分时间都花在从 list 里取出相应的对象了:

class:Dictionary
1
2
3
4
5
6
7
8
9
10
private List<WordFrequency> senstive = new List<WordFrequency>();
private List<WordFrequency> insenstive = new List<WordFrequency>();
public void Increase(string word, bool senstive)
{
if (senstive)
this.senstive.Find((WordFrequency wf) => wf.Word.Equals(word)).Time++;
else
this.insenstive.Find((WordFrequency wf) => wf.Word.Equals(word.ToLower())).Time++;
}

这里的 Find() 操作是依靠 lambda 匿名函数来取,每次都要遍历一遍整个字典,所以非常慢。

后来想到其实没必要把 frequency 存起来,每次跑完数据再统一计算一次就可以了。所以这样就可以用 KeyValuePair<string, int>来表示了,而这个东西是可以存进 C# 提供的 Dictionary 类的,其内部是原理是 HashTable ,所以会快很多,并且可以用方括号语法直接访问:

class:Dictionary
1
2
3
4
5
6
7
8
9
10
private Dictionary<string, int> senstive = new Dictionary<string, int>();
private Dictionary<string, int> insenstive = new Dictionary<string, int>();
public void Increase(string word, bool senstive)
{
if (senstive)
this.senstive[word]++;
else
this.insenstive[word.ToLower()]++;
}

这样修改之后效率增加了 6 倍(后来才知道其实如果把控制台的 log 信息去掉远远不止这个速度),一亿字的数据一晚上就跑完了。

现在文本就可以用 Array.Split() 打断成数组,然后只需要遍历这个数组就可以完成词频的统计了。

class:FrequencyCalculator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (dic.Exist(word, false))
dic.Increase(word, false);
else if (dic.Exist(word, true))
dic.Increase(word, true);
else if (null != (fuzzy = dic.Fuzzy(word)))
foreach (string w in fuzzy)
{
if (dic.Exist(w, false))
dic.Increase(w, false);
else if (dic.Exist(w, true))
dic.Increase(w, true);
}
else
dic.Unexist(word);

需要提一下的是,我还多声明了一个 Dictionary 用来存储不在字典里的文本。这样在跑完数据之后很容易就能发现不在字典里的词。

先对比大小写不敏感的字典;如果不在这个字典里,则对比大小写敏感的字典;如果还不在,对其进行模糊比较;如果还没有,则放进不在字典里的字典里。

这里的模糊比较是这样的,因为网上下载的文本经常会有两个单词黏一起的情况,如: shesaid,为了对付这样的单词才加了这一步:

class:Dictionary
1
2
3
4
5
6
7
8
9
10
11
12
13
// Split words like 'doyou'
public string[] Fuzzy(string word)
{
string[] ret = new string[2];
for (int i = 1; i < word.Length; i++)
{
ret[0] = word.Substring(0, i);
ret[1] = word.Substring(i);
if ((this.Exist(ret[0], true) || this.Exist(ret[0], false)) && (this.Exist(ret[1], true) || this.Exist(ret[1], false)))
return ret;
}
return null;
}

放一部分结果上来:

词频就说到这,下篇讲统计两个单词相结合的频率。


以下是清洗文本所用的正则表达式:

class:FileCleaner
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
private string _clean(string raw)
{
string c = raw;
// convert whitespace
c = Regex.Replace(c, @"\xA0|\s+|(&nbsp;)|\-", " ", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// strip any punctuation
c = Regex.Replace(c, @"[^a-zA-Z\s\u0027\u2019]+", " ", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// convert '
c = Regex.Replace(c, @"\u2019", "\u0027", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// remove numbers
c = Regex.Replace(c, @"\d+(,\d+)*(\.\d+)?", " ", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// stemming am
c = Regex.Replace(c, @"I'm", "I am", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// stemming are
c = Regex.Replace(c, @"([a-zA-Z]+)('re)", "$1 are", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// stemming will
c = Regex.Replace(c, @"([a-zA-Z]+)('ll)", "$1 will", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// stemming have
c = Regex.Replace(c, @"([a-zA-Z]+)('ve)", "$1 have", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// remove abbreviation
c = Regex.Replace(c, @"([a-zA-Z]+)(('s)|(s')|('d))", "$1", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// remove leading '
c = Regex.Replace(c, @"(\s|^)(\u0027+)([a-zA-Z])", " $3", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// remove tailing '
c = Regex.Replace(c, @"([a-zA-Z])(\u0027+)(\s|$)", "$1 ", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// remove extra whitespace
c = Regex.Replace(c, @"\s{2,}", " ", RegexOptions.Compiled | RegexOptions.IgnoreCase | RegexOptions.Multiline);
// trim string
return c.Trim();
}