一段短句去重代码

弄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 为啥自己不做去重呢。。。。。

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

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

你看cos的实现就好啦.

要去重复用set最好

不是那么简单的划定一条线就能去重的。。要考虑的问题多了去了。。。。
比如分词，等等
'''
邓丽欣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，说话言语间有得罪请莫怪。