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
|
