La duplicazione dei contenuti e il filtro antiduplicazione di Google

Di seguito un accorpamento di vari pezzi che ho ritrovato in giro sulla duplicazione dei contenuti, datato 2006, ma che fa luce su quello che è un annoso problema che affligge i motori di ricerca.

La duplicazione dei contenuti

Uno dei problemi principali che i motori di ricerca si trovano ad affrontare riguarda la duplicazione dei contenuti.

La duplicazione di un documento, inteso come pagina web, file di testo o multimediale, può derivare da diverse situazioni che si possono riassumere in 2 macro categorie: la duplicazione di contenuti come tecnica black hat seo, al solo fine di ingannare il motore ed aumentare la propria posizione nelle serp, e la legittima ridistribuzione delle informazioni: basta pensare alle citazioni, ad una hot news, o alle licenze creative commons.

Google, in particolar modo, ha sviluppato un algoritmo per la determinazione di contenuti duplicati e simili, che sentiamo spesso nominare come “filtro antiduplicazione“: di seguito vengono riportate le traduzioni del brevetto di Google sulla duplicazione dei contenuti.

STORIA DELL’INVENZIONE 

La presente invenzione concerne il recupero e il management delle informazioniin generale. Più specificatamente, l’invenzione riguarda la scoperta, ed eventualmente la rimozione, di contenuti e informazioni dupicati o simili

A seguire il termine documenti potrebbe essere diversamente interpretato a potrebbe includere contenuti come pagine webfile di testo, file multimediali, strutture di link, etc. Così, il termine potrebbe notificare quando documenti simili sono rilevati, esatti documenti duplicati saranno rilevati come conseguenza.

Rilevare contenuti duplicati e simili ha molte potenziali applicazioni. Per esempio, i documenti duplicati o simili possono indicare infrazioni di copyright e plagi. Un importante applicazione di rilevazione di contenuti simili appartiene al contesto del recupero e dell’archiviazione delle informazioni.

Esistono efficienti tecniche per rilevare i documenti duplicati. Rilevando quando e se i documenti sono duplicati o simili è molto difficile, specialmente in grandi raccolte di documenti come il Web.

Le fonti per contenuti duplicati e simili sono introdotti nella sezione 1.2.1. I problemi che questi documenti duplicati o simili sollevano, sia per gli utenti finali che che per le entità che li assistono sono descritti in 1.2.2. Infine, nella sezione 1.2.3 vengono introdotte le tecniche usate per la rilevazione di documenti duplicati e simili tra grandi collezioni di documenti.

  • Fonti di duplicazione e documenti simili
  • Problemi sollevati da contenuti duplicati e simili
  • Tecniche conosciute per scoprire documenti duplicati e simili
  • Filtro antiduplicazione: indice dell’invezione

Fonti di duplicazione e documenti simili

Su Internet, il World Wide Web può includere gli stessi documenti duplicati in differenti forme e in differenti posti. (naturalmente, altri network, oppure sistemi “stand alone” possono avere documenti duplicati). Vediamo le fonti di queste duplicazioni.

Primo, alcuni documenti sono “specchiati” in differenti siti nel Web. Questo specchiare è usato per alleviare potenziali problemi quando tanti utenti cercano di accedere allo stesso documento nello stesso momento, e/o per minimizzare eventuali latenze del network (es. utilizzando copie cache di pagine web localmente) 

Secondo, alcuni documenti potrebbero averedifferenti versioni con differenti formattazioni. Per esempio, un dato documento può avere un “piano di testo” e una versione HTML cosacche gli utenti possono visualizzare o scaricare il contenuto nella forma che preferiscono. Così come sempre più differenti
strumenti (PC, cellulari, etc) sono usati per accedere a Internet, un dato
documento può avere differenti versioni con differenti formattazioni per ogni formato (solo testo, testo più media, etc).

Terzo, i documenti sono spesso “prepended” o allegati con informazioni circa la loro locazione nel Web, la data, la data di ultima modifica, la versione, il titolo, il percorso gerarchico di classificazione (es. una pagina Web può essere classificata sotto più categorie dello stesso sito Web), etc. Esempio illustrato nella sezione 4.4 (figs13). 

