Calcolo veloce ed efficiente su array

Question

Desidero contare il numero di occorrenze per una frase particolare in un documento. Ad esempio "forum StackOverflow". Supponiamo che D rappresenti i documenti impostati con il documento che contiene entrambi i termini.

Ora, supponiamo di avere la seguente struttura dei dati:

A[numTerms][numMatchedDocuments][numOccurInADocument] 

dove numMatchedDocuments è la dimensione di D ed numOccurInADocument è il numero di occorrenze di un particolare termine si verifica in un particolare documento, ad esempio:

A[stackoverflow][document1][occurance1]=3; 

significa, il termine "stackoverflow" si verifica nel documento "document1" e la sua prima occorrenza è nella posizione "3".

Quindi seleziono il termine che si verifica meno e ricopro tutte le sue posizioni per trovare se "forum" si verifica in una posizione + 1 il termine corrente "stackoverflow" posizioni. In altre parole, se trovo "forum" nella posizione 4, questa è una frase e ho trovato una corrispondenza per questo.

la corrispondenza è semplice per documento e viene eseguita abbastanza velocemente ma quando il numero di documenti supera i 2.000.000 diventa molto lento. L'ho distribuito su core e ovviamente è più veloce, ma mi chiedo se c'è un modo algoritmicamente migliore per farlo.

grazie,

psudo-Code:

boolean docPhrase=true; 
int numOfTerms=2; 
// 0 for "stackoverflow" and 1 for "forums" 
for (int d=0;d<D.size();d++){ 
//D is a set containing the matched documents 
int minId=getTheLeastOccuringTerm(); 
for (int i=0; i<A[minId][d].length;i++){ // For every position for LeastOccuringTerm 
    for(int t=0;t<numOfTerms;t++){ // For every terms 
     int id=BinarySearch(A[t][d], A[minId][d][i] - minId + t); 
     if (id<0) docPhrase=false; 
    } 
} 
} 

Answer 1

Come ho già detto nei commenti, Suffix Array può risolvere questo tipo di problema. Ho risposto a una domanda simile (Fastest way to search a list of names in C#) con una semplice implementazione di # C# Suffix Array.

L'idea di base è avere una serie di coppie di indici che puntano a un indice di documento e una posizione all'interno di quel documento. La coppia di indici rappresenta la stringa che inizia in quel punto nel documento e continua fino alla fine del documento. Ma i documenti reali e il loro contenuto esistono solo una volta nel tuo negozio originale. Suffix Array è solo una matrice di queste coppie di indici, con una coppia per ogni posizione in ogni documento. Quindi ordinate la matrice suffisso nell'ordine in cui indicano il testo. Una volta ordinati, ora puoi trovare molto rapidamente qualsiasi frase tra i documenti eseguendo una semplice ricerca binaria sulla matrice di suffissi. Costruire (principalmente l'ordinamento) l'array Suffix può essere un lungo periodo di tempo. Ma una volta costruito, è molto veloce da cercare. È abbastanza facile sulla memoria poiché il contenuto del documento attuale esiste solo una volta.

Sarebbe banale estenderlo ai conteggi di restituzione di corrispondenze di frase all'interno di ciascun documento.

Questo è un po 'diverso rispetto alla descrizione classica di un Array Suffix in cui solitamente si parla del Suffix Array che opera su una singola stringa molto grande. Ma le modifiche per farlo funzionare per una serie di stringhe/documenti non è così grande, anche se può aumentare la quantità di memoria consumata dalla matrice Suffix a seconda del numero massimo di documenti e della lunghezza massima del documento, e di come si codifica la coppie di indici.