H******7 发帖数: 1728 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: HanSolo7 (隼), 信区: Programming
标 题: load一个巨大的k-v table到一个view里,有搜索功能 怎么设计?
发信站: BBS 未名空间站 (Sat Jan 17 00:42:58 2015, 美东)
有一个100万行的文件。
keyabcbalabala: 1
keycdebalabla: 2
keyxyzbalabala: 3
...
...
提供一个功能 在搜索兰里打 "abc" 就显示出所有Key里包含abc的kv pair.
有2个问题:
1. 为了提高用户体验,怎么设计数据结构?
2. 有没有优化手段?
谢谢。 | w********s 发帖数: 1570 | 2 对key的任意substring作hash
对hashtable优化,当只有一个v的时候,直接存储v,而不是list ptr | w********s 发帖数: 1570 | 3 如果你做过搜索引擎的话,或者看过其中细节的话,应该知道. | l*****k 发帖数: 1059 | | s********t 发帖数: 11 | 5 实际上不会对所有substring做索引的。现实当中会有个ignore words词表,而且最小
词长度会有限制,比如至少3个字符。这样的话可以考虑切词(leetcode有work break
)建立索引。
提高用户体验可以将相关索引直接返回。比如用户请求abc,返回abc,abcd,abce等等
。如果索引用某种树结构,可以考虑将查到结果的前后n条记录都返回。高级一点的是
做相关词处理,计算一组用户输入词序列的输入概率,然后弹出相关词。这需要记录用
户每一次输入然后跑某种模型算法得到。也有一些实时算法可以及时的弹出相关词。
貌似扯远了……。 |
|