求问一道关于auto complete的题目

求问一道关于 quip onsite autocompele的题目 链接如下
http://www.1point3acres.com/bbs/ ... &highlight=quip
和
http://www.1point3acres.com/bbs/thread-385460-1-1.html
这道题如果不用 trie 该怎么做呢？ trie确实很占内存 刚刚试了一下自己的程序200mb的单词文档用了2g的内存， 看面筋好像面试官一直希望用除了trie能节省memory的方法做。
搜到一个compressed trie
http://theoryofprogramming.com/2016/11/15/compressed-trie-tree/

我在地里之前回答一个人的onsite的时候那人没怎么搭理我, 就很恼火, 然后上网搜了一下打个头的具体做法.

但是之前水太多帖子了, 感觉找不到回答了. 我按印象说的了..

autocomplete 等价于 typeahead, 基本上就是说给你一个prefix string, return top k matching string.

我印象中这个题有三种做法.

第一个是大家都会想到的, trie, 然后在每个节点上存储满足当前prefix string 的 top k 个. 好处是容易搜索,  坏处是占用空间大. 因为每个节点都需要int[26], 以及一个top k, 而且大多数并不是需要的.

第二个方法是把所有的word 按字典排序, 然后按给定的prefix 二分搜索开始以及结尾, 然后对着这中间的所有字符做 nlgk 排序. 这个方法是preprocess nlgn, 2遍 lgn, 和一遍 nlgk. 坏处是需要对所有的字符排序, 而且要maintain这个排序.

第三个方法是第一个方法的升级, 做的是ternary tree. 好像是个三分树. 其实我不熟, 没用过. 左岔是比当前root小, 右岔是比当前root大, 中岔是一样. 好像这样, 从来没有遇见过. 这个方法不会造26个结点, 好处坏处我完全不懂, 不敢评论了.

其实autocomplete的博士论文还挺多的, 你多搜搜把..

Trie或者Compressed Trie其实都是玩具.. Quip这个问题可能取材于真实的应用场景，具体问题具体分析，不要用应试思维去套用某一种算法或者数据结构 —— 因为最后能work的代码很可能是若干种方案的变形以及组合。

链接的帖子里提到了Elastic Search，那么就是类似于全文检索（full text search）的功能，一般使用倒排索引（inverted index）。并且倒排索引自身也有多种设计方案，所谓no single algorithm wins，要根据workload特性来选择。而根据链接的帖子里的描述，需要支持多个词匹配prefix，其实非常符合倒排索引的使用特性。

不过楼主提到自己使用的输入是200MB的单词文档，也就是说每个单词自成一行？这个似乎与链接帖子里提到的并不是同一种使用场景。

LC上有这个玩意吧，Search Autocomplete，我待会儿看看discussion页面有没有别的解法

szyyn95 发表于 2018-8-25 06:12
LC上有这个玩意吧，Search Autocomplete，我待会儿看看discussion页面有没有别的解法

看了一下 好像都是用trie 但是quip这道题好像面试官都要求不用trie的样子

killeralan 发表于 2018-8-25 07:19
看了一下 好像都是用trie 但是quip这道题好像面试官都要求不用trie的样子

我面过, 就是trie

czcbangkai 发表于 2018-8-25 09:39
我面过, 就是trie

诶 难道面试官没有很不情愿的 然后让你分析memory啥的。。

肥宅快乐水 发表于 2018-8-25 09:56
我在地里之前回答一个人的onsite的时候那人没怎么搭理我, 就很恼火, 然后上网搜了一下打个头的具体做法.
...

第二个方法啥叫搜索开始和结尾 我理解的是直接搜到了 prefix的位置然后往后查？

killeralan 发表于 2018-8-25 10:36
第二个方法啥叫搜索开始和结尾 我理解的是直接搜到了 prefix的位置然后往后查？

举个例子好了, 你里面有

string = [aaa, aab, abc, acc, acd, ace, aee]
freq = [1,2,5,7,5,3,2]

那么你现在搜以ac开头的prefix string, 按二分搜索会搜到acc的位置, 也可以搜到ace的位置, 都是lgn操作.
看lc34.

然后假如你现在要top2, 那就是用一个普通的priority queue.

killeralan 发表于 2018-8-25 10:36
第二个方法啥叫搜索开始和结尾 我理解的是直接搜到了 prefix的位置然后往后查？

被审核了, 类似lc34.

你string是按字典排序, 所以知道prefix 的第一个和最后一个的位置.

补充内容 (2018-8-25 11:39):
string = [aaa, aab, aac, abb, abc, acc, acd, ace, aee]
freq = [#,#,#..]
可以搜索到以acc开头的起始位置和最后一位, 然后做top k, 用priority queue即可