儿童版“意甲”开赛啦！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

儿童版“意甲”开赛啦！

儿童版“意甲”开赛啦！# Parenting - 为人父母

n*n2011-09-11 07:09

1 楼

定义句子的相似度为：句子A和句子B的相同单词数/(句子A的单词数+句子B的单词数)
有一个文本，大小2G，约有1千万个句子，求相似度最高的10个句子对。要求效率最高。
大家有什么想法吗？

D*W2011-09-11 07:09

2 楼

Aidan小同学平生才练过一次球，就全身披挂上阵，开踢了第一场足球比赛，还开场就
被教练安排在左边锋的位置上。小球员“无知者无惧”，无辜地站在他的中线边上等着
开球。倒是老妈很有自知之明地被吓得不轻，你知道那是谁的位置啊？梅西和小罗的啊！
哨声一响，红色和白色的小马蜂们就开始跟着那停不住的球前后涌动。Aidan同学很是
不满意球不听话，情急之下，把球抱起来摆摆正再踢... 好久没碰到球了，终于滚到
了眼前，看我给它一大脚 --- 坏了，方向错了... 教练白千叮万嘱了。好在我们学得
快，第一个quater 之后手再没用过，当卧底的事儿也再没沾边儿了。下半场换位置作
后卫，好像还挺有贡献，一个大脚一举瓦解了对方的攻击。
烈日炎炎之下四个quarter 不容易，不过主场4：0 的首场告捷还是让我们欢欣鼓舞。
不过好像是啦啦队的家长们更欢欣鼓舞，小朋友们大多筋疲力尽、一脸茫然。这不重要
，重要的是，小男生跟妈妈说要 "be tough"!

j*u2011-09-11 07:09

3 楼

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*n2011-09-11 07:09

4 楼

嗯我也想到了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)