Google PhraseRank: indicizzazione per frasi.

Phrase identification in an information retrieval system

I sistemi di IR finora usati dai più grandi motori di ricerca si sono sempre basati sull’acquisizione di contenuti e documenti di testo tramite algoritmi in grado di riconoscere i temi trattati da un documento usando le singole parole contenute: da un documento, eliminate le stopwords, si acquisiscono le parole che formano il documento e si classifica qust’ultimo in base alla rilevanza delle parole all’interno del testo.

Il processo non è assolutamente così semplice come l’ho descritto sopra, ma rende l’idea degli attuali processi per la ricerca e il recupero delle informazioni di un documento di testo in una grande collezione di documenti come il web.

Il gigante californiano di Mountain View, ultimamente, ha rilasciato una serie di 5 brevetti che potrebbero cambiare l’attuale sistema di information retrieval, cambiando così non solo il sistema di indicizzazione dei documenti, ma anche il sistema di ranking e di ordinamento dei risultati, un processo di IR che andrebbe a rivoluzionare l’attuale mondo SEO: l’indicizzazione per frasi.

Il primo brevetto di Google della serie si intitola Phrase identification in an information retrieval system.

Abstract

“Un sistema di IR che usa frasi per indicizzare, recuperare, organizzare e descrivere documenti. Le frasi identificate predicono la presenza di altre frasi nel documento. I documenti vengono indicizzati in accordo alle frasi che includono. Le frasi correlate e l’estensione delle frasi sono anch’esse definite. Frasi in una query sono identificate e usate per recuperare e valorizzare i documenti. Le frasi sono anche usate per raggruppare i documenti nei risultati delle ricerche, creare le descrizioni dei documenti ed eliminare documenti duplicati dai risultati e dall’indice.”

Di seguito leggiamo le traduzioni dei claims del brevetto:

1. Un metodo di selezione documenti in un insieme in risposta ad una query, che comprende: ricevimento della query, idenfitifcazione di una pluralità di frasi nella query, dove minimo una frase è formata da più parole, identificazione dell’estensione di almeno una delle frasi identificate, e selezione dei documenti dall’insieme di documenti che contengono almeno una frase dall’insieme includendo frasi nella query e nell’estensione della frase.

2. Il metodo chiamato al punto 1, dove la selezione dei documenti comprende: combinazione di una “posting list” di un frase identificata e una “posting list” dell’estensione della frase identificata per formare una “posting list” combinata; selezione dei documenti che appaiono nella “posting list” combinata e nelle“posting list”di altre frasi identificate.

3. Un metodo di selezione documenti in una raccolta di documenti in risposta ad una query, comprendendo: ricevimento della query, identificazione di una frase incompleta nella query, rimpiazzo della frase incompleta con l’estensione della frase e selezione documenti dalla raccolta contenente l’estensione della frase.

4. Il metodo chiamato al punto 3, dove l’identificazione della frase incompleta e il suo rimpiazzo comprende: identificazione di una frase candidata nella query, corrispondenza della frase candidata ad una frase incompleta in una lista di frase incomplete e rimpiazzo della frase
candidata con l’estensione della frase associata con la frase incompleta.

5. l metodo chiamato al punto 3, dove un estensione della frase di una frase incompleta comprende una super sequenza di frasi
incomplete che comincia con la frase incompleta.

6. Un metodo di selezione documenti in una raccolta in risposta ad una query, che comprenda: ricevimento di una query includendo la prima e la seconda frase, recupero della “posting list”dei documenti contenente la prima frase; per ogni documento nella lista: accesso alla lista indicando frasi correlate della prima frase che sono presenti nel documento, e sensible a reagire alla lista della frase correlata indicando che la seconda frase è presente in un documento, selezionando il documento da includere nel risultato di una query, senza richiamare una “posting list”di documenti contenenti la seconda frase.

