贝叶斯公式与拼写检查器

winston

今天复习了下概率论中贝叶斯的基础知识，动手写了个Java版本的简单的拼写检查器。
我们在使用Google时，当我们输入一个错误的单词，经常可以看到Google提示我们是不是要查找什么什么。
它是怎样做到的呢？现在我们就来实现一个简单的拼写检查器。




1. 什么是贝叶斯公式？


来看来自维基百科的定义：


贝叶斯定理

贝叶斯定理由英国数学家贝叶斯 ( Thomas Bayes 1702-1761 ) 发展，用来描述两个条件概率之间的关系，比如 P(A|B) 和 P(B|A)。按照定理 6 的乘法法则，P(A∩B)=P(A)·P(B|A)=P(B)·P(A|B)，可以立刻导出贝叶斯定理：

如上公式也可变形为

另一个例子，现分别有 A，B 两个容器，在容器 A 里分别有 7 个红球和 3 个白球，在容器 B 里有 1 个红球和 9 个白球，现已知从这两个容器里任意抽出了一个球，且是红球，问这个红球是来自容器 A 的概率是多少?

假设已经抽出红球为事件 B，从容器 A 里抽出球为事件 A，则有：P(B) = 8 / 20，P(A) = 1 / 2，P(B | A) = 7 / 10，按照公式，则有：

在上面的例子中，
事件A：要猜测事件的概率（从容器A里抽出球 - 要猜测和计算的事件）
事件B：现实已发生事件的概率（抽出红球 - 已经抽出红球，已经发生的事件）

正因贝叶斯公式可用于事件发生概率的推测，因此它广泛应用于计算机领域。从垃圾邮件的过滤，中文分词，机器翻译等等。下面的拼写检查器可以说是牛刀小试了。


2. 拼写检查器

第一步，以一个比较大的文本文件big.txt作为样本，分析每个单词出现的概率作为语言模型(Language Model)和词典。
big.txt的地址是：http://norvig.com/big.txt

第二步，如果用户输入的单词不在词典中，则产生编辑距离(Edit Distance)为2的所有可能单词。所谓编辑距离为1就是对用户输入的单词进行删除1个字符、添加1个字符、交换相邻字符、替换1个字符产生的所有单词。而编辑距离为2就是对这些单词再进行一次上述所有变换，因此最后产生的单词集会很大。可以与词典作差集，只保留词典中存在的单词。

第三步，假设事件c是我们猜测用户可能想要输入的单词，而事件w是用户实际输入的错误单词，根据贝叶斯公式可知：
     P(c|w) = P(w|c) * P(c) / P(w)。
这里的P(w)对于每个单词都是一样的，可以忽略。而P(w|c)是误差模型(Error Model)，是用户想要输入w却输入c的概率，这是需要大量样本数据和事实依据来得到的，为了简单起见也忽略掉。因此，我们可以找出编辑距离为2的单词集中P(c)概率最大的几个来提示用户。


3. Java代码实现

