初涉自然语言处理(四):统计 Bigram

这篇文章之所以拖了这么久是因为我没法解决内存问题,因为随着统计的进行内存占用肯定会越来越高,我在本地测试 300 个文件内存占用已经达到了 500M,而我服务器只有 1G 的空余内存。好在我发现了个逆天的方法能够大幅加快文本处理速度(> 5,000,000 words/s)。

放张内存受虐图:

首先要计算 bigram,肯定得设计一种数据结构来存储它。这里介绍一个叫 Trie 树的结构,其原理就是利用相同字符串的公共部分来节省空间。严格来 Trie 树的一个节点应该只存一个字母,但对于此任务直接存字符串显然是更好的选择。看了网上的实现还是用的 class,而有了上次的教训我还是选择用 KeyValuePair 来实现,这个没什么说的,代码放最后了

这部分的难点主要是逻辑比较复杂,比如遇到了不在字典里的词,指针跳几个,遇到了需要 Fuzzy 的词怎么处理,连续遇到两个又怎么处理,上一个词是大小写敏感还是不敏感……错综缠绕地很不直观,但是细心一点理顺了也没什么难的。我得承认这段我写得太渣。。。

这是计数的逻辑:

class:BigramCounter
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
public void CountWords(string[] words)
{
last = 0;
current = 1;
length = words.Length;
count = 0;
for (; current < length; current++)
{
// Jumped due to unknown word
if (last == current)
{
if (!dic.Exist(words[current], true) && !dic.Exist(words[current].ToLower(), false))
last++;
continue;
}
// New sentence, reset the pionter
else if (words[current].Equals("<s>"))
{
last = current;
continue;
}
// counter
if (!words[current].Equals("<s>") && !words[current].Equals("</s>")) { count++; }
if(!AddWords(words[last], words[current]))
{
last += 2;
continue;
}
last = current;
}
tt.TotalCount += count;
}

这是上面调用的 AddWords() 方法,之所以把这一步单独抽象出来是为了在 fuzzy 时能够复用自身代码。

class:BigramCounter
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
bool lastIsSenstive = false;
bool lastIsFuzzy = false;
string[] fuzzy1 = null;
string[] fuzzy2 = null;
private bool AddWords(string first, string second)
{
if (dic.Exist(second.ToLower(), false))
{
if (lastIsSenstive)
{
tt.Increase(lastIsFuzzy ? fuzzy1[1]: first, second.ToLower());
lastIsSenstive = false;
}
else
tt.Increase(lastIsFuzzy ? fuzzy1[1].ToLower() : first.ToLower(), second.ToLower());
lastIsFuzzy = false;
}
else if (dic.Exist(second, true))
{
if (lastIsSenstive)
tt.Increase(lastIsFuzzy ? fuzzy1[1] : first, second);
else
tt.Increase(lastIsFuzzy ? fuzzy1[1].ToLower() : first.ToLower(), second);
lastIsSenstive = true;
lastIsFuzzy = false;
}
else if (null != (fuzzy2 = dic.Fuzzy(second)))
{
AddWords(lastIsFuzzy ? fuzzy1[1] : first, fuzzy2[0]);
AddWords(fuzzy2[0], fuzzy2[1]);
count++;
lastIsFuzzy = true;
fuzzy1 = fuzzy2;
}
else
return false;
return true;
}

最后说一下提速的方法:之前我是把打印 log 的语句写在工作线程里的,这次我为 logger 单独开了一个线程,结果直接提速上百倍。速度简直飞快,一亿多字不到 5 分钟就处理完了。。。

看来在控制台打印语句是很费时的啊。。。

最后生成的文件有 300M,这可愁死我了,怎么进行检索呢。。。

TrieTree 类:

class:TrieTree
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
// ctor() was omitted
public class TrieTree
{
// singleton
static TrieTree _instance = null;
public static TrieTree GetInstance()
{
if (_instance == null)
_instance = new TrieTree();
return _instance;
}
private Dictionary<string, Dictionary<string, int>> counter;
private double totalCount = 0;
private double coverage = 0;
public void Increase(string first, string second)
{
if (!counter.Keys.Contains(first))
counter.Add(first, new Dictionary<string, int>());
if (!counter[first].Keys.Contains(second))
counter[first].Add(second, 1);
else
counter[first][second]++;
}
public void Increase(string first, string second, int frequency)
{
if (!counter.Keys.Contains(first))
counter.Add(first, new Dictionary<string, int>());
counter[first].Add(second, frequency);
}
}