7. Il metodo chiamato al punto 6, comprendente inoltre: sensibile a reagire alla lista delle frasi correlate che indicano che la seconda frase non è presente in un documento, escludendo il documento dai risultati della query, senza recuperare una “posting list”di documenti contenenti la seconda frase.

8. Il metodo chiamato al punto 6, comprendente: in risposta alla lista delle frasi correlate indicando che la seconda frase non è una frase correlata alla prima, intersecando la “posting list”dei documenti per la prima frase e con una “posting list” di documenti per la seconda frase per selezionare i documenti contenenti sia la prima che la seconda frase.

9. Il metodo chiamato al punto 6, comprendente inoltre: archiviazione delle liste di frasi correlate per una prima frase in rispetto ad un documento in un vettore di bit, dove un bit del vettore è regolato per ogni frase correlata alla prima frase che è presente nel documento, e un bit del vettore è rimosso per ogni frase correlata alla prima frase che non è presente nel documento, dove il vettore di bit ha un valore numerico, e valorizzando il documento selezionato determinando un valore adattato del vettore in accordo con l’insieme di bit per le frasi correlate alla prima frase che sono presenti nel documento.

10. Un metodo di ordinamento dei documenti inclusi nei in un risultato di una ricerca in risposta ad una query, dove la query comprende minimo una frase di ricerca, comprendendo: per ogni documento nel risultato di ricerca, accedendo al vettore di frase correlate per una frase di ricerca, dove in ogni bit del vettore è indicata la presenza, o l’assenza, di una frase correlata alla frase di ricerca; e ordinando i documenti nei risultati delle ricerche con il valore del loro vettore di frasi correlate, in modo che il documento con il più alto valore del vettore di frasi correlate è ordinato più in alto nei risultati delle ricerche.

11. Il metodo del punto 10, dove ogni bit del vettore di frasi correlate è associato con un frase correlata della frase di ricerca; e i bit sono ordinati cosicchè il più significativo bit del vettore è associato con una frase correlata avendo una più estesa informazione guadagnata in rispetto alla frase di ricerca, e il bit meno significativo è associato con una frase correlata avendo la minore informazione appresa in rispetto alla frase di ricerca.

12. Un metodo di ordinamento dei documenti inclusi nei risultati di ricerca in risposta ad una query, dove la query comprende al meno una frase di ricerca: per ogni documento nel risultato di ricerca: accedendo al vettore di frasi correlate per una frase della query, dove in ogni bit del vettore è indicata la presenza o assenza di una frase correlata alla frase di ricerca; per ogni bit indicando la presenza di una frase correlata della frase di ricerca, aggiungendo un predeterminato numero di punti associati con il bit per valorizzare un documento, e ordinando i documenti nei risultati di ricerca tramite il loro punteggio.

13. Il metodo al punto 12, dove ogni bit del vettore di frasi correlate è associato con una frase correlata alla frase di ricerca; i bit sono ordinati cosicchè il bit più significativo del vettore è associato con una frase correlata avendo la più estesa informazione guadagnata in rispetto alla frase di ricerca, e il bit meno significativo associato con una frase correlata avendo la minore informazione guadagnata in rispetto alla frase di ricerca; e il predeterminato numero di punti è associato con ogni serie di bit dal maggior numero di punti associati con i bit più significativi fino al minor numero di punti
associati con il bit meno significativo.

14.Un metodo per fornire un sistema di ir: automaticamente identificando frasi valide in un insieme di documenti comprendendo una pluralità di documenti, dove le frasi valide contengono frasi con più parole; indicizzando i documenti in accordo con le frasi valide contenute nei documenti, ricevendo una query di ricerca; identificando frasi contenute nella query, selezionando documenti in accordo alle frasi identificate, e ordinando i documenti selezionati

Storia dell’invezione

