Google 面试题 - 怎样实现拼写纠错的功能？

在我们日常工作生活中，经常会面临单词拼写错误的时候，那么如何能够最快的实现纠正拼写错误呢？比如你写"华盛顿"这个词，写成了 Wasingdon，查一下字典很容易判断是否有这个单词，但是，要找到正确的拼写 Washington，就颇费周章了。我们先把这个问题放一下，带着这个问题来学习今天所要学习的内容，二分查找。

二分查找是一种非常简单易懂的快速查找算法，生活中到处可见。比如说，我们现在来做一个猜字游戏。我随机写一个 0 到 99 之间的数字，然后你来猜我写的是什么。猜的过程中，你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。这就是一个典型的二分查找问题。

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二分查找的时间复杂度，假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。

可以看出来，这是一个等比数列。其中 n/2k=1 时，k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较，所以，经过了 k 次区间缩小操作，时间复杂度就是 O(k)。通过 n/2k=1，我们可以求得 k=log2n，所以时间复杂度就是 O(logn)。这就是对数时间复杂度。这是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1)的算法还要高效。为什么这么说呢？比如 n 等于 2 的 32 次方，这个数很大了吧？大约是 42 亿。也就是说，如果我们在 42 亿个数据中用二分查找一个数据，最多需要比较 32 次。

简单的二分查找实现，最简单的情况就是有序数组中不存在重复元素。

二分查找的循环实现，

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
 
  while (low <= high) {
    int mid = (low + high) / 2;
    if (a[mid] == value) {
      return mid;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
 
  return -1;
}

二分查找的递归实现，

public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}
 
private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low > high) return -1;
 
  int mid =  low + ((high - low) >> 1);
  if (a[mid] == value) {
    return mid;
  } else if (a[mid] < value) {
    return bsearchInternally(a, mid+1, high, value);
  } else {
    return bsearchInternally(a, low, mid-1, value);
  }
}

二分查找的局限性：

首先，二分查找依赖的是顺序的表结构，二分查找算法需要按照下标随机访问元素。数组按照下标随机访问数据的时间复杂度是 O(1)，而链表随机访问的时间复杂度是 O(n)。所以，如果数据使用链表存储，二分查找的时间复杂就会变得很高。

其次，二分查找针对的是有序数据，二分查找要求数据必须是有序的。如果数据没有序，我们需要先排序。排序的时间复杂度最低是 O(nlogn)。所以，如果我们针对的是一组静态的数据，没有频繁地插入、删除，我们可以进行一次排序，多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低。二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用。

再次，数据量太小不适合二分查找。如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。只有数据量比较大的时候，二分查找的优势才会比较明显。不过，如果数据之间的比较操作非常耗时，不管数据量大小，都推荐使用二分查找。比如，数组中存储超过 300 个字符的字符串之间比对大小，就会非常耗时。则需要尽可能地减少比较次数，而比较次数的减少会大大提高性能，这个时候二分查找就比顺序遍历更有优势。

最后，数据量太大也不适合二分查找。二分查找的底层需要依赖数组，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。太大的数据用数组存储会比较吃力了，所以也不能用二分查找了。

回到开头说的 google 面试题，如何能够最快的实现纠正拼写错误呢？最直截了当的回答是把字典中所有英文单词在计算机中建立一个词典，大家无论是使用 word 写文档，还是在 Google 提供的搜索中，在相应的软件里实现一个直接查字典的功能就好了。字典该怎么设计？其中一种设计方法是采用排好序的线性数组，这样采用二分查找，就可以判断一个字符串的拼写是否是正确的（在构词学上称为"合法"）。如果英语的单词有 25 万个，那么做 18 次单词的比对即可（2 的 18 次方大约等于 25 万）。如果再考虑到单词的平均长度是 6 个字母，每次比对要进行六次，这样一共就是 108 次比对。

当然，我们还可以利用哈希表来存储词典，大约只要进行两单词查找，就可以判断一个单词的拼写是否法。这样只要比对字母 12 次左右。

