a**********2 发帖数: 340 | 1 两个文件A,B,每行存了一个sentence(可能会很长),文件B非常大
要你找出A里面每个sentence在B中出现的次数
我说用hash table,他就问我hash function怎么写,说这个句子可能很长
貌似他想要的是其他解法。 |
g*****k 发帖数: 623 | 2 bless
不用hash还真不知道该怎么做。直观上就是用hash啊。。。
【在 a**********2 的大作中提到】 : 两个文件A,B,每行存了一个sentence(可能会很长),文件B非常大 : 要你找出A里面每个sentence在B中出现的次数 : 我说用hash table,他就问我hash function怎么写,说这个句子可能很长 : 貌似他想要的是其他解法。
|
g**e 发帖数: 6127 | 3 他考的应该是怎么写hash function。如果句子很长,可以取一个segment做hashing。
类似Rabin–Karp
当然可能会有collision
【在 g*****k 的大作中提到】 : bless : 不用hash还真不知道该怎么做。直观上就是用hash啊。。。
|
g*****k 发帖数: 623 | 4 如果是考hash function,那么这个table size如何设定?
【在 g**e 的大作中提到】 : 他考的应该是怎么写hash function。如果句子很长,可以取一个segment做hashing。 : 类似Rabin–Karp : 当然可能会有collision
|
g**e 发帖数: 6127 | 5 hash table size = # of sentenses in file A
【在 g*****k 的大作中提到】 : 如果是考hash function,那么这个table size如何设定?
|
g*****k 发帖数: 623 | 6 题目说明B非常大,如果设定size是A的行数,那么collision太多了吧。
【在 g**e 的大作中提到】 : hash table size = # of sentenses in file A
|
r********t 发帖数: 395 | 7 bitmap..
【在 a**********2 的大作中提到】 : 两个文件A,B,每行存了一个sentence(可能会很长),文件B非常大 : 要你找出A里面每个sentence在B中出现的次数 : 我说用hash table,他就问我hash function怎么写,说这个句子可能很长 : 貌似他想要的是其他解法。
|
b**********r 发帖数: 91 | 8 Aho-corasick string pattern search
【在 a**********2 的大作中提到】 : 两个文件A,B,每行存了一个sentence(可能会很长),文件B非常大 : 要你找出A里面每个sentence在B中出现的次数 : 我说用hash table,他就问我hash function怎么写,说这个句子可能很长 : 貌似他想要的是其他解法。
|
m**q 发帖数: 189 | 9 把A的所有行放到trie中,遍历B时对每一行去lookup trie?
【在 a**********2 的大作中提到】 : 两个文件A,B,每行存了一个sentence(可能会很长),文件B非常大 : 要你找出A里面每个sentence在B中出现的次数 : 我说用hash table,他就问我hash function怎么写,说这个句子可能很长 : 貌似他想要的是其他解法。
|
b*****1 发帖数: 52 | 10 可以用double hash reduce collision , e.g., use different base in robin karp.
【在 g**e 的大作中提到】 : 他考的应该是怎么写hash function。如果句子很长,可以取一个segment做hashing。 : 类似Rabin–Karp : 当然可能会有collision
|