从单词统计问题看面试

By | 10月11日
Advertisement

由于写作仓促,文中难免会有错误,欢迎指出。

问题描述

首先这里对单词的界定是:以空白分割的字符序列。单词统计的问题可以描述为:在一篇正常格式的英文文档中(作为面试,这里并没有提及中文分词和单词统计的问题),统计每个单词出现的次数,要求统计出现次数最多的N个单词和相应的出现次数。问题简单明了,无需对字面做更多的解释。

为什么面试官都喜欢考诸如此类的问题?

这类问题,大都有一个共同点:不仅要考虑数据的存储,而且要考虑排序的问题。更重要的是,普通方法可以解,偏偏面试官要找性能最好的、形式最优雅的。

怎么解?

仔细研读一下题目,发现其实只有三件事情要做:1.单词次数统计 2. 排序。3.输出前N个,其中问题3只是问题2的衍生,因此可以忽略。进一步分析发现,其实这是典型的TOP K问题。抛开TOP K问题的经典解决方案不提,我们先看看一步步来看问题的解决思路。

1. Map

C++ Standard Template Library中提供了一种高效的容器Map, 它是一种键值对容器(关联容器),因此可以轻松存储<单词, 次数>这种键值序列,因而,最简洁的解决方案可以是这样的:

int main(void){
    Map <String , int> wc;
    Map <String , int>::iterator j;
    String w;
    while( cin >> w ){
        wc[ w ] ++;
    }
    for( j = wc.begin(); j != wc.end(); j++ ){
        count << j->first <<  " : " j->second << "\n";
    }
    return 0;
}

由于Map的特性(数据插入时保证有序),因此输出的结果其实是按照key(也就是单词)排好序的。所以,还需要对输出的结果进行排序。至于怎么排序,sort,qsort,还是自建heap sort,不再赘述。

这样已经很好了,Map容器本身内建红黑树,使得插入的效率很高。

但是,这样真的好吗?别忘了,面试官的要求更高。

2. Hashtable 神器,一键直达,效率再快一点

对于单词和单词次数的映射,除了使用Map外,还可以使用自定义的hash表,hash表的节点应该包括三个基本的域:指向单词的指针或String,单词的出现次数int,指向下一个节点的指针node *。假设我们处理hash冲突的方案是链地址法。则:

Hash表node的定义为:

typedef struct node{
    char * word;
    int  count;
    node * next;
} node;

再次假设,处理的独立的单词个数不超过5w, 因此可以选择50021 这个质数作为hash表的大小。而hash算法,我们可以选择常用的BKDR算法(以31为累乘因子),这样,可以将单词映射为一个unsigned int的整数:

#define HASH_SIZE 50021;
#define MUL_FACTOR 31;
node* mmap[HASH_SIZE];

unsigned int hashCode( char *p){
    unsigned int result = 0;
    while(*p != '\0' ){
        result = result * MUL_FACTOR + *p++;
    }
    return result % HASH_SIZE;
}

函数wordCount( char *p )用于将单词和单词的出现次数插入hash表中,如果hash表中有相应的节点,则增加单词的次数并返回,否则需要添加新的节点到hash表的表头并初始化次数为1.

 1 void wordCount( char *w ){
 2     unsigned int hashCode = hash( p );
 3     node * p;
 4
 5     while( p = mmap[hashCode];p!=NULL;p = p->next ){
 6         if(strcmp(w, p->word) == 0){
 7             (p->count)++;
 8             return ;
 9         }
10     }
11
12     node*q = (node*) malloc(sizeof(node));
13     q->count = 1;
14     q->word = (char *) malloc(sizeof(w) + 1);
15     strcpy(q->word, w);
16     q->next = mmap[hashCode];
17     mmap[hashCode] = q;
18 }

同样,hash表只是提供了数据存储,并没有排序,排序的问题,还需要你来完成。

这样似乎就完美了。

可素,伦家既不懂算法,又不会C++的容器。肿么办 ?

3. Shell版本的单词统计

Linux提供了很多文本操作的工具,比如uniq, tr ,sort。而管道的存在,恰到好处的解决了文本和单词及中间处理结果需要存储的问题。最重要的一点,这些工具是一系列的黑盒,你只需要知道如何使用,而大不必去在乎内部实现的细节。

对于本题,用Linux 工具去处理,命令可以是:

cat  word |
tr –cs a-zA-Z\’ ‘\n’ |
tr A-Z a-z |
sort |
uniq –c |
sort –k1,1nr |
head –n 10

对该程序每一行的解释:

  1. cat word 将word文件的内容读入缓存区,并作为下一个命令的输入
  2. tr –cs a-zA-Z\’ ‘\n’ 将非字母字符转换为换行符,保证一行一个单词
  3. tr A-Z a-z 将所有单词转为小写形式,保证and和And是同一个单词
  4. sort 按单词排序
  5. uniq –c 统计每个单词的重复次数,也就相当于单词的出现次数
  6. sort –k1,1nr 按照出现次数排序逆序排序,-n指定数字比较。-r指定逆序排序
  7. head –n 10 输出出现次数最多的10个单词和它们的出现次数

写到这里,突然想起若干年前去百度面试的时候,一个技术T5的大拿问的问题,也就是这道单词统计的问题:一个文本中包含了很多单词,每行一个单词,如何统计每个单词的次数?极其小白的我毫不含糊的回答:PHP脚本中每次读一行,用关联数组存单词和单词次数…….结果必然是惨烈的。

4. 文本处理的利器-AWK

既然提到了linux工具,那就不得不提一下awk(ɔk), awk是一个强大的文本分析处理工具。Wiki上如是说:

AWK是一种优良的文本处理工具,Linux及Unix环境中现有的功能最强大的数据处理引擎之一。AWK提供了极其强大的功能:可以进行正则表达式的匹配,样式装入、流控制、数学运算符、进程控制语句甚至于内置的变量和函数。它具备了一个完整的语言所应具有的几乎所有精美特性。

虽然仅是溢美之词,但是不得不承认awk确实很强大。

awk -F ' |,'
'{
    for(i=1; i<=NF;i++){
        a[tolower($i)]++;
    }
}

END{
    for(i in a)
        print i, a[i] |"sort -k2,2nr";
}'  word

gawk 3.1+中,可以使用内置函数asort和asorti对数组进行排序,不过排序的功能较弱。例如asort(a) ,若a是关联数组,asort的行为是只对值排序,而键将被丢弃,取而代之的是新的1-n的数字索引。这可以通过自定义排序函数的方式或者结果通过管道传递给系统sort排序解决。

5. 数据库版本的方案。

我们这里假设文本已经是一行一个单词。数据库表的基本结构为:

CREATE TABLE `test` (
  `word` varchar(20) DEFAULT NULL
) ENGINE=MyISAM DEFAULT CHARSET=gbk;

单词入库(也可以load data in file):

awk '
BEGIN{
    sql="insert into test(word) values ";
    mysql="mysql -hxxxxxx -uxxxxx -pxxx test -e ";
}

{
    for(i=1;i<=NF;i++){
        sq="\"" sql "('\''" $i"'\'')" "\"";
        print mysql sq |"sh -x";
    }
}' word

那么简单的查询:

select word,count(word) as total from test group by word order by total desc;

就可以得到单词的次数。这种方法很简单,因为数据库替你完成了所有统计和排序的工作,这也是为什么很多人一旦有什么需求就求助于数据库。

基于Key-Value的缓存系统(Redis等)也可以完成排序的功能,这里不再赘述。

思考

如果你是面试官,你看好哪一种解法?算法和数据结构的,还是shell的,awk的。就我而言,我认为面试是挑选人才的,而不是靠所谓的“奇技淫巧”去为难别人的。如果是我,看到有人用了shell的方式,或者awk的方式,我会给他高分。虽然算法是王道,但真的需要“一切从源码做起”么?

参考文献:
1. http://www.cnblogs.com/ggjucheng/archive/2013/01/13/2858470.html
2.《shell脚本指南》
3.《编程珠玑》

