算法 拼写检查的四种实现

yfractal · 2018年12月22日 · 最后由 yfractal 回复于 2019年03月07日 · 2643 次阅读
本帖已被设为精华帖!

算法有趣的地方在于,可以用不同的方式处理同一个问题,并且总有更好的方法。比如拼写检查。

拼写检查大体是这样的,给出一个字典文件,给出一个比对文件。比对文件里的单词,如果某个单词不在字典文件里的话,就认为拼写错误。要做的就是找出比对文件里所有拼写错误的单词。

暴力破解(brute force)

最直观的方法,就讲文件里的单词一一同字典里的单词做比较,如果不在字典里,就输出。最简单,也最费时。

假设字典文件一共有nd个字符,用于比对的文件有nt字符,复杂度则为 O(nd * nt)。

具体实现

我们看一下运行速度,测试用的字典里大约有 14 万个单词,用作比对的文件大约有12 万个单词。 用时将近3分钟。显然速度太慢,需要优化。

单词查找树(Trie)

我们知道,如果给出的单词以a开头,那么字典里以其他字母开头单词,就不需要我们做比较了。就好比二叉树查找,每次查找,总是可以丢掉不符合要求的那一半。 收到二叉树的启发,我们可以使用一种叫做Trie的多叉树来实现。

假设字典里有 ab, ac, c, d 这四个单词,生成的trie会是如下形状(t1、t2只是表述,方便做讨论):

   root(t1)
  /    \     \
 a(t2)  c(t3) d(t4)
/     \
b(t5)  c(t6)

做检查的时候,需要从跟节点,一级一级的向下找。 假设我们查找"ad",根节点的子节点 t2 的值就是 a,第一个字母匹配成功了。我们再匹配第二个字节 d,t2 的子树里,没有 d这个字母,匹配失败。则 ad 为一个错误的拼写。 只有当我们匹配了单词的每一个字母,并且最后一个字母是结尾字母,那么这个单词才是在字典中存在的。

具体实现

使用同样输入只花了不到 1.3 秒的时间,快了上百倍。

哈希表(Hash Table)

拼写查找,要求的是插入和查找速度快,Hash Table刚好符合要求。 同样的数据,只用了 0.14 秒,比trie的实现快了将近10 倍。 具体实现

Bloom Filter

Hash Table 从速度上来说,已经是极限了,看起来是最适合的算法。但在某些场景下,依然有更好的方法 -- Bloom Filter!

Bloom Filter 相对于 Hash Table 来说,最大的优势就是,Bloom Filter 不需要存完整的 key (比如单词),会更节约存储空间。 Bloom Filter 将一组 key(比如单词)通过多个哈希方程映射到一个数组内,并可以根据这个数组来判断这个单词是否已经被插入了。

算法的大体思路如下: 初始化一个 n 个 bit 的数组arr,插入某个值时,我们通过哈希方程,得到对应的 index,将数组这个位置设为 1。 假设我们使用 2 个哈希方程h1, h2,我们会得到两个 index(可能是1个),我们就将数组的这两个位置设为 1。

查找的时候,用所有的哈希方程,得到对应的 index,然后检查数组在这些位置上,是否均为1,如果均为1,则认为这个值被插入过。

伪代码如下:

require 'bitarray'
class BloomFilter
  attr_accessor :arr
  def initialize
    self.arr = BitArray.new(n)
  end

  def insert(key)
    arr[h1(key)] = 1
    arr[h2(key)] = 1
  end

  def include?(key)
    arr[h1(key)] == 1 && arr[h2(key)] = 1
  end

  # BloomFilter 会有多个哈希函数,2 个只是为了说明算法的工作原理。
  def h1(key)
    # xxx
  end

  def h2(key)
    # xxx
  end
end

Bloom Filter 虽然大大的节省了空间,但却有一定的概率出错(false positive),以为哈希方程有一定的概率会产生冲突(collision),既当查找时,一个值没有被插入,但却被误认为是插入过了。可以通过更长的数组和更多的哈希方程来解决这个问题。

Bloom Filter还有一个弊端,就是不能做删除操作。不过可以通过给每一位加上个 counter 来解决,就是所谓的Counting Bloom Filter,具体可以看这篇文章,这里就不详述了。

具体实现

同样的输入,需要0.11秒。

执行速度对比

SpellChecker
                      user     system      total        real
brute_force     162.660000   1.560000 164.220000 (168.961906)
by_trie           1.160000   0.100000   1.260000 (  1.305419)
by_hash_table     0.140000   0.000000   0.140000 (  0.145828)
by_bloom_filter   0.100000   0.010000   0.110000 (  0.108583)

相关代码

参考

共收到 24 条回复

那拼写建议呢?

jasl 将本帖设为了精华贴 12月22日 16:15

叫作 Trie 的多叉树其实就是实现数据库索引用到的 B+ 树(多叉树),查询的时间复杂度是 O(log n),它的优势是范围查询(比如楼上提到的拼写建议)。

为什么不用查找效率最好二叉树?因为在硬盘上顺序读比随机读快,并且 B+ 树深度比二叉树少的多,在查询的时候执行的顺序读比随机读多,所以 B+ 树更适合。

拼写检查的实际需求是 KV 查询, B+ 树并不合适。哈希表(Hash Table) 的 KV 查询时间复杂度是 O(1) ,它才是最好的选择。

Bloom Filter 是在哈希表的基础上,压缩信息,加速查询。这种压缩是有损数据压缩,丢失了一些信息,所以带来了可能出错的问题。

tuliang 回复

B+ 树要怎么用?

tuliang 回复

不是问 B+ 树是什么,问是问怎么做拼写检查。

tuliang 回复

B树并不是二叉树,你可能对B树有着错误的理解。

