Koala++/屈伟
查询补全可以分为两种：
1. 线下计算出来的结果，比如输入“机器学”，提示“机器学习”
2. 一种是需要运行时确定的，比如输入“机萁学习”，这个词从来没有人搜索过，没办法从线下计算的结果中得到。
首先数据应该从查询日志中得到，因为这是最能反应用户搜索趋向的数据了，先要从这里把所有的查询词和相应的查询次数得到，比如“机器学习 100次”，其中大致要繁体转简体，符号全角半角统一，限制查询的长度，去掉一些符号，比如“Koala++、”，可能就是用户点回车的时候不小心点到了“、”。
线下计算方法1. 首部一致
这种情况是最常见的，有点类似于trailing wildcard query，就是通配符在尾部的情况，比如quwe*，这里只是处理首部一致的情况，可能马上会想起前缀树，trie之类的数据结构，可是对一个不是面向全文搜索的搜索引擎，用户量又不是很大的情况，查询数据本就没多少，何苦呢？再说了，这些结构相对于Hash Map来说，只是节省内存而已，我测了一下我写的，用Hash Map才用了11M的内存，完全没必要用别的数据结构优化，Hash Map的查询时间复杂度是O(1)，这更不必说。所以这个方法是很直接的，举一个例子，“数据压缩”这个查询，保存在Hash Map中就是“数”=>“数据压缩”，“数据”=>“数据压缩”，“数据压”=>“数据压缩”，这里不应该有 “数据压缩”=>“数据压缩”，因为别人都输入完了，没有必要提示。
2. 首部一致拼音
用户输入些字母，将用户输入的字母当作拼音来看，比如：用户输入了“k”，提示“考拉”。这也不是什么问题，将“考拉”的拼音得到“kaola”，然后也使用Hash Map：“k”=>“考拉”，“ka”=>“考拉”，“kao”=>“考拉”，“kaol”=>“考拉”，“kaola”=>“考拉”，这与上面的一点点不同是“kaola”=>“考拉”这个是有的。另外，如果要学google那么，就要把“k”=>“考拉”去掉，不将单个字母当作拼音的一部分处理。
3. 子串一致
这里要将首部一致的这种情况排除，因为它已经计算过了。这里可以枚举所有长度大于K的子串，加入到Hash Map中，比如“数据压缩”，K=2时，保存到Hash Map里的有：“据压”=>“数据压缩”，“压缩”=>“数据压缩”，“据压缩”=>“数据压缩”。这里长度K不能太小，比如等于1，那提示的也太乱了，还不如不要。
4. 子串拼音提示
将刚才提示的全部转换成拼音就可以了，还以“数据压缩”为例：“juya”=>“数据压缩”，“yasuo”=>“数据压缩”，“juyasuo”=>“数据压缩”，这里也许也应该限制一下，因为也许没人有会输入很长的拼音查询，还是用长度限制一下，节省点内存比较好。
5. 纠错提示
用下面介绍的“运行时计算”的方法得到错误与正确的查询之间的关系，比如“数具挖掘”=>“数据挖掘”，这些数据可能要从日志中得到。
在向Hash Map里保存时，只用保存Top M个，因为最终也只会显示M个，比如google最多显示10个提示，格式是“query=>suggest1,suggest2,…suggestM”，suggest1, suggest2 ,…, suggestM要根据查询次数进行排序。
1. 将“首部一致”和“首部一致拼音”这两种的Hash Map合到一起(当然，算的时候就合到一起了)，称为suggestA，用户输入“数”，那就到suggestA里找，发现“数”=>“数据压缩，数据分析，数据挖掘”，就返回这中个侯选查询。用户输入“k”，到suggestA里找，发现“k”=>“kaola，koala++”，则返回“kaola，koala++”。
2. 将“子串一致”和“子串拼音提示”这两种的HashMap合到一起，称为suggestB，用户输入“压缩”，在suggestA中没有找到时，才到suggestB中找，发现“压缩”=>“数据压缩，解压缩”，则返回“数据压缩，解压缩”，还可以在suggestA中没有返回足够的提示时用suggestB的结果补充，要注意去掉重复的。
3. 如果在suggestA和suggestB中都找不到，那就将它转换成拼音去查找，比如“石是求”转换成拼音“shishiqiu”，到suggestA中去找，找不到再去suggestB中找，比如找到了“shishiqiu”=>“实事求是”(经“实事求”=>“实事求是”的拼音转换)，就返回“实事求是”，但这里有一个问题，比如“围萁”(围棋的误写)的拼音是“weiqi”，而用“weiqi”在suggestA中找，可能会得到“卫青”，因为“卫青”拼音“weiqing”开头也是“weiqi”，这看起来不太合适，它有一点点线上计算。
运行时计算运行时计算与tolerant retrieval有很大的重复，并且要求很高的效率，并且用户输入错了，他也应该是知道的，也许不用纠正。不像已经是发向服务器的查询，是无可挽回的了。
Logo语言的老师讲，一个问题，50个人就有50种正确解法。这话就算是对的，可是50个人得到50个正解的解法前，会创造500种错误的解法。运行时计算，就是对付这种用户所犯的独一无二，或是极度罕见的错误。
1. 在1还是没有找到的情况下，比如，用五笔的人，经常把“机器学习”输入成“机哭学习”，那输入“机哭学习”的时候，可以编辑距离的方法算一下它与“机器学习”的编辑距离，这个要使用k-gram与编辑距离结合起来的方法算，不然运算量太大。但种方法很麻烦，因为找不到提示就要算编辑距离，那输入“甜切片面包”时没在在Hash Map中找到(因为已经输入完了)，还要算一个编辑距离提示个“咸切片面包”吗？那就还要记录完整查询的列表之类的东西，总之是为一个没必要的功能搞的很麻烦。并且这个在tolerant retrieval中，还可以看一下idf值，也许更合理。
2. 方言的影响。方言中有时会把两个音分不清，比如湖北人发“n”和“l”就差不多，他们自己有时也搞不清，江西人发“r”和“l”又差不多。比如江西九江的用户想搜索“太热了”，他又比较懒惰，所以他输入的是拼音“tailele”或是“tairili”(我舍友的经典笑话)，这两个我想应该是没有提示的(google都提示不出来)，那就要用类似soundex的索引处理，soundex的核心做法就是将发音相似的音映射到同一个值上去，比如：“tailele”这个在suggestA和suggestB中都找不到，那就试一下“tairele”，“tairere”，“tailere”，当然这不是soundex，在soundex中比如我们将“l”和“r”映射到同一个值0，那“tairele”，“tairere”，“tailere”，“tailele”都会映射成“tai0e0e”，在他搜索“tailele”出会先映射到“tai0e0e”去找到这4个侯选查询，也许也没4个，只有1个“tairele”。
但这只解决了很小很小的一部分，中国方言数量很多，据我同学说，相邻县方言不同很正常，当然有心情也可以根据IP一个地方搞一个，但有的地方方言我个人感觉比印度英语还难懂，我怀疑还存在对应关系吗？而且有的方言比如上海话，的确是字都不一样。
当然我个人是坚决反对对方言进行支持的，工作量大不说，意义也不大，只是对那些连普通话都讲不好的人才有用，而且我一门方言也不会，对我完全没意义。
中国很多人都学过英语，虽然很多人脑子里只留下了几个四字单词，但还是崇洋媚外的，以为吃个外国食物就是国际人士的蠢货，比如想搜索一家pizza店，如果店名是英语，谁知道那些英语盲会输成什么，pisa，pissa。而这可能还是用编辑距离或是soundex进行纠错的，当然全完可以在搜索时进行纠错，没必要在补全时纠错。