Similar Posts:

  • HR(人事)经理必看――面试问题大全

    HR经理必看――面试问题大全 影响他人的能力 如果你是某事的负责人的话,你很容易让他人听你的:但是,当你不是负责人时,让别人听自己的话是非常难的事.想要培养自己影响他人的能力的话,得通过与他人的共同的理想和目标来建立个人关系.那些拥有影响力并能感召他人的应聘者通常能够使同事和客户支持自己的观点和目标.下面的一些问题能够考核出应聘者在这方面的能力. No 1. 请你举一例说明你曾经使某人做他并不喜欢做的事情. No 2. 请描述一下这样一个经历:你使别人参与.支持你的工作,并最终达到了预期目的.

  • java,scala之spark streaming 版本的单词统计(通过监听端口)

    ubuntu安装netcat Ubuntu上默认安装的是netcat-openbsd,而不是经典的netcat-traditional.  网上例子很多都是以netcat-traditional为例.  sudo apt-get -y install netcat-traditional  设置默认的nc,选择/bin/nc.traditional:  sudo update-alternatives --config nc 命令       nc -lk 8888 java版本 import

  • 从统计数据看各大邮箱的使用情况

    从统计数据看各大邮箱的使用情况 个人 +--------------+-------+---------+ | domain | count | percent | +--------------+-------+---------+ | qq.com | 14618 | 63.9066 | | 163.com | 3840 | 16.7876 | | 126.com | 1837 | 8.0310 | | sina.com | 595 | 2.6012 | | yahoo.cn | 225 |

  • MapReduce 单词统计案例编程

    MapReduce 单词统计案例编程 一.在Linux环境安装Eclipse软件 1. 解压tar包 下载安装包eclipse-jee-kepler-SR1-linux-gtk-x86_64.tar.gz到/opt/software目录下. 解压到/opt/tools目录下: [[email protected] tools]$ tar -zxf /opt/sofeware/eclipse-jee-kepler-SR1-linux-gtk-x86_64.tar.gz -C /opt/

  • 山东理工大学ACM平台题答案 1180 C语言实验——单词统计

    C语言实验--单词统计 Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^ 题目描述 从键盘输入一行字符(长度小于100),统计其中单词的个数,各单词以空格分隔,且空格数可以是多个. 输入 输入只有一行句子.仅有空格和英文字母构成. 输出 单词的个数. 示例输入 stable marriage problem Consists of Matching members 示例输出 7 #include <stdio.h> #include <

  • 用spark建立一个单词统计的应用

    声明:版权所有,转载请联系作者并注明出处  http://blog.csdn.net/u013719780?viewmode=contents 博主简介:风雪夜归子(Allen),机器学习算法攻城狮,喜爱钻研Meachine Learning的黑科技,对Deep Learning和Artificial Intelligence充满兴趣,经常关注Kaggle数据挖掘竞赛平台,对数据.Machine Learning和Artificial Intelligence有兴趣的童鞋可以一起探讨哦,个人CS

  • 从单词统计看Map

    直接看代码: String str = "Do as I say , not as I do"; str = str.toLowerCase(); str = str.replaceAll("[^A-Za-z]", " "); str = str.replaceAll("\\s+", " "); String [] s = str.split("\\s+"); Map<String

  • 站在面试官角度看面试

    当你走近会客室,面试过程就开始了,当然你得不卑不亢,谦虚谨慎,除了这些放之四海皆准的原则,你还应该知道.面试就是个沟通,让对方认识到你的实力,并且你也了解到是否喜欢并且能做这个工作,后者可能很多人没有意识到. 沟通很奇妙,每个人都说自己能很好的别人沟通,在面试官看来,沟通不是让你不停的附和或者滔滔不绝讲述,而是从对话中能了解双方的立场,无论是支持和反对,都能深入对问题的探讨,怕的是无论对方说什么,自己都在说自己的那一套,这样的人也许是一个目标清晰的人,但不是一个好的沟通者,因为对方说什么都不能影

  • 【数据结构-trie树】trie数实现单词查询和单词统计

    参考内容: 1. 这位童鞋的文章 http://blog.csdn.net/zhulei632/article/details/6704496 2. 严蔚敏 -数据结构 1.键树的定义: 键树又叫"数字查找树".深度>=2 . 树中的每个节点一般不是直接包含关键字,而是包含组成关键字的符号(当然叶子节点除外,叶子节点可能包含整个单词以及词频,非叶节点也可包含单词和词频).根据存储结构的不同,又分为双链树和多重链表树.或者就是常说的"Trie树",取自检索&qu

  • 在一个文本文件中的单词统计频率并打印前十个

    //单词结构体 struct word{ char name[30]; int num; struct word *next; }; //这是统计单词部分,用的是fgetc函数对文本进行读取,因此没有手动读取过程,直接将txt放入指定目录下就可以读取,判断是否读完用了feof函数 void readfile(struct word *head) { FILE *fp; if((fp=fopen("D:\getin.txt","r"))==NULL) //没有文件 {

Tags: