一段短句去重代码

弄google 热榜，重复问题实在是太严重了。。。
比如：http://www.google.cn/rebang/clip?bid=12000000&length=8&num=15

 

写了一段代码，用于去重：

'''
输入字符串数组，return 去重后的数组
implement in 1 hour..
'''
def duplicate_detection(list):
    dict = []
    for str in list:
        for char in str:
            if char not in dict:
                dict.append(char)
    def exist(str ,char): 
        if str.find(char) != -1:
            return 1
        return 0
    vec_cache = {}
    '''把str转换为向量'''
    def str2vec(str):
        if str not in vec_cache:
            vec_cache[str] = [exist(str, char) for char in dict]
            #print str, '->', vec_cache[str]
        return vec_cache[str]
    
    def cos(str1, str2):
        v1 = str2vec(str1)
        v2 = str2vec(str2)
        rst = 0
        for i in range(0, len(v1)):
            rst += v1[i] * v2[i]
        return rst#相同字符的个数
    threshold = 3
    rst = []
    for str in list :
        if all(cos(str,tmp)< threshold for tmp in rst):
            rst.append(str)
    return rst

def main():
    print duplicate_detection([
            'abc',
            'abcd',
            'def'
            ])
    list = u'''
邓丽欣6分钟视频
邓丽欣视频下载
邓丽欣6分钟
邓丽欣六分钟
都市猎人
林秀琴 失业
林秀琴失业
邓丽欣图片
邓丽欣
邓丽欣下载
邓丽欣 下载
一后三王
'''.split('\n')
    for rst in duplicate_detection(list):
        print rst
if __name__ == "__main__":
    main() 

输出：

邓丽欣6分钟视频
都市猎人
林秀琴 失业
一后三王

 

效果不错噢


google 为啥自己不做去重呢。。。。。

评论

4 楼 amu_lucifer 2011-01-20  

不是那么简单的划定一条线就能去重的。。要考虑的问题多了去了。。。。
比如分词，等等
'''
邓丽欣6分钟视频
邓丽欣视频下载
邓丽欣6分钟
邓丽欣六分钟
都市猎人
林秀琴 失业
林秀琴失业
邓丽欣图片
邓丽欣
邓丽欣下载
邓丽欣 下载
一后三王
广都会市长装扮猎人
木秀于林，必将做琴
广都会市长装扮猎人
'''

你告诉我为什么最后两个不出来？难道你觉得是重复的？

当然，我这也只是提个建议，LZ的代码简单的过滤一下是可以

光就程序而言，
1，采用list关键字作为参数名？
2，效率不高


example：


class my_set(set):
    def __hash__(self):
        return hash(tuple(self))

def duplicate_detection(li): 
    str_set,res_list = my_set(),[]
    for s in li:
        temp_set = my_set(s)
        if not filter(lambda x:x.__and__(temp_set).__len__()>3,str_set):
            str_set.add(temp_set)
            res_list.append(s)
    return res_list
 
def main():
    list = u'''''
邓丽欣6分钟视频
邓丽欣视频下载
邓丽欣6分钟
邓丽欣六分钟
都市猎人
林秀琴 失业
林秀琴失业
邓丽欣图片
邓丽欣
邓丽欣下载
邓丽欣 下载
一后三王
广都会市长装扮猎人
木秀于林，必将做琴
'''.split('\n') 
    for rst in duplicate_detection(list): 
        print rst.encode("utf8") 
if __name__ == "__main__": 
    main() 




PS，说话言语间有得罪请莫怪。

3 楼 jamiesun 2010-05-13  

要去重复用set最好

2 楼 zwws 2010-04-28  

1. 收集所有的字符到一个列表(A)
2. 遍历项列表, 将"每个项的字符是否在A中存在"的结果以向量格式存至列表(B), 用于计算相同字符出现个数
3. 逐一对比, 将出现三次以下的项插入列表

你看cos的实现就好啦.

1 楼 fengzl 2010-03-12  

介绍下算法，这样看得更明白