[0009] I sistemi di IR, generalmente chiamati motori di ricerca, sono ora uno strumento essenziale per trovare informazioni su larga scala, diverse, e crescenti come Internet. Di solito, i motori di ricerca creano un indice che correla i documenti (o pagine) a parole individuali presenti in ogni documento. Un documento è recuperato in risposta ad una query contenente un certo numero di termini di ricerca, generalmente basato sull’avere alcuni dei termini di ricerca presenti nel documento. I documenti recuperati sono poi ordinati in accordo ad altre misure statistiche, come la frequenza di occorrenze dei termini di ricerca, il dominio, analisi dei link e simili. I documenti recuperati sono poi presentati agli utenti, tipicamente nel loro ordine valorizzato, e senza altri raggruppamenti o gerarchie imposte. In alcuni casi, una porzione selezionata di un testo di un documento è presentata per fornire all’utente una breve descrizione del contenuto del documento.

[0010] Dirette corrispondenze booleane dei termini di ricerca hanno ben note limitazioni, e in particolare non possono identificare documenti che non hanno i termini di ricerca, ma hanno parole correlate. Per esempio, in un tipico sistema booleano, una ricerca con “pastori australiani” non potrebbe fornire documenti su altre razze di cani come i Border Collies che non hanno l’esatto termine di ricerca. Anzi, tale sistema è similmente in grado di recuperare e valorizzare altamente i documenti circa l’Australia (che non hanno niente a che fare con i cani), e documenti in generale sui pastori.

[0011] Il problema è che i sistemi convenzionali indicizzano documenti basati su termini individuali, piuttosto che su concetti. I concetti sono spesso espresso in frasi, come “pastori australiani”, “presidente degli Stati Uniti” o “Sundance film festival”. Al meglio, alcuni sistemi indicizzeranno i documenti in rispetto a un predeterminato e molto limitato insieme di parole conosciute, che sono generalmente selezione da un operatore umano. L’indicizzazione di frasi è di solito evitata a causa delle richieste computazionali e di memoria per identificare tutte le possibili frasi con 3, 4, 5 o più parole. Per esempio, sull’assunto che ogni 5 parole possono costituire una frase, e un grande corpodi testo potrebbe avere al minimo 200.000 termini unici, ci sarebbero approssimativamente 3.2 per 10 alla 26 frasi possibili, chiaramente molto più che un sistema esistente potrebbe memorizzare o comunque manipulare in modo programmatico. Altro problema è che le frasi continuamente entrano ed escono dal lessico in termini del loro uso, molto più frequentemente che una nuova parola venga inventata. Nuove frasi vengono sempre generate, in campo tecnologico, artistico, legato ad eventi mondiali e legislativo. Altre frasi poi tendono a scomparire dall’uso comune nel tempo.

[0012] Alcune sistemi di IR esistenti cercano di provvedere al recupero di concetti usando modelli co-occorrenti di singole parole. In questi sistemi una ricerca su una parola, come “presidente” recupererà documenti che hanno altre parole che frequentemente compaiono in associazione a “presidente”, come “bianca” e “casa”. Mentre questo approccio può produrre dei risultati di ricerca avendo documenti che sono concettualmente correlati a livello di singole parole, questo non cattura di solito le relazioni in tema che sono inerenti fra co-occorenze di frasi.

[0013] In accordo a questo, c’è bisogno di un sistema di IR e di una metodologia che può comprensivamente identificare frasi su larga scala, indicizzare documenti in relazione a frasi, cercare ed ordinare documenti in accordo con le loro frasi, e fornire raggruppamenti addizionali e informazioni descrittive sui documenti.

Sommario del brevetto

[0014] Un sistema e una metodologia di IR che usa frasi per indicizzare, ricercare, ordinare e descrivere documenti in un insieme di documenti. Il sistema è adatto per identificare frasi che hanno sufficientemente frequenza e/o uso distinto in un insieme di documenti per indicare che esse sono “valide” o “buone” frasi. In questo modo frasi di più parole, per esempio frasi di 4, 5, o più termini, possono essere identificate. Questo evita il problema di identificare e indicizzare ogni possibile frase risultante da tutte le possibili sequenze di un dato numero di parole.