9楼 已删除
10楼 已删除

和敏感词过滤差不多啊 不过敏感词过滤还需要去噪之类

hooopo 回复

嗯,都是类似的问题。bloom filter 还有一个经典的应用是过滤弱密码。bloom filter 可以把很多的数据都 “存”在内心里,查起来快,redis 就 bloom filter 的插件。

alixiaomiao 回复

对 我理解错了 B树也是多叉树 它更接近B+树 B树和B+树,本质上都是一样的,只是B+树所有的根节点和枝节点上只保存关键字索引和其子节点指针,所有的数据信息都被保存到了叶子节点,这样每个枝节点可以存储更多的数据,从而降低树的层级高度,并且所有的叶子节像是一个链表一样,指向右边的叶子节点,从而可以有效加快检索效率,如果需要遍历所有的数据,只需要遍历叶子节点链式结构即可,方便且高效。

alixiaomiao 回复

我看错人了…不好意思…

你这代码居然是两年前写的。 😄

lanzhiheng 回复

被发现了…

yfractal 回复

总算把代码看懂了。 😄 BloomFilter 还需要找时间另外看一下。

  • Trie能给出拼写建议,类似搜索引擎上搜索词提示, 当然也能检查词汇是否存在。很节约储存空间。
  • HashTable只能判断词汇是否存在,不能给出拼写建议
  • 布隆过滤器用多个哈希函数将结果映射在bitmap上,用来判断词汇是否存在,不能给出拼写建议。节约空间,速度也快。
  • B树也能实现trie树的效果,且几乎没有差别(不限制子节点数量)。 只不过B树为磁盘读取量身定做,可按操作系统页的大小来存数据,尽量减少磁盘IO次数,更加强大复杂。

拼写检查用Trie有好处,因为在你还没写完某个词汇时,就可能判断出这个词汇不存在,不用写完了才告诉你。

early 回复

我没想到 B 树要怎么做拼写检查。。。

B 树和 Trie 不一样的地方是,Trie 没有深度约束,B 树有。用 B 树的话,就要把 com(组件对象模型),cool,computer 都存到叶子上。。。

B 树还有一个 order 的约束,在单词上,order 只能为 26,那就是 13 到 26,空间也会有大量的浪费。

像 com(组件对象模型),computer 这种,在 B 树似乎要村两次?

lanzhiheng 回复

这篇文章写的不怎么样(好吧,我偷懒了,没有再改改。。。

Hash 是准确的,准确的代价就是需要更多的存储空间。存储空间的代价有两个,一个是存储空间本身,一个是要分几次才能拿到内存里。

BloomFilter 是一个不准的 hash table。

比如输入一个 key,经过 hash function,得到一个 index,将 arr 的 index 设置为 1,既 arr[index] = 1

查找的时候,将输入通过 hash function 转化为数组的 index,如果 arr[indexe] 存在,就认为这个值插过了。

hash function 有一定的冲突的概率,比如 "abc" 和 "ccc" 通过 hash function 的到的 index 可能是一样的,就会误判。

伟大的计算机先哲,尼古拉斯赵四曾经说过,如果一次 hash 解决不了,就 hash 两次,所以 BloomFilter 一般会用多个 hash function。

yfractal 回复

不不不,我觉得写得很好,够简单。是我技术不到家 因为BloomFilter 的概念我之前没接触过,所以以后需要另外花时间看看。 😅

yfractal 回复

把约束去掉,约束是根据场景人为加上去的。 B树也是一个多叉树,多叉树都能实现拼写检查,差别只是子节点的储存方式, Trie是通过一个hash或数组来存,B树根据范围条件来放(按某种顺序对字符排序),当然可能就不需要叶子了,但也会觉得就不是B树了。

所以认为B树不适合或不行,我也是认同的。

23楼 已删除

Bloom Filter 是 Probabilistic data structure。分清这个概念就更好理解了。既然是概率,那就不是确定的。要求概率模型做确定性的事物是在本质上无视它的属性。所以拿它来和 hash table 类比是不恰当的

fantasticfears 回复

不理解不恰当的地方, 这个是对拼写检查这个问题,提出了四种解决方案,然后并做比较,在实际应用中,也会在 bit map 和 bloom filter 之间做选择。 bloom filter 在拼写检查中,如果出现 false positive,结果就是一个错误(没在字典里)的拼写,认为是正确的,这个在拼写检查里,一般是可以接受的。

early 回复

我想了一下,还是说出我的想法吧。

数据结构是靠约束来定义的,如果约束不满足,就不能叫这个数据结构了。就好比偶数,能被 2 整除的数,是偶数。如果不能被 2 整除,就不是偶数。

yfractal 回复

BloomFilter 是一个不准的 hash table。

我要放到语境里说。这个讨论中和应用无关。你说它是一个不准的 hash table。那我们从定义开始看,Hash Table 是一个数据结构,用 hash function 定义一个 K,V 的结构。同时实现了 associative array abstract data type(ADT)。而 Bloom Filter 是一个概率数据结构。首先它没有实现和 hash table 一样的 ADT,你不能取回存的值。它实现的接口大概是给定一个值,能否确定它不在这个集合里面。或者可能在这个集合里面(这是概率论最基本的假设了,概率的基本是集合。所以说是概率数据结构)。然后它是有 false positive 的,这个你已经讲了。结合这两点,这是我前面讲“拿它来和 hash table 类比是不恰当的”。

当然做拼写检查,讲这些都是多话了。

fantasticfears 回复

你是想说,纯粹从算法比较的角度来讲,这两个算法有本质的区别,所以不能直接比较?

这篇文章是从具体问题出发,提出解决方案,并做比较。算法是为解决实际问题而存在的。

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册