Quarto, in alcuni casi un nuovo documento viene generato
da un documento esistente usando consistenti rimpiazzi di parole.
 Per esempio, un sito Web può presentare
diversi “brand” per differenti utenti cambiando soltanto determinate parole.Infine, alcune pagine Web aggregano o incorporano contenuti da altre fonti sul Web.

Problemi sollevati da contenuti duplicati e simili

Duplicati e documenti simili sollevano potenziali problemi sia per le persone che accedono all’informazione (es. dal Web) sia per le entità che aiutano le persone ad accedere alle informazioni desiderate (es. i motori di ricerca). Vediamo questi problemi.

Sebbene la gente continua a usare i computers per entrare, manipolare e immagazzinare informazioni, in visione dello sviluppo dell’immagazzinamento dei dati, dello sviluppo di Internet, e dei sistemi di link e collegamenti incrociati che riportano un informazione (es. usando collegamenti con link ipertestuali) le persone useranno i computer per accedere a una vastità di informazioni sempre
crescente.

I motori di ricerca sono stati sviluppati per aiutare gli utenti a trovare le informazioni desiderate. I motori di ricerca, tipicamente, cercano contentuti o “siti Web” archiviati conseguenti a una certa ricerca. In risposta a una determinata ricerca, viene proposta un lista ordinata in base al valore attribuito al documento, che tipicamente include brevi descrizioni del contenuto, così come collegamenti testuali (es. testi con associate URL) ai contenuti. Il sistema di ordinamento è tipicamente basato sulla corrispondenza delle parole cercate nella ricerca e le parole che appaiono nel contenuto.

Dal punto di vista degli utenti, documenti duplicati o simili sollevano problemi. Più specificatamente, quando gli utenti sottopongono una ricerca al motore, la maggior parte di loro non vuole collegamenti a pagine Web che hanno una grande ridondanza di informazioni. Per esempio, i motori di ricerca rispondono a una ricerca fornendo un gruppo di dieci risultati. Se sono fornite pagine con contenuti duplicati, molti tra i risultati di un gruppo potrebbero includere gli stessi contenuti. Da questo l’esigenza di una tecnica per evitare che il motore fornisca, come risultato di una ricerca, collegamenti a pagine Web che hanno contenuti duplicati.

La maggior parte dei motori di ricerca assolvono a tre funzioni principali:

  • esplorazione del Web
  • indicizzazione dei contenuti
  • rispondere a una data ricerca usando l’indice
    dei contenuti per generare i risultati.

Data l’enorme vastità di informazioni disponibili, queste 3 funzioni sono automatizzate a una grande estensione. Mentre l’operazione di esplorazione assocerà parole o frasi con un documento (es. una pagina Web), l’operazione di indicizzazione assocerà documenti (es. pagine Web) con parole o frasi. L’operazione di ricerca allora:

  • usa l’indice per trovare documenti (es. pagine Web) contenenti varie parole di un certa ricerca
  • valorizza e ordina i documenti trovati in accordo ad altre implementazioni

Ricordiamo che il Web può includere gli stessi documenti duplicati in differenti forme o in differenti posti nel Web. Per esempio, come introdotto in 1.2.1 sopra, i documenti possono essere “specchiati” in diversi siti nel Web, i documenti possono avere un numero di diversi formati cosi che gli utenti possano visualizzare o scaricare il contenuti nella forma che preferiscono, i documenti possono essere proposti in differenti versioni con diverse informazioni allegate, alcuni documenti possono essere stati generati da altri con un consistente cambiamento di parole, e alcuni documenti possono essere aggregati e incorporati da un’altra fonte nel Web. Potrebbe essere desiderabile eliminare questi documenti duplicati e questi simili.