[0015] Il sistema è anche adatto per identificare frasi che sono correlate l’una all’altra, basandosi sull’abilitità di una frase di predire la presenza di un’altra frase nel documento. Più specificatamente, si usa una misura di predizione in relazione all’attuale grado di co-occorrenza di due frasi verso un aspettato grado di co-occorrenza delle due frasi. L’ottenimento dell’informazione, come la percentuale dell’attuale grado di co-occorrenza per aspettarsi il grado di co-occorrenza, è una misura di predizione. Due frasi sono correlate dove la misura di predizione supera una predeterminata soglia. In questo caso, la seconda frase ha un guadagno significativo dalle informazioni riguardo alla prima frase. Semanticamente, saranno frasi correlate quelle che sono comunemente usate per discutere e descrivere un dato tema o un concetto, come “presidente degli stati uniti” e “casa bianca“. Per una data frase, le frasi correlate possono essere ordinate in accordo alla loro rilevanza o significato basate sulle loro rispettive misure di predizione.

[0016] Un sistema di IR indicizza documenti in un insieme di documenti tramite la validità o la bontà delle frasi. Per ogni frase, una “posting list” identifica i documenti che contengono la frase. In più, per una data frase, una seconda lista, vettore, o altra struttura è usata per immagazzinare dati indicando quali delle frasi correlate di una data frase sono presenti in ogni documento contenendo la frase data . In questo modo, il sistema può prontamente identificare non solo quali documenti contengono quali frasi in risposta ad una query di ricerca, ma quali documenti contengono anche frasi che sono correlate alla frase di ricerca, e questo più similmente all’essere specifiche sui temi o concetti espressi nelle frasi di ricerca.

[0017] L’uso delle frasi e delle frasi correlate provvedono alla creazione e l’uso di clusters di frasi correlate, che rappresentano, semanticamente, significativi raggruppamenti di frasi. I clusters sono identificati dalle frasi correlate che hanno una misura di predizione molto alta fra tutte le frasi del cluster. I clusters possono essere usati per organizzare i risultati di una ricerca, inclusa la selezione di quali documenti da includere nei risultati della ricerca e il loro ordine, così come l’eliminazione di documenti dai risultati delle ricerche.

[0018] Il sistema di IR è anche adatto per usare le frasi quando ricerca i documenti in risposta ad una query. La query è processata per identificare ogni frase che è presente nella query, così come per rercuperare l’associata “posting list” per le frasi di ricerca, e le informazioni sulle frasi correlate. In più, in alcune istanze un utente può immettere una frase incompleta nella frase di ricerca, come “presidente degli“. Le frasi incomplete come questa possono essere identificate e rimpiazzate dall’estensione della frase, come “presidente degli stati uniti“. Questo aiuto assicura che più similmente le ricerche degli utenti vengono di fatto eseguite.

[0019] Le informazioni relative di frase possono anche essere usate dal sistema per identificare e selezionare quali documenti includere nei risultati delle ricerche. Le informazioni sulla frasi correlate indicano per una data frase in un dato documento, quali frasi correlate alla data frase sono presenti in un dato documento. Di conseguenza, per una query contenente due frasi di ricerca, la “posting list” per la prima frase di ricerca è processata per identificare documenti contenenti la prima frase, e poi l’informazioni relativa di frase è processata per identificare quali di questi documenti contiene anche la seconda frase di ricerca. Questi ulteriori documenti vengono inclusi nei risultati della ricerca. Questo elimina la necessità del sistema di processare separatamente la “posting list” della seconda frase di ricerca, fornendo tempi di ricerca più veloci. Giustamente, questo approccio può essere esteso ad ogni numero di frase in una query, limitando risorse computazionali e tempi.