4. package com.cdai.studio.spellcheck;
7. import java.io.BufferedReader;
8. import java.io.FileReader;
9. import java.io.IOException;
10. import java.io.InputStreamReader;
11. import java.util.Collections;
12. import java.util.Comparator;
13. import java.util.HashMap;
14. import java.util.HashSet;
15. import java.util.LinkedList;
16. import java.util.List;
17. import java.util.Map;
18. import java.util.Map.Entry;
19. import java.util.Set;
20. import java.util.regex.Pattern;
23. public class SpellCheck {
26.        private static final char[] ALPHABET = "abcdefghijklmnopqrstuvwxyz".toCharArray();
27.       
28.        public static void main(String[] args) throws Exception {
29.               new SpellCheck().start();
30.        }
31.       
32.        public void start() throws IOException {
33.               // 1.Build language model
34.               Map<String, Double> langModel =
35. buildLanguageModel("big.txt");
36.               Set<String> dictionary =
37. langModel.keySet();
38.               
39.               // 2.Read user input loop
40.               BufferedReader reader
41. = new BufferedReader(new InputStreamReader(System.in));
42.               String input;
43.               while ((input = reader.readLine()) != null)
44. {
45.                      input =
46. input.trim().toLowerCase();
47.                      if ("bye".equals(input))
48.                            break;
49.                      if (dictionary.contains(input))
50.                            continue;
51.                      long startTime = System.currentTimeMillis();
52.                      
53.                      // 3.Build set for word in edit distance and remove
54. inexistent in dictionary
55.                      Set<String>
56. wordsInEditDistance2 = buildEditDistance2Set(langModel,
57. input);
58.                      wordsInEditDistance2.retainAll(dictionary);
59.                      
60.                      // 4.Calculate Bayes's probability
61.                      // c - correct word we guess, w - wrong word user input
62. in reality
63.                      // argmax P(c|w) = argmax P(w|c) * P(c) / P(w)
64.                      // we ignore P(w) here, because it's the same for all
65. words
66.                      List<String> guessWords =
67. guessCorrectWord(langModel, wordsInEditDistance2);
68.                      System.out.printf("Do you mean %s ? Cost time: %.3f
69. second(s)\n",
70.                                   guessWords.toString(),
71. (System.currentTimeMillis() - startTime) / 1000D);
72.               }
73.               
74.        }
75.       
76.        private Map<String, Double> buildLanguageModel(String
77. sample)
78.                      throws IOException {
79.               Map<String, Double> langModel
80. = new HashMap<String, Double>();
81.               BufferedReader reader
82. = new BufferedReader(new FileReader(sample));
83.               Pattern pattern = Pattern.compile("[a-zA-Z]+");
84.               String line;
85.               int totalCnt = 0;
86.               while ((line = reader.readLine()) != null)
87. {
88.                      String[] words =
89. line.split(" ");
90.                      for (String word : words) {
91.                            if (pattern.matcher(word).matches()) {
92.                                   word =
93. word.toLowerCase();
94.                                   Double wordCnt =
95. langModel.get(word);
96.                                   if (wordCnt == null)
97.                                          langModel.put(word,
98. 1D);
99.                                   else
100.                                          langModel.put(word,
101. wordCnt + 1D);
102.                                   totalCnt++;
103.                            }
104.                      }
105.               }
106.               reader.close();
107.               
108.               for (Entry<String, Double> entry :
109. langModel.entrySet())
110.                      entry.setValue(entry.getValue() /
111. totalCnt);
112.               
113.               return langModel;
114.        }
115.       
116.        private Set<String>
117. buildEditDistance1Set(
118.                      Map<String, Double>
119. langModel,
120.                      String input) {
121.               Set<String> wordsInEditDistance
122. = new HashSet<String>();
123.               char[]
124. characters = input.toCharArray();
125.               
126.               // Deletion: delete letter[i]
127.               for (int i =
128. 0; i < input.length(); i++)
129.                      wordsInEditDistance.add(input.substring(0,i)
130. + input.substring(i+1));
131.               
132.               // Transposition: swap letter[i] and
133. letter[i+1]
134.               for (int i =
135. 0; i < input.length()-1; i++)
136.                      wordsInEditDistance.add(input.substring(0,i)
137. + characters[i+1] +
138.                                   characters[i] +
139. input.substring(i+2));
140.               
141.               // Alteration: change letter[i] to
142. a-z
143.               for (int i =
144. 0; i < input.length(); i++)
145.                      for (char c
146. : ALPHABET)
147.                            wordsInEditDistance.add(input.substring(0,i)
148. + c + input.substring(i+1));
149.               
150.               // Insertion: insert new letter a-z
151.               for (int i =
152. 0; i < input.length(); i++)
153.                      for (char c
154. : ALPHABET)
155.                            wordsInEditDistance.add(input.substring(0,i)
156. + c + input.substring(i));
157.               
158.               return wordsInEditDistance;
159.        }
160.       
161.        private Set<String>
162. buildEditDistance2Set(
163.                      Map<String, Double>
164. langModel,
165.                      String input) {
166.               Set<String> wordsInEditDistance1 =
167. buildEditDistance1Set(langModel, input);
168.               Set<String> wordsInEditDistance2
169. = new HashSet<String>();
170.               for (String editDistance1 :
171. wordsInEditDistance1)
172.                      wordsInEditDistance2.addAll(buildEditDistance1Set(langModel,
173. editDistance1));
174.               wordsInEditDistance2.addAll(wordsInEditDistance1);
175.               return wordsInEditDistance2;
176.        }
177.       
178.        private List<String> guessCorrectWord(
179.                      final Map<String, Double> langModel,
180.                      Set<String>
181. wordsInEditDistance) {
182.               List<String> words = new LinkedList<String>(wordsInEditDistance);
183.               Collections.sort(words, new Comparator<String>() {
184.                      @Override
185.                      public int compare(String word1, String word2)
186. {
187.                            return langModel.get(word2).compareTo(langModel.get(word1));
188.                      }
189.               });
190.               return words.size() > 5 ? words.subList(0, 5) : words;
191.        }
192.       
193. }

复制代码

运行结果：

raechel

Do you mean [reached, reaches, ranches, rachel] ? Cost time: 0.219 second(s)

thew

Do you mean [the, that, he, her, they] ? Cost time: 0.062 second(s)

虽然不是很准确，但是不是很有趣呢？如果感兴趣，我们可以继续深入学习。

有了兴趣和求知欲，并不断实践，才能学好编程。

参考文章

平凡又神奇的贝叶斯 http://mindhacks.cn/2008/09/21/the-magical-bayesian-method/

怎样写一个拼写检查器 http://blog.youxu.info/spell-correct.html

作者：dc_726 发表于2011-12-27 22:34:22 原文链接