2009-01-19 70 views
11

如果一個網頁與另一個網頁相同,有哪些技術可以用來檢測?如何確定兩個網頁是否相同?

通過同樣的,我的意思並不是焦炭換字符等效(這很容易),但強大到足以忽略類似網頁上的當前日期/時間等

例如,走了雅虎新聞文章加載頁面,10分鐘後在另一個瀏覽器中打開相同的頁面。巴林重寫,這些網頁會有一些差異(時間戳,可能是像廣告,可能像相關的故事),但一個人可以看看這兩個,並說他們是一樣的。

注意我沒有試圖修復(或依靠)URL規範化。即,弄清楚foo.html & foo.html?bar = bang是一樣的。

+0

到底發生了什麼? – RJHunter 2009-02-01 09:45:53

回答

11

這聽起來像是在用一種可靠的方法來衡量兩個頁面的相似度。

鑑於頁面結構不會發生太大變化,我們可以將問題減少到測試頁面上的文本是否大致相同。當然,有關攝影師頁面的the problems alluded to by nickf這種方法仍然存在,但如果您主要關注Yahoo!新聞或類似的應該沒問題。

要與頁面進行比較,可以使用機器學習中稱爲「字符串內核」的方法。這裏有一個早期的paper最近一套slides在一個R包和一個video lecture

非常粗略地說,一個字符串內核會查找多少個單詞,單詞對,三個單詞等兩個文檔的共同點。如果A和B是兩個文檔,k是一個字符串內核,那麼k(A,B)的值越高,這兩個文檔越相似。

如果你設置了一個閾值t,並且只說兩個文檔對於k(A,B)> t是相同的,那麼你應該有一個合理的好方法來做你想做的事情。當然,您必須調整閾值才能爲您的應用程序獲得最佳結果。

0

如果沒有您想要比較的網頁結構的詳細知識,那麼這可能非常棘手。也就是說,一臺機器應該如何告訴一個帶有幾張不同圖片的頁面是一樣的 - 如果它是一個帶廣告的新聞網站,那麼它應該是相同的,但如果它是一個攝影師的投資組合,那麼它肯定是不同的。

如果您確實知道頁面的結構,那麼我會做的是手動選擇頁面的各個部分(使用ID,CSS選擇器,XPath等)進行比較。例如,只比較頁面刷新之間的#content div。從那裏開始,您可能需要將容差級別添加到逐字符比較中。

實際上有一種類似的服務。它被稱爲Rsspect(由Qwantz fame的Ryan North編寫),它可以檢測任何網站的變化並創建一個RSS源,即使您不控制該頁面。

0

你可以生成每個人的MD5哈希,然後比較。就像你說的,很簡單。

您正在尋找的是一種用於比較兩個頁面的技術,這些頁面可以更改任意元素。這是一個難題。

  1. 確定頁面中哪些區域可以更改,而您不關心。小心!他們會一直四處走動。
  2. 哈希或做一些你關心的頁面部分的DOM的校驗和。小心!這些也將一直在改變。

你對抗屏幕抓取的第一條規則:頁面本質上是不穩定的。所以這是一個棘手的問題。您的解決方案將具有足夠的可靠性,可以解決您的源數據所面臨的各種細微變化,除非您也可以直接控制源頁面,並且可以針對此設計解決方案。

祝你好運!我曾經嘗試過解決這個問題的系統,這確實是一個難以解決的問題。

+0

散列只會讓你到目前爲止b/c這是一個二元差異;他們散列相同或不相等。鑑於上面提到的其他措施(餘弦相似度等)更精確地衡量*如何關閉頁面。處理網絡的東西,這可能是你想要的領域。 – 2009-01-19 03:04:04

0

這樣做的方法是不對整個頁面進行比較,因爲正如你所說的那樣,人類也不會被它欺騙。假設你對Yahoo!的新聞文章感興趣,頁面,那麼你應該看看新聞部分。然後你可以做任何事情,一個散列或新舊版本之間的字面比較。

2

我使用vgrep這種東西。

這是一個鮮爲人知的叫做visual-grep的工具,它依靠先進的技術,如sapient直觀設備和視覺皮層,可以快速確定頁面的相同性,並且它非常準確和高效(它應該因爲它已經發展了相當長的時間)。

在幽默警察今天不在的情況下標記社區維基:-)。

+1