[0020] Il sistema può essere poi adattato per usare la frase e l’informazione relativa di frase per ordinare i documenti in un insieme di risultati di ricerca. L’informazione relativa di frase di una data frase è preferibilmente immagazzinata in un formato, come un vettore di bit, che esprime il relativo significato di ogni frase correlata a una data frase. Per esempio, il vettore di frase correlato ha un bit per ogni frase correlata ad una data frase, e i bit sono ordinati in accordo alle misure di predizione per la frase correlata. I bit più significativi del vettore di frase correlato sono associati con le frasi correlate che hanno il valore più alto della misura di predizione, e il bit meno significativo è associato con la frase correlata che ha il valore più basso della misura. In questo modo, per un dato documento e una data frase, l’informazione relativa di frase può essere usata per valorizzare un documento. Il valore del vettore di bit può essere usato come valore del documento. In questo modo documenti che contengono un alto ordine di frasi correlate di una frase di ricerca sono più portati ad essere correlati alla query che quelli che hanno un basso ordine di frasi relative. Il valore del vettore di bit può essere usato anche come componente in una più complessa funzione di valorizzazione, e può essere pesato ulteriormente. I documenti possono essere ordinati in accordo con il loro loro valore.

[0021] L’informazione di frase può anche essere usata in un sistema di IR per personalizzare le ricerche per un utente. Un utente è modellato come una raccolta di frasi, per esempio, derivate da documenti che l’utente ha visionato (per esempio, visti sullo schermo, stampati, archiviati, etc). Più in particolare, dato un documento selezionato dall’utente, le relative frasi che sono presenti in questo documento, sono incluse in un modello o profilo dell’utente. Durante ricerche subsequenziali, le frasi nel “modello utente” sono usate per filtrare le frasi di una query di ricerca e per pesare il punteggio del documento dai documenti recuperati.

[0022] L’informazione di frase può anche essere usata in un sistema di IR per creare una descrizione di un documento, per esempio i documenti inclusi in un insieme di risultati di ricerca. Data una query di ricerca, il sistema identifica la frase presente nella query, insieme alle frasi ad essa correlate, e le la sua estensione. Per un dato documento, ogni frase di un documento ha un conto di quante frasi di ricerca, frasi correlate, ed estensioni sono presenti nella sentenza. Le frasi del documento possono essere ordinate da questi conti (singolarmente o in combinazione), e un certo numero delle frasi superiori di posto (esempio cinque frasi) sono selezionate per formare la descrizione del documento. La descrizione del documento può essere presentata all’utente quando un documento è incluso nei risultati delle ricerche, cosi che l’utente ottenga una migliore comprensione del documento, relativamente alla query.

[0023] Un perfezionamento ulteriore di questo processo di generazione delle descrizioni dei documenti permette al sistema di fornire descrizioni personalizzate, che riflettano l’interesse dell’utente. Come prima, un “modello utente” archivia informazioni identificando frasi correlate che sono di interesse per l’utente. Questo modello utente è intersecato con una lista di frasi correlate alle frasi di ricerca, per identificare sia frasi comuni sia gruppi. L’insieme comune è poi ordinato in accordo all’informazione relativa di frase. L’insieme risultante di frasi correlate è poi usato per ordinare le frasi di un documento secondo il numero di casi di queste frasi correlate presenti in ogni documento. Un numero di frasi che hanno il numero più alto di frasi comuni correlate è selezionato come descrizione personalizzata del documento.

[0024] Un sistema di IR può anche usare l’informazione di frase per identificare ed eliminare documenti duplicati, sia mentre indicizza l’insieme di documenti, o mentre processa una query di ricerca. Per un dato documento, ogni frase di un documento ha un conto di quante frasi correlate sono presenti nella frase. Le frasi del documento possono essere ordinate tramite questo conto, e un certo numero di frasi di posto superiore (esempio cinque frasi) sono selezionate per formare la descrizione del documento. Questa descrizione è poi archiviata in associazione al documento, per esempio come una stringa o un hash delle frasi. Durante l’indicizzazione, un nuovo documento trovato è processato nello stesso modo per generare la descrizione del documento. La nuova descrizione del documento può essere abbinata contro precedenti descrizioni, e se la corrispondenza viene trovata, allora il nuovo documento è duplicato. Similarmente, durante la preparazione dei risultati di una query di ricerca, i documenti nell’insieme dei risultati delle ricerche possono essere processati per eliminare duplicati.

