W dniu środa, 16 stycznia 2013 09:29:22 UTC+1 użytkownik firr kenobi napisał:
> nie rozumiem, jak wogole wygladalo by
> takie indeksowanie np na przykladzie zaindeksowania 'robinsona cruzoe' (okolo
> 500kb)? robi sie cos w rodzaju slownika/mapy
> ze slowami i offsetami w pliku?

Też nie mam ani szczegółowej wiedzy, ani doświadczeń praktycznych z
tego typu algorytmami. Wyobrażam sobie to mniej/więcej w ten sposób...

Mamy tekst:
char text[M];

Mamy długość prefixa:
const int N = 6;

Mamy parę:
struct Pair {
unsigned int key; // suma-klucz
unsigned int pos; // pozycja w text.
Pair *next;
};

Mamy hash-table:
Pair *hash_table[S];

Mamy klucze, po jednym kluczu dla znaku alfabetu:
const unsigned int keys[256] = {rand,rand...rand};

Inicjujemy hash-table:
unsigned int key = 0;
for( int i=0 ; i<N ; i++ )
key ^= keys[ text[i] ];
for( int i=N ; i<M ; i++ ) {
Pair *pair = new Pair( key , i-N , NULL );
const unsigned int entry = key % S;
insert( pair , hash_table , entry );
key ^= text[i-N] ^ text[i];
}

Potem mamy wzorzec:
char pattern[N+R];

Liczymy klucz:
key = 0;
for( int i=0 ; i<N ; i++ )
key ^= keys[ pattern[i] ];

Liczymy punkt wejścia do hash-table:
entry = hash_table + key % S;
while( entry ) {
print( entry->pos ); // pozycje pod którymi może zaczynać się wyszukiwany tekst
enetry = entry->next;
}

Pozdrawiam