引言

前几日，QQ群里有个人提了两个问题：

1、现有一组关键词，如：{internet; music; video…}，给定一篇文章，请统计出文章中这些关键词分别出现的词频。请描述数据结构、算法，相应的时间复杂度，可以用伪代码加注释或者文字辅助说明的方式。
2、实现搜索的联想功能，比如“liu”出现刘德华，刘若英，在继续输入刘德，就剩1个了。

对于这两个问题，我的第一反应是：
1、做hash，扫描一遍统计次数。
2、字典树，输入的时候遍历字典树当前节点下的子节点，之后将拼音转化为中文。

我认为问题2的答案优化空间很大，但是想了一会又始终不得要领。群里有人回复“马尔可夫链”，在网上搜索一通，似乎和这个问题风马牛不相及，直到找到一篇论文：《基于Markov链的整句输入算法研究与实现》，研究一番，不由得感慨：自己的过去对问题的认识实在太肤浅。… Read the rest