接下来再谈谈如何纠错，这并非是个很容易的问题，我们需要从理论和工程两个角度来回答。先从理论上回答。

当我们知道一个单词写错了，我们如何判断它所对应的正确拼写可能是哪一种呢？一般来讲我们要看错误的拼写和哪个正确的拼写"相近"。但是，这个相近其实并不好度量。比如"华盛顿"的错误拼写 Wasingdon 和正确的拼写 Washington 是否相近呢？我们感觉它们确实相近，但是这个错误拼写其实和另一个英国人的名字 Watingdon 似乎更相近。

因此，有必要量化地度量一下这些单词之间的相近程度，或者反过来说，差异程度。要做这件事，就要定义一种差异程度的度量，在构词学中，它被称为"编辑距离"。接下来我们就说说什么是编辑距离（Editing Distance），它是如何计算的。

对比一下 Wasingdon 和 Washington。我们刻板地把相同位置的字母一个一个地比较，那么它就错了六个或者七个字母，因为从 Was 之后所有的字母都错位了。下图一致的字母用蓝色表示，后面错掉的用红色表示。

但是，我们一般会认为 Wasingdon 只错了两个字母，即少了一个 h，把 t 写成了 d。如果我把缺少掉的字母 h 用空格"－"表示，让它和 h 对应，那么后面的字母大多能够对应起来。大家可以扫一眼下面的表格，我们依然用蓝色表示正确的匹配，红色表示错误的匹配。从这个表中你可以看出，标红色的错误只有两处。

接下来的问题是，上述两个拼写的编辑距离到底应该如何定义？

很清楚，应该用最小的差异来定义。也就是说，编辑距离是 2，而不是 6。那么接下来怎么计算编辑距离呢？这就要用到和我们前天说的维特比算法相类似的一种动态规划算法了。这个算法的细节我们省略了，它的思想和维特比算法一样，把一个指数复杂度的问题，变成一个平方复杂度的问题。具体到"华盛顿"这个单词上，大约可以把 18 万次计算，缩减到 100 次计算。

下面一个表格是采用动态规划的方法，计算出的"华盛顿"正确拼法和错误拼法不同的对应方式字母之间的差异。表中横线上的是错误拼法，竖线上的是正确拼法。红色的是差异最小的对应方法，即用一个空格"－"对应丢失的 h，用 d 对应 t。

对于所有的英语单词，我们都可以两两找出它们的编辑距离。比如 a 和 an 差 1，but 和 cut 差 1，tell 和 tail 差 2，等等。因此，进行拼写纠错的第一步，就是对于那些在词典里没有的单词，找到和它们编辑距离比较小，比如相差只有一到两个字母的单词作为候选。对于上面例子中 Wasingdon 这个写法，"华盛顿"的正确写法 Washington 和英国人的名字 Watingdon 都可以作为候选。

接下来到底挑选哪个单词来修正就有讲究了。虽然前者相差两个字母，后者只相差一个字母，看似后者更接近，但是，如果考虑到"华盛顿"这个词本身出现的概率要比 Watingdon 高得多，通常似乎改正成为"Watingdo"更合理。

不过，凡事也有例外，如果上下文是讨论 1066 年威廉征服这件事，还真有一个叫做 Watingdon 的家族跟随威廉一世来到英国。因此，正确使用上下文很重要。事实上，稍微好一点的拼写矫正都需要考虑上下文。而利用上下文做选择，其实采用的还真是维特比算法。

总结，二分查找的核心思想理解起来非常简单，有点类似分治思想。即每次都通过跟区间中的中间元素对比，将待查找的区间缩小为一半，直到找到要查找的元素，或者区间被缩小为 0。但是二分查找的代码实现比较容易写错。你需要着重掌握它的三个容易出错的地方：循环退出条件、mid 的取值，low 和 high 的更新。二分查找虽然性能比较优秀，但应用场景也比较有限。底层必须依赖数组，并且还要求数据是有序的。对于较小规模的数据查找，我们直接使用顺序遍历就可以了，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

参考《谷歌方法论》、《数据结构与算法之美》