n******n
发帖数: 49 | 1 定义句子的相似度为：句子A和句子B的相同单词数/(句子A的单词数+句子B的单词数)
有一个文本，大小2G，约有1千万个句子，求相似度最高的10个句子对。要求效率最高。
大家有什么想法吗？ | j*****u
发帖数: 1133 | 2 the key is to build inverted index, otherwise it is O(N^2): N is #sentenses
if data can be put into memory in full(2G usually okay), build two hashtable
s when reading the file
ha: sentense -> list of words in the sentense
hb: word -> list of sentenses that contain this word
then:
foreach sentense s in ha
{
get related sentenses by iterating s.words and looking up in hb;
foreach (rs in related sentenses)
calculate similiary(s, rs);
}
finally sort and get top 10.
Complexity is reduced to O(N * avg(#related-sentenses))
If cannot put whole data into memory, this problem can be solved by MapReduc
e
It needs several iterations of map-reduce in order to calculate simularity(c
ertain data needs to be carried around during intermediate steps) and sort
高。
【在 n******n 的大作中提到】
: 定义句子的相似度为：句子A和句子B的相同单词数/(句子A的单词数+句子B的单词数)
: 有一个文本，大小2G，约有1千万个句子，求相似度最高的10个句子对。要求效率最高。
: 大家有什么想法吗？
| n******n
发帖数: 49 | 3 嗯 我也想到了inverted index. 但是具体做法 和你的有些不同。和jerryju的相比，
可能不能算个好算法。。。。 但是 还是贴出来 讨论
首先，如果给2个句子算相似度，我就把其中一个hash，对另一个句子进行遍历，看这
第二个句子当中有多少个词出现在第一个句子对应的hashset里面。
现在，如果是1千万个句子，
第一步，我就用个mapreduce统计每个词在整个文本中出现的次数，输出
frequency>这样的pair。把这些pairs中的前n个（比如前500位）定义为“高频词”。
第二步，统计每个句子当中高频词数，比如i am a programmer, i，am, a这三个词都
是高频词，那就认为这个句子中高频词数为3。
第三步，取所有句子中最高频和次高频的两个句子，按照公式计算相似度，把这个相似
度作为一个下限，等下第四步用这个下限对文本中的句子对进行排除。
第四步，因为我们知道相似度一定是小于min(句子a单词数，句子b单词数）/(句子a单
词数+句子b单词数),所以我们取所有可能的句子对，算min(句子a单词数，句子b单词数
）/(句子a单词数+句子b单词数),如果算出的值小于第三步中的下限，则排除这个句子
对，根本不需要进行相似度计算。
第五步，因为第四步已经排除了一些，所以第五步可以进行pair-wise的相似度计算，
用个最小堆或者sort，选出相似度最高的10对。
如果某些步骤数据不能直接放进memory, 就用map reduce。
sentenses
hashtable
【在 j*****u 的大作中提到】
: the key is to build inverted index, otherwise it is O(N^2): N is #sentenses
: if data can be put into memory in full(2G usually okay), build two hashtable
: s when reading the file
: ha: sentense -> list of words in the sentense
: hb: word -> list of sentenses that contain this word
: then:
: foreach sentense s in ha
: {
: get related sentenses by iterating s.words and looking up in hb;
: foreach (rs in related sentenses)
|
|
