• [已通過]Shingle,Simhash算法網頁相似度計算原理以及python實現_SEO交流_SEO前線
    發現更大的SEO世界
     找回密碼
     注冊
    搜索
    »首頁»SEO培訓 SEO論壇 SEO交流 帖子
    发新帖
    kaurus,做靠譜的seo。    

    [已通過]Shingle,Simhash算法網頁相似度計算原理以及python實現

    常見的網頁去重算法有:
    I-Match算法
    Shingle算法
    SimHash算法
    Counting Bloom Filter算法
    其中Shingling、SimHash最被搜索引擎廣泛使用。

    Shingle算法
    第一步:特征抽取
    抽取多個特征詞彙,通過比較兩個特征集合實現文檔重查(Shingle算法)
    shingle-1-300x253.png

    Shingle算法:對長度L的文檔,每個N個漢字取一個Shingle,一共渠道L-N+1個Shingle

    第二步
    相似度计算和评价 Shingle算法的比较方法为记录完全一致的Shingle个数,然后除以两个文档总个数减去一致的Shingle个数,计算出的数值为“jaccard系数”
    shingle-2.jpg

    再通過jaccard系數量化相似度後,可通過此數值判斷是否相似,搜索引擎中達到0.2才能判斷爲相似

    Shingle的python實現:
    #encoding:utf-8
    #計算文檔相似性(shingle)

    import time
    start = time.time()

    class ShingLing(object):

        cut_step = 5  #切片字长
        text = []
        com_count = 0

        def __init__(self,text1,text2):
            self._cut(text1)
            self._cut(text2)

        def _cut(self,text):
            if len(text) < self.cut_step:
                return

            text = list(text)
            pice_list = []
            for i in range(len(text) - self.cut_step):
                pice = text[i:i + self.cut_step]
                pice_list.append(pice)
            re = {'pice':pice_list,'length':len(text)-self.cut_step}
            self.text.append(re)

        def com(self):
            pice1 = self.text[0]['pice']
            pice2 = self.text[1]['pice']

            for item in pice1:
                if item in pice2:
                    self.com_count += 1

            total_length = self.text[0]['length'] + self.text[1]['length']
            com_count = self.com_count*2
            return com_count/float(total_length)

    text1 = str(open('1.txt','r').read())
    text2 = str(open('2.txt','r').read())

    s = ShingLing(text1,text2)
    end = time.time()
    time = end-start

    print s.com()
    print '运行时间:' + str(time)

    Simhash算法
    Simhash是Google提出的一種用于網頁判重的hash算法。
    傳統的hash算法只負責將原始內容盡量均勻隨機地映射爲一個簽名值,原理上相當于僞隨機數産生算法。傳統hash算法産生的兩個簽名,如果相等,說明原始內容在一定概率下是相等的;如果不相等,除了說明原始內容不相等外,不再提供任何信息,因爲即使原始內容只相差一個字節,所産生的簽名也很可能差別極大。
    從這個意義上來說,要設計一個hash算法,對相似的內容産生的簽名也相近,是更爲艱難的任務,因爲它的簽名值除了提供原始內容是否相等的信息外,還能額外提供不相等的原始內容的差異程度的信息。
    Simhash具有两个“冲突的性质”: 1. 它是一个hash方法 2. 相似的文本具有相似的hash值,如果两个文本的simhash越接近,也就是汉明距离越小,文本就越相似。 因此海量文本中查重的任务转换位如何在海量simhash中快速确定是否存在汉明距离小的指纹。也就是:在n个f-bit的指纹中,查询汉明距离小于k的指纹。

    p8003522.jpg

    Simhash的python實現

    #coding=utf-8

    import time
    start = time.time()
    class simhash():
        def __init__(self, tokens='', hashbits=128):
            self.hashbits = hashbits
            self.hash = self.simhash(tokens)

        def __str__(self):
            return str(self.hash)

        def __long__(self):
            return long(self.hash)

        def __float__(self):
            return float(self.hash)

        def simhash(self, tokens):
            # Returns a Charikar simhash with appropriate bitlength
            v = [0]*self.hashbits

            for t in [self._string_hash(x) for x in tokens]:
                bitmask = 0
                for i in range(self.hashbits):
                    bitmask = 1 << i
                    if t & bitmask:
                        v += 1 #查看当前bit位是否为1,是的话则将该位+1
                    else:
                        v += -1 #否则得话,该位减1

            fingerprint = 0
            for i in range(self.hashbits):
                if v >= 0:
                    fingerprint += 1 << i
    #整個文檔的fingerprint爲最終各個位大于等于0的位的和
            return fingerprint

        def _string_hash(self, v):
            if v == "":
                return 0
            else:
                x = ord(v[0])<<7
                m = 1000003
                mask = 2**self.hashbits-1
                for c in v:
                    x = ((x*m)^ord(c)) & mask
                x ^= len(v)
                if x == -1:
                    x = -2
                return x

        def hamming_distance(self, other_hash):
            x = (self.hash ^ other_hash.hash) & ((1 << self.hashbits) - 1)
            tot = 0
            while x:
                tot += 1
                x &= x-1
            return tot

        def similarity(self, other_hash):
            a = float(self.hash)
            b = float(other_hash)
            if a>b: return b/a
            return a/b

    if __name__ == '__main__':

        s = str(open('1.txt','r').read())
        hash1 =simhash(s.split())

        s = str(open('2.txt','r').read())
        hash2 = simhash(s.split())

        print '%f%% percent similarity on hash' %(100*(hash1.similarity(hash2)))
        print hash1.hamming_distance(hash2),"bits differ out of", hash1.hashbits

    end = time.time()
    time = end - start
    print '运行时间:' + str(time)

    實際測試
    從網易新聞隨便找一篇文章做text1,然後用奶盤僞原創後在手動段落、短語錯位用做text2
    text1 = ”’
    新华网休斯敦4月30日电 美国得克萨斯州西部一座油田4月30日发生爆炸,造成2名工人死亡,另有9人受伤。
    據《休斯敦紀事報》網站報道,該油田所在地拉溫縣警方表示,工人們當時正在用重型設備更換一座油井的井口部件,由于壓力加大,突然發生爆炸。2名工人當場被炸死,另外9人受傷。
    警方說,油田地處偏僻的鄉村地區,通信條件不佳,因此現場其他詳情無法得知。
    近年來,包括得克薩斯州在內的美國一些地區的油氣行業一片興旺。在拉溫縣,許多新油田如雨後春筍般湧現。
    美國能源信息局近期公布的數據顯示,去年美國的石油産量達到日均740萬桶,其中,得克薩斯州占全美總産量的近35%。與此同時,得克薩斯州27家煉油廠的産能占全美煉油總量的29%。
    ”’
    text2 = ”’
    新华网休斯敦4月30日电 美国得克萨斯州西部一座油田4月30日发生爆炸,造成2名工人死亡,还有9人受伤。
    警方說,油田地處偏遠的村莊區域,通信條件欠安,因而現場其他概況無法得知。
    這些年,包含得克薩斯州在內的美國一些區域的油氣職業一片興隆。據《休斯敦紀事報》網站報導,該油田所在地拉溫縣警方表示,工大家當時正在用重型設備更換一座油井的井口部件,因爲壓力加大,俄然發生爆炸。
    2名工人當場被炸死,別的9人受傷。在拉溫縣,許多新油田如雨後春筍般出現。
    美國能源信息局近期公布的數據顯現,上一年美國的石油産值到達日均740萬桶,其間,得克薩斯州27家煉油廠的産能占全美煉油總量的29%。與此同時,得克薩斯州占全美總産值的近35%。
    ”’

    “原創”與“僞原創”測試後shingle值和simhash值分別如下:
    shingle-simhash-1.jpg

    由此可见,市面上一堆伪原创的东西压根不靠谱,这还是很粗糙的相似度判断 ……

    在從網易找另一篇新聞做text2,測試相似度
    new text2 = ”’
    近些年來,銀行固定收益類理財産品的收益率突破7%關口,主要在2013年明顯發生過兩回,分別是2013年6月末、12月末。
    21世紀經濟報道統計發現,與2013年情形相比,2014年超過7%收益的銀行理財呈現三大特點,首先是門檻高,2013年的産品認購起點多爲5萬元,而最近則在10萬元、30萬元和50萬元較爲普遍。
    其次2013年兩次高收益理財,發生的背景都是市場流動性緊張,因此它們期限較短,多在1-3個月以內。而上述的理財産品期限基本都在1年、2年時間;再者,2013年的産品發行銀行以股份行爲主,最近則以中小城商行、農商行爲主。
    事實上21世紀經濟報道統計,自2014年以來,銀行似乎更願意用收益較高的長期限理財産品,來鎖定投資者的資金。銀率網數據也證明這點,在一季度,投資期限大于六個月的中長期理財産品占發行總量的比例爲13.61%,環比上升16.56個百分點。
    投資期限在一年以上的人民幣理財産品總計發行273款,占人民幣理財産品發行總量的2.36%,環比上升60.59個百分點。
    相反,今年1月-2月,“寶寶”類貨基産品攀登上收益率的高峰,譬如表現最好的貨基産品7天年化收益率達7.51%,達到6%的比比皆是。當時1-3個月的理財産品平均收益率僅在5.54%。最近余額寶已經跌至5.0480%、微信理財通則是5.0270%,僅錢大掌櫃仍能保持在5.776%。
    ”’

    兩篇內容不想關的文檔相似度測試結果如下:
    shingle-simhash-2.jpg


    发表于 2014-5-26 18:35:58
    回複 收藏
    快速回複 返回頂部 返回列表