幽默警察應該如此 - 爲你的這個笑話的跛腳投票;) – 2009-01-19 02:24:15

+0

+1。你的社區維基版太糟糕了。 =) – 2009-01-19 04:51:49

5

通過使用某種相似性度量,例如cosine similarity,您可以檢測到兩個頁面是相同的。然後,您必須定義一個可用於接受兩個文檔是否相同的最小閾值。例如,當應用餘弦測量時,我會選擇一個最接近1的值,因爲它的範圍從-1到完全不同,1爲相同。

0

我頭腦中的第一個想法是使用BeautifulSoup(Python)將頁面處理成XML文檔,對它們運行diff,並計算不同的行數。如果計數> X%,則不同。不是非常健壯,可能容易出錯,但這是我爲測試做的快速入侵。

你可能想看看這個網頁,其中討論比較兩個XML文檔:
http://www.ibm.com/developerworks/xml/library/x-diff/index.html

一個HTML文件可以強制與美麗的湯,然後用所列的技術相比的XML文檔。

1

您可以使用Web瀏覽器組件來呈現這兩個頁面的屏幕截圖,然後比較這些圖像。可能是最簡單的選擇。

0

我有類似的問題。我試圖爲用戶提交的鏈接目錄設計一個安全的鏈接系統。用戶將在博客或新聞網站上發佈頁面並將鏈接提交給索引。人會驗證鏈接是否合適,然後將頁面添加到索引中。

問題是想出一種方法來自動化檢查,確保鏈接隨着時間的推移仍然適用。例如,有人在幾周後修改了頁面並插入了種族歧視?新聞網站是否開始告訴人們你必須訂閱閱讀這個故事?

我最終提取了段落<p>元素並將緩存副本與當前單詞進行比較。簡單的說:

cached[] = { "Lorem", "Ipsum", "..." }; 
scanned[] = { "Lorem, "foo", ... }; 

之後,一系列的分揀機將在它的工作而忽略常用詞「如果能,但還是和」一邊用較重的治療換言之(髒話等)。

這導致了一個評分系統,除了少量的編輯和修改(拼寫錯誤,句子結構等)外,它們很快就會顯示是否需要再次檢查內容。然後返回分數,高於閾值的分數將被放入隊列中以供人重新驗證。

這也有助於解釋網站的重大變化。我不相信它會完全依靠自己來運作,但它在人類的一點幫助下確實做得很好。誠然,該系統的效率遠不及方法所能達到的效率。

2

根據你在做什麼,你可能會對TemplateMaker感興趣。你給它一些字符串(比如網頁),它標出了變化的位。您在Yahoo!新聞例如,您只需訪問一次網頁並告訴TemplateMaker學習它。然後你會再次獲取並告訴它學習一個。

當您很高興您的TemplateMaker每次都知道相同的內容時,您可以獲取另一個頁面並詢問TemplateMaker是否與其他模板匹配。 (它將給你已經改變,如果你有興趣的部分。)

0

您可以嘗試使用HTTP頭就像如果-Modified-Since的,或其他一些高速緩存相關的頭。此外,查看站點地圖文件可能會有所幫助,以瞭解搜索引擎需要多久檢查一次。

我的另一個嘗試(可能會聯合使用)將列出頁面上div s中的所有id s和class s。如果這些列表不匹配,那麼可能會有相當明顯的變化。否則,他們可能非常相似。

編輯:你也可以比較的img元素。

4

對於這類問題,我發現通過學術論文搜索要比問StackOverflow好得多,在處理具體問題時,專家們往往比人羣更聰明。

每個webcrawler或搜索引擎都有這個問題,並已解決它。使用基於內核的方法like the accepted answer is suggesting可能是一種很好的方法,但是您可能想從更簡單的已知可以正常運行的技術開始。之後您可以轉移到內核方法,並測試它們是否改善了結果。

最好的辦法是閱讀Henzinger's 2006 paper 'Finding near-duplicate web pages: a large scale evaluation of algorithms'

,你很可能會尋找產生拉賓指紋與'Fingerprinting by random polynomials' Rabin 1986的第一步。

0

我最近遇到這個問題,並在JavaScript解決方案在這裏工作: https://github.com/kennychua/pdiffy/

它可以讓你比較一個頁面(最好是無損PNG格式)的圖像,它會告訴你的圖像是不同的,如果是這樣,它將突出顯示差異。

它也有能力忽略你描述的時間戳問題等領域