A parte l’eliminazione di documenti duplicati e simili per andare incontro alle esigenze e alle aspettative degli utenti, l’eliminazione di documenti duplicati e simili è desiderabile dai motori di ricerca per:

  1. ridurre lo spazio richiesto (esempio per gli indici e le strutture di dati derivati dagli indici)
  2. ridurre le risorse necessarie per i processi di indicizzazione, ricerca, etc.

In visione di questi obiettivi sono necessarie diverse tecniche per scoprire (ed eliminare) documenti simili

Tecniche conosciute per scoprire documenti duplicati e simili

Alcune precedenti tecniche per scoprire documenti duplicati e simili implicano la generazione di alcuni elementi dei documenti chiamati “fingerprints” (impronte digitali) (esempio paragrafi, sentenze, parole o targhette, insegne (per esempio l’accavvallamento stirato di parole consecutive)).

Guardiamo per esempio gli articoli:

  • Z. Broder, “On the Resemblance and Containment of Documents,” Proceedings of Compression and Complexity of Sequences 1997, pp. 21-27, IEEE Computer Society (1988);
  • S. Brin et al., “Copy Detection Mechanisms for Digital Documents,” Proceedings of the ACM SIGMOD Annual Conference, San Jose 1995 (May 1995)

Alcuni o tutti i “fingerprints” possono essere usati per determinare documenti duplicati o simili. In maniera più specifica, due documenti potrebbero essere considerati simili se condividono più di un predeterminato numero (minimo due, generalmente piu’ alto) di “fingerprints”.

Per un grande insieme di documenti (per esempio i miliardi di documenti che vengono indicizzati dai motori di ricerca) questa determinazione diventa piuttosto costosa, sia letteralmente che in termini di spazio per l’archiviazione.

Guardiamo, per esempio, l’articolo:

  • M. Fang et al., “Computing Iceberg Queries Efficiently,” Proc. 24.sup.th Int’l. Conf. On Very Large Databases, pp. 299-310 (1998)

Il problema non è di facile soluzione. Per esempio, non è in special modo utile “pre-processare” le rappresentazioni di tali documenti usati nelle tecniche Broder per eliminare da ulteriori considerazioni, come la conoscenza dei “fingerprints”, per essere unica.

Questo perché tutti i documenti con “fingerprints” non unici (come i documenti rimasti dopo il pre-processamento) possono, tuttavia, avere documenti non simili. Questo necessita, quindi, di una migliore tecnica per la determinazione di documenti duplicati e simili.

Filtro antiduplicazione: indice dell’invezione

Il brevetto sul filtro anti duplicazione che vi presentiamo può determinare documenti simili da:

1) per ogni documento, generando i “fingerprints

2) determinando documenti simili basandosi sui “fingerprints”

In una incorporazione, i “fingerprints” possono essere pre-processati per eliminare quelli che occorrono solamente in un documento.

In un’altra, soltanto i rimanenti “fingerprints” potrebbero essere usati nella determinazione di documenti duplicati.

L’atto della generazione dei “fingerprints” per ogni documento può essere compiuto:

1) estraendo parti (come le parole) dai documenti,

2) hashing, ognuna di queste parti estratte per determinare quali da un pre-determinato numero di liste

3) per ognuna di queste liste, generando dei “fingerprints”


In risposta alla determinazione di documenti duplicati, la presente invenzione può funzionare anche per eliminare i documenti duplicati. 

La presente invenzione può funzionare per generare dei clusters di documenti simili, nei quali usare una proprietà transitiva. Ogni documento può avere un identificativo per l’identificazione del cluster al quale è associato. In questa alternativa, in risposta a una data ricerca, se due candidati risultano documenti dello stesso cluster e se i due candidati risultano documenti corrispondenti alla ricerca, solo quello dei due che è ritenuto più rilevante (per esempio da una alto valore di PageRank, oppure se è più recente) viene restituito dalla ricerca. 

Nel campo dei motori di ricerca, la presente invenzione può essere usata anche durante le attività di crawl per accelerarne il processo e alleggerire la banda disponibile non archiviando documenti simili, pagine o siti, come determinato dalla scoperta dei documenti durante un crawl precedente.