j******2 发帖数: 362 | 1 板上原来有人面经里的:
search box的search suggestion function。 不一定是exactly prefix matching. 例
如type一个人的middle 或者是last name, match 的也要出现在search box 里面。
用trie吧,没搞懂如果type in "xyz", 姓"xyz"和名"xyz"的咋能都reach? |
x*********w 发帖数: 533 | 2
trie吧, 用trie存储所有名字的所有后缀?
【在 j******2 的大作中提到】 : 板上原来有人面经里的: : search box的search suggestion function。 不一定是exactly prefix matching. 例 : 如type一个人的middle 或者是last name, match 的也要出现在search box 里面。 : 用trie吧,没搞懂如果type in "xyz", 姓"xyz"和名"xyz"的咋能都reach?
|
w********p 发帖数: 948 | 3 这个要再清楚点。
比如一个人的名字是 Steven Paul Jobs
当你type "aul" 的时候 Steven Paul Jobs 要不要显示。
假设是说,当你type
S
St
Ste
Stev
Steve
P
Pa
Pau
Paul
J
Jo
Job
Jobs
的时候Steven Paul Jobs的名字都要被显示。
那么就很简单了
把每个单词 都放在Trie tree 里, 同时建个map,把每个单词和full nam对应起来。
Steven -> Steven Paul Jobs
-> Steven Gnome
Paul -> Steven Paul Jobs
-> Paul Xu
Jobs -> Steven Paul Jobs
-> Jessica Jobs
【在 j******2 的大作中提到】 : 板上原来有人面经里的: : search box的search suggestion function。 不一定是exactly prefix matching. 例 : 如type一个人的middle 或者是last name, match 的也要出现在search box 里面。 : 用trie吧,没搞懂如果type in "xyz", 姓"xyz"和名"xyz"的咋能都reach?
|
j******2 发帖数: 362 | 4 明白了,谢谢大牛!!
【在 w********p 的大作中提到】 : 这个要再清楚点。 : 比如一个人的名字是 Steven Paul Jobs : 当你type "aul" 的时候 Steven Paul Jobs 要不要显示。 : 假设是说,当你type : S : St : Ste : Stev : Steve : P
|
d**e 发帖数: 6098 | 5 如果输入aul时也要显示呢?
【在 w********p 的大作中提到】 : 这个要再清楚点。 : 比如一个人的名字是 Steven Paul Jobs : 当你type "aul" 的时候 Steven Paul Jobs 要不要显示。 : 假设是说,当你type : S : St : Ste : Stev : Steve : P
|
j******2 发帖数: 362 | 6 [新加一问]:
怎么把priority加到trie的数据结构里
priority #1 : 在你的friend list 里面
priority #2 : 在你的second degree friend list 里面
priority #3 : 当前hot query search like ipad3, iphone5 之类的. |
w********p 发帖数: 948 | 7 Trie 的建立或者搜索就要改。
或者Paul, aul, ul l 都塞到trie里。
或者trie的每个节点都要搜,-- 这种就不如直接map了。
【在 d**e 的大作中提到】 : 如果输入aul时也要显示呢?
|
w********p 发帖数: 948 | 8 加priority 不过是多了些条件而已
有多种方法解决。
比如在map里first name/ last name/ middle name 对应的不是一个full name, 而是
一个class object 其中包括 full name,priority 等等。但是这个方法慢, memory
用的多
或者在你建立trie的时候,就是按照friendship degree 分的。
这样会快些,但是space 要多些。如果像是facebook, linkedin这种数据量很大的,这
个比上个方法好些。
仅供讨论,毕竟没有仔细想,和写。
【在 j******2 的大作中提到】 : 板上原来有人面经里的: : search box的search suggestion function。 不一定是exactly prefix matching. 例 : 如type一个人的middle 或者是last name, match 的也要出现在search box 里面。 : 用trie吧,没搞懂如果type in "xyz", 姓"xyz"和名"xyz"的咋能都reach?
|
c******a 发帖数: 789 | 9 按照friendship degree分建造trie,这是说:每个user按degree level得有好几个
trie,trie里是他同degree所有connection。这空间可是n^2哦。但因为pre-process
了,查起来会快很多。
第一个方法要online地sort,会慢。但不明白为啥memeory用得多。
memory
【在 w********p 的大作中提到】 : 加priority 不过是多了些条件而已 : 有多种方法解决。 : 比如在map里first name/ last name/ middle name 对应的不是一个full name, 而是 : 一个class object 其中包括 full name,priority 等等。但是这个方法慢, memory : 用的多 : 或者在你建立trie的时候,就是按照friendship degree 分的。 : 这样会快些,但是space 要多些。如果像是facebook, linkedin这种数据量很大的,这 : 个比上个方法好些。 : 仅供讨论,毕竟没有仔细想,和写。
|
r**h 发帖数: 1288 | 10 感谢指点!不过有一种情况我不大明白:
可以想见每个用户的priority情况都不一样的(比如说A是B的好友但未必是C的好友)
。那种情况下应该如何处理呢?面对每个用户都建立一个包含所有用户信息的trie感觉
不现实啊
或者说每个用户,因为他的好友数这些都很有限。因此可以在他的好友里面直接先查了
,如果不行的话,再到general的trie里面去查?
memory
【在 w********p 的大作中提到】 : 加priority 不过是多了些条件而已 : 有多种方法解决。 : 比如在map里first name/ last name/ middle name 对应的不是一个full name, 而是 : 一个class object 其中包括 full name,priority 等等。但是这个方法慢, memory : 用的多 : 或者在你建立trie的时候,就是按照friendship degree 分的。 : 这样会快些,但是space 要多些。如果像是facebook, linkedin这种数据量很大的,这 : 个比上个方法好些。 : 仅供讨论,毕竟没有仔细想,和写。
|
x*****0 发帖数: 452 | |
w******j 发帖数: 185 | |
s*******e 发帖数: 1630 | |
w******j 发帖数: 185 | |