Szybkie i wydajne obliczenia na tablicach

Question

Chcę policzyć liczbę wystąpień dla określonej frazy w dokumencie. Na przykład "fora stackoverflow". Załóżmy, że D reprezentuje dokumenty ustawione z dokumentem zawierającym oba pojęcia.

Teraz załóżmy, że mam następującą strukturę danych:

A[numTerms][numMatchedDocuments][numOccurInADocument] 

gdzie numMatchedDocuments jest wielkość D i numOccurInADocument jest liczba wystąpień dany termin występuje w danym dokumencie, na przykład:

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

oznacza, termin "stackoverflow" występuje w dokumencie "document1", a jego pierwsze wystąpienie znajduje się na pozycji "3".

Następnie wybieram termin, który występuje co najmniej, i zapętla się na wszystkich jego pozycjach, aby sprawdzić, czy "forum" występuje na pozycji + 1 w bieżącym okresie "stackoverflow" pozycji. Innymi słowy, jeśli znajdę "forum" na pozycji 4, to jest to fraza i znalazłem dla niej dopasowanie.

dopasowanie jest proste dla każdego dokumentu i przebiega w miarę szybko, ale gdy liczba dokumentów przekracza 2 000 000, robi się bardzo wolno. Rozdzieliłem ją na rdzenie i oczywiście robi się to szybciej, ale zastanawiam się, czy algorytm ma lepszy sposób na zrobienie tego.

Dzięki,

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

Jak wspomniano w komentarzach, Suffix Array może rozwiązać tego typu problemu. Odpowiedziałem na podobne pytanie (Fastest way to search a list of names in C#) za pomocą prostej implementacji C# tablicy Suffix.

Podstawową ideą jest zestaw tablic indeksów wskazujących na indeks dokumentów i pozycję w tym dokumencie. Para indeksów reprezentuje ciąg rozpoczynający się w tym punkcie dokumentu i kontynuuje do końca dokumentu. Ale rzeczywiste dokumenty i ich zawartość istnieją tylko raz w oryginalnym sklepie. Wzorzec Suffix to tylko zestaw tych par indeksów, z parą dla każdej pozycji w każdym dokumencie. Następnie posortuj Wzmocnienie w kolejności, w jakiej wskazują one tekst. Po posortowaniu możesz teraz bardzo szybko znaleźć dowolną frazę spośród dowolnych dokumentów, wykonując proste wyszukiwanie binarne na tablicy przyrostków. Konstruowanie (głównie sortowanie) tablicy Suffix może być czasochłonne. Ale po skonstruowaniu jest bardzo szybki do wyszukiwania. Pamięć jest dość łatwa, ponieważ rzeczywista treść dokumentu istnieje tylko raz.

Byłoby trywialnie, aby rozszerzyć go do liczby powracających dopasowań fraz w obrębie każdego dokumentu.

To jest trochę inny niż klasyczny opis Suffix Array, gdzie zazwyczaj mówi się o Suffix Array działającym na jednym, bardzo dużym łańcuchu. Ale zmiany, które sprawiają, że działa dla tablicy łańcuchów/dokumentów, nie są tak duże, chociaż może zwiększyć ilość pamięci zużywanej przez macierz przyrostową w zależności od maksymalnej liczby dokumentów i maksymalnej długości dokumentu oraz sposobu kodowania pary indeksów.