I: descrizione del sistema

[0037] In riferimento alla fig.1, è mostrata l’architettura software di un sistema di ricerca incoporato 100 in accordo all’incorporazione della presente invenzione. In questo, il sistema include un sistema di indicizzazione 110, un sistema di ricerca 120, un sistema di presentazione 130 e un server front end 140.

[0038] Il sistema di indicizzazione 110 è responsabile dell’identificazione di frasi nei documenti, e dell’indicizzazione dei documenti in accordo con le loro frasi, accedendo a diversi siti web 190 e altri insiemi di documenti. Il server front end 140 riceve le query dall’utente di un client 170, e fornisce queste query al sistema di ricerca 120. Il sistema di ricerca 120 è responsabile della ricerca di documenti rilevanti per la query di ricerca (risultati di ricerca), includendo l’identificazione di ogni frase nella query di ricerca, e poi dell’ordinamento dei documenti nei risultati della ricerca usando la presenza di frasi per influenzare l’ordine di importanza. Il sistema di ricerca 120 fornisce i risultati di ricerca al sistema di presentazione 130. Il sistema di presentazione 130 è responsabile della modifica dei risultati di ricerca inclusa la rimozione di documenti duplicati, e della generazione di descrizioni in tema coi documenti, e fornisce i risultati di ricerca modificati al server front end 140, che fornisce i risultati al client 170. Il sistema 100 include un indice 150 che archivia le informazioni di indicizzazione pertinenti ai documenti, e un magazzino di frasi (dati) 160 che archivia le frasi, e le informazioni statistiche correlate.

[0039] Nel contesto di questa applicazione, i “documenti” rappresentano ogni tipo di media file che può essere indicizzato e recuperato dal motore di ricerca, inclusi documenti web, immagini, file multimediali, documenti di testo, pdf o altri. Un documento può avere una o più pagine, partizioni, segmenti o altri componenti, appropriatamente al suo contenuto e tipo. In maniera equivalente un documento può essere inteso come una “pagina“, come comunemente si usa per riferirsi ai documenti su Internet. Nessuna limitazione all’opportunità dell’invenzione è implicata dall’uso del termine generico “documenti”. Il sistema di ricerca 100 opera su un largo corpo di documenti, come Internet e il World Wide Web, ma può nello stesso modo essere usato in insiemi più limitati, come per l’insieme di documenti di una libreria o di una impresa privata. In entrambi i contesti, si valuteranno i documenti che sono generalmente distribuiti su diversi sistemi di computer e siti. Senza perdita di generalità allora, i documenti in generale, a meno del formato o della locazione (esempio quale sito web o database) sarà collettivamente corrisposto ad un corpo o ad una raccolta di documenti. Ogni documento ha associato un identificativo che identifica univocamente il documento; l’identificativo è di solito una URL, ma anche altri tipi (esempio numeri documenti) possono essere usati. In questa è assunto l’uso delle URL per l’identificazione dei documenti.

Il sistema di indicizzazione: parte I

[0041] In una incorporazione, il sistema di indicizzazione 110 fornisce tre funzioni primarie operative:

1. identificazione di frasi e frasi correlate,
2. indicizzazione di documenti con rispetto alle frasi,
3. generazione e mantenimento di una tassonomia basata sulle frasi.

Queste abilità valuteranno che il sistema di indicizzazione 110 compierà altre funzioni in supporto delle convenzionali funzioni di indicizzazione.

[0042] 1. L’dentificazione delle frasi

