[EPI] Design Problems笔记

2016-07-21 00:27:00

Element Of Programming - Design Problems

设计题的三个要点：
1.组件分解
2.并行计算
3.利用缓存

1. Spell Checker

场景：

给一个word，假设这是一个拼错的英文单词，我们应返回一个list of word，list里的words都是和word可能的正确拼写。

分析：

有两个概念要clarify:
1.对于“拼错"这个概念，什么叫"拼错"，什么叫"拼对"，都是相对的，我们可以假设一本词典，这里面所有的单词都是拼对的，其他的都是拼错的。还有一个延伸就是，如果这个词”拼对“了，程序还check不check呢？
2.给一个word，我们先生成一堆和他很像的词，这些词可能拼对也可能拼错，我们把拼对的返回，问题在于，这里的”像“怎么界定？这里我们假设 - “像”，表示所有和word的edit distance(Levenshtein distance) exactly为2的单词们。

数据结构：

把词典预处理成一个map，key是所有的字典单词，value无所谓。我们只想快速的知道这个word是不是词典(拼对)的，对这个单词的其他性质并不关心。

核心算法：

给一个word，生成所有与这个word的edit distance(只substitute，不add也不remove)为2的所有string来,挨个去查hashmap。查出来的这些按照某种rank algorithm排序选出最高的10条。
至于这个排序算法，请看本题的后续部分。

复杂度：

对于一个request_spell_check(String word), 假设字母有m(英语的话就是26)个，单词长n(一般来讲1~15)
时间O(m^2 * n^2),因为设定edit distance为2，改装一个word的可能性有n(n-1)(m-1)^2/2种，假设改写一种是一条java语句(一次循环)，那么改写一个interesting(长度为11)大约需要循环次数为:34375，假设1s内一台电脑可以运行10^8条java语句，那么每个request的耗时大约是0.3ms，1ms这个级别，是可以接受的。
空间O(1),通过上面的查找，查找的结果可能会非常大，我们只要返回一个ranked list of suggestions就好了，比如rank最高的十条。

后续：

关于排序算法，输入是一个list of word，这些word都在词典里，是拼对的词，现在要从里面找出10条最可能是答案的词，明显是一个没有标准答案的问题，所以要根据情况分析trade-off:

Typing errors model，我们的排序就要根据键盘的layout来判断了；
Phonetic modeling，情景：我想打一个词，只会读，不会写，比如kat打出了cat。解决方法是，把输入的单词按phonemes划分，每段按发音进行替换。
History of refinements，搜集用户打错的数据 - 用户经常会打一个词，然后删了，打了另一个词，然后request请求，这两个词第一个词就是潜在的错误拼写，第二个是正确拼写。
Stemming，通过把["computers", "computer", "compute", "computing"]提取为"compute"，当我们拿到一个word时，对他stemming，然后把stemming结果的列表返回。

2. Stemming Problem

场景：

Stemming是搜索引擎normalize环节的一个技术，中文叫做词干提取，顾名思义，即把["computers", "computer", "compute", "computing"]提取为"compute"。Stemming既用在query string上，也用在document的存储中。前者可以延伸语义，比如查compute的时候很可能对computer感兴趣或者你想查的根本就是computer。后者可以大大降低搜索引擎索引的存储大小，也可以提高搜索效率。

分析：

Stemming明显是一个没有标准答案的问题，基本上是在trade-off，根据情景解决问题。而且这个题目太大，这里只是简述。
本质上Stemming就是根据某种规则(rule)重写(rewrite)。

重写，基本都是focus在后缀(suffix)上，改后缀(wolves -> wolf)，删后缀(cars -> car)。
规则，这些规则干的事儿就是，先找到哪儿到哪儿是后缀(应该有个后缀表什么的)，然后把这个后缀transform一下(应该也有个转换表什么的)。

一个有效的实现方法是根据这些规则建立一个Finite State Machine - 有限状态机。

后续：

越sophisticated的system会有更多的exceptions，即考虑更多地特殊情况，比如Chinese -> China这种。
Porter stemmer，作者Martin Porter，目前是公认最好的英语stemming algorithm。
其他的方法有：stochastic methods, n-gram based approaches.