10个频繁出现的词

发布时间:2020-06-10 11:00:00
阅读量:60
作者:猎维人工智能培训
海量数据面试题

在一个文本文件中大约有1万行,每行1个词,要求统计出其中出现次数最频繁的10个词。

分析

用Trie树统计每个词出现的次数,时间复杂度是O(nl)(l表示单词的平均长度),最终找出出现最频繁的前10个词(可用堆来实现,时间复杂度是O(nlog10)。

扩展

什么是Trie树?

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,常用于统计和排序大量字符串等场景中(但不仅限于字符串),且经常被搜索引擎用于文本词频统计。它的优点是最大限度地减少无谓的字符串比较,查询效率比较高。

Trie树的核心思想是以空间换时间,利用字符串的公共前缀来降低查询时间的开销,以达到提高效率的目的。

它有以下三个基本性质。

(1)根结点不包含字符,除根结点外每一个结点都只包含一个字符。

(2)从根结点到某一结点的路径上经过的字符连接起来,即为该结点对应的字符串。

(3)每个结点的所有子结点包含的字符都不相同。

Trie树的构建

先来看一个问题:假如现在给定10万个长度不超过10个字母的单词,对于每一个单词,要判断它出没出现过,如果出现了,求第一次出现在第几个位置。这个问题该怎么解决呢?

如果采取最笨拙的方法,对每一个单词都去查找它前面的单词中是否有它,那么这个算法的复杂度就是O(n2)。显然对于10万的范围难以接受。

换个思路想:假设要查询的单词是abcd,那么在它前面的单词中,以b,c,d,f之类开头的显然就不必考虑了,而只要找以a开头的单词中是否存在abcd就可以了。同样,在以a开头的单词中,只要考虑以b作为第二个字母的,一次次缩小范围和提高针对性,这样一个树的模型就渐渐清晰了。

因此,如果现在有b、abc、abd、bcd、abcd、efg和hii这6个单词,可以构建一棵图所示的Trie树。

如图1所示,从根结点遍历到每一个结点的路径就是一个单词,如果某个结点被标记为红色(如图中加黑点的节点),就表示这个单词存在,否则不存在。那么,对于一个单词,只要顺着它从根结点走到对应的结点,再看这个结点是否被标记为红色就可以知道它是否出现过了。把这个结点标记为红色,就相当于插入了这个单词。

这样一来,查询和插入可以一起完成,所用时间仅仅为单词长度(在这个例子中,便是10)。这就是一棵Trie树。

图1

我们可以看到,Trie树每一层的结点数是26i级别的。所以,为了节省空间,还可以用动态链表,或者用数组来模拟动态,而空间的花费不会超过单词数乘以单词长度。

查询

Trie 树是简单且实用的数据结构,通常用于实现字典查询。我们做即时响应用户输入的Ajax搜索框时,就是以Trie树为基础数据结构的。本质上,Trie树是一棵存储多个字符串的树。相邻结点间的边代表一个字符,这样树的每条分支代表一个子串,而树的叶结点则代表完整的字符串。和普通树不同的地方是,相同的字符串前缀共享同一条分支。

下面再举一个例子。给出一组单词inn、int、ate、age、adv、ant,可以得到图2所示的Trie树。

可以看出以下几条。

1 每条边对应一个字母。

2 每个结点对应一项前缀。叶结点对应最长前缀,即单词本身。

3 单词inn与单词int有共同的前缀"in",所以它们共享左边的一条分支(根结点→i→in)。同理,ate、age、adv和ant共享前缀"a",所以它们共享从根结点到结点a的边。

图2

查询操纵非常简单。例如,要查找int,顺着路径i→ in→int就找到了。

搭建Trie的基本算法也很简单,无非是逐一把每个单词的每个字母插入Trie树。插入前先看前缀是否存在:如果存在,就共享,否则创建对应的结点和边。例如,要插入单词add,就有下面几步。

(1)考察前缀"a",发现边a已经存在。于是顺着边a走到结点a。

(2)考察剩下的字符串"dd"的前缀"d",发现从结点a出发,已经有边d存在。于是顺着边d走到结点ad。

(3)考察最后一个字符"d",这次从结点ad出发没有边d了,于是创建结点ad的子结点add,并把边ad→add标记为d。


本题解析节选自July一书《编程之法:面试和算法心得》第六章 海量数据处理。

更多资讯