[0043] L’operazione di identificazione della frase del sistema di indicizzazione 110 identifica “buone” o “cattive” frasi nell’insieme di documenti che sono utili per indicizzare e ricercare documenti. In un certo aspetto, le buone frasi sono frasi che occorrono in più di una certa percentuale di documenti nell’insieme di documenti, e/o sono indicati avendo un’apparenza distinta in tali documenti, come delimitato dalle modifiche di tags altri morfologie, formattazione, o indicatori grammaticali. Un’altro aspetto delle buone frasi è che sono premonizioni di altre buone frasi, e non sono soltanto sequenze delle parole che compaiono nel lessico. Per esempio, la frase “presidente degli Stati Uniti” è una frase che predice altre frasi quali “George Bush” e “Bill Clinton“. Tuttavia, altre frasi non sono premonitrici, come “cadere dalle nuvole” o “fuori di testa” poiché gli idiomi e i modi di dire come questi tendono a comparire con molte altre frasi differenti e non correlate. Quindi, la fase dell’identificazione della frase determina quali frasi sono buone frasi e quale sono difettose (cioè, difettando nella potenza premonitrice).

[0044] In riferimento alla fig.1, il processo di identificazione della frase segue i seguenti passi funzionali:

[0045] 200: Raccolta delle possibili buone frasi, con frequenza e co-occorrenza statistica delle frasi.

[0046] 202: Classificazione delle frasi possibili sia come buone o difettose basate sulle statistiche di frequenza.

[0047] 204: Scremare la lista di buone frasi basandosi su una misura preventiva derivata dalle statistiche di co-occorrenza.

[0048] Ciascuna di queste fasi ora sarà descritta con ulteriori dettagli .

[0049] La prima fase 200 è un processo tramite cui il sistema di indicizzazione 110 indicizza un insieme di documenti in una raccolta di documenti, facendo ripetutepartizioni nella raccolta di documenti nel tempo. Una partizione è processata per il passaggio. Il numero di documenti recuperati per passaggio può variare, ed è preferibilmente circa 1.000.000 per partizione. Si preferisce che soltanto i documenti precedentemente non recuperati siano processati in ogni partizione, fino a che non siano processati tutti i documenti, o si incontrino alcuni altri criteri per la terminazione del processo. In pratica, il recupero continua poichè i nuovi documenti sono continuamente aggiunti alla raccolta di documenti. I seguenti passi sono presi dal sistema di indicizzazione 110 per ogni documento che è recuperato.

[0050] Attraversare le parole del documento con una lunghezza della finestra di frase di n, dove la n è una lunghezza massima voluta della frase. La lunghezza della finestra sarà tipicamente almeno 2 e preferibilmente 4 o 5 termini (parole). Le frasi includono preferibilmente tutte le parole nella finestra di frase, comprese quelle che in altri modi sarebbero considerato stop words, come “un” “il” e così via. Una finestra di frase può essere terminata da una conclusione della linea, un ritorno di paragrafo, un tag, o altri indizi di un cambiamento nel contenuto o formato.

[0051] La figura 2 illustra una parte di un documento 300 durante un attraversamento del processo di recupero, mostante la finestra di frase 302 che comincia alla parola “razza” e che si estende di 5 parole verso la destra. La prima parola nella finestra di frase 302 è la frase candidata i, e ciascuna delle sequenze i+1, i+2, i+3, i+4 e i+5 è similarmente una frase candidata. Quindi, in questo esempio, le frasi candidate sono: “razza“, “cani di razza“, “cani di razza per“, “cani di razza per“, “cani di razza per i baschi” e “cani di razza per i pastori baschi“.

[0052] In ogni finestra di frase 302, ogni frase candidata è controllata a sua volta per determinare se è già presente nella buona lista di frasi 208 o nella lista di frasi possibili 206 . Se la frase candidata non è presente sia nella buona lista 208 o nella lista possibile 206, allora la frase candidata è stata già determinata per essere “cattiva” eviene saltata.

[0053] Se la frase candidata è nella buona lista 208, come entrata g_j allora la voce di indice 150 per la frase g_j è aggiornata per includere il documento (per esempio, il relativo URL o altro identificativo del documento), per indicare che questa frase candidata g_j compare nel documento corrente. Un’entrata nell’indice 150 per una frase g_j (o un termine) è riferita come la “posting list” della frase g_j . La “posting list” include una lista dei documenti d (dai loro identitificativi, per esempio un numero di documento, o alternativamente un URL) in cui la frase si presenta.

[0054] In più, la matrice di co-occorrenze 212 è aggiornata, come ancora spiegato sotto. Nel primissimo passaggio, le buone e le cattive liste saranno vuote e così, la maggior parte delle frasi tenderanno ad essere aggiunte alla lista di frasi possibili 206.

[0055] Se la frase candidata non è nella buona lista 208 allora è aggiunta alla lista possibile 206, a meno che non sia già presente. Ogni entrata p sulla lista di frasi possibili 206 ha tre conteggi associati:

[0056] P(p): Numero di documenti su cui la frase possibile compare;

[0057] S(p): Numero di tutti i casi della frase possibile;

[0058] M(p): Numero di casi interessanti della frase possibile. Un caso di una frase possibile è “interessante” dove la frase possibile è distinta dal contenuto limitrofo nel documento tramite indicatori grammaticali o di formattazione, per esempio essendo in grassetto, o sottolineate, o come anchor text di un link, o tra virgolette. Queste (ed altre) distinzioni di apparenza sono indicate dalle varie modifiche fornite con i tag HTML e dagli indicatori grammaticali. Queste statistiche sono effettuate per una frase quando è disposta sulla buona lista 208.

[0059] In addizione alle varie liste, è mantenuta una matrice delle co-occorrenze 212 (G) per le buone frasi. La matrice G ha dimensioni m x m, dove m è il numero delle buone frasi. Ogni elemento G(j,k) nella matrice rappresenta un paio di buone frasi ( g_j , g_k ). La matrice 212 mantiene logicamente tre conti separati per ogni paio ( g_j , g_k ) di buone frasi in rispetto ad una finestra secondaria 304 che è incentrata sulla parola corrente i, e si estende di +/- h parole. In un esempio, come in fig.3, la finestra secondaria 304 è di 30 parole ( i+30, i-30 ). La matrice delle co-occorrenze 212 mantiene:

[0060] R(j,k) Conteggio delle righe co-occorrenti. Il numero delle volte che la frase g_j appare in un finestra secondaria 304 con la frase g_k.

[0061] D(j,k) Conteggio interessante disgiunto. Il numero delle volte che ogni frase g_j o g_k appare come testo distinto nella finestra secondaria.

[0062] C(j,k) Conteggio interessante congiunto. Il numero di volte che sia le frasi g_j che g_k appaiono come testo distinto nella finestra secondaria. L’uso di questo conteggio è particolarmente utile per evitare le circostanze dove la prase (ad esempio: nota di copyright) appare frequentemente nelle barre laterali, nel footer o nell’header, a questa non ha poteri di predizione di altro testo.

[0063] In riferimento all’esempio di fig.2, assumiamo che “cani di razza” è nella buona lista di frasi 208, così come le frase “pastore australiano” e “pastore australiano Club dell’America“. Entrambi queste frasi compaiono nella finestra secondaria 304 intorno alla frase corrente “cani di razza“. Comunque, la frase “pastore australiano Club dell’America” compare come anchor text di un link (indicato dalla sottolineatura) verso un sito web. Così il conteggio della riga co-occorrente per la coppia “cani di razza” “pastore australiano” viene incrementato, e il conteggio di riga e quello di interesse disgiunto per “cani di razza” “pastore australiano Club dell’America” sono entrambi incrementati visto che le frasi posteriori compaiono come testo distinto.