W dniu środa, 16 stycznia 2013 10:29:01 UTC+1 użytkownik M.M. napisał:
> 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;
>
> }
>

Ni do konca rozumiem niestaty co tu sie robi,
moze jakis komentarz szczegolowy? co to jest pattern?

nie wiem czy budowanie drzewa z pojedynczych liter czy bajtow (np w przypadku
indeksowani tresci robinsona kruzoe) mieloby jakies spore walory co do uzytecznosci
bo to drzewo byloby zaiste wielkie tj 'roztyte' (jak ja ostatnio bo pysk mi
ostatnio nieststy utył)
Pewnie mozna takie drzewo zbudowac ale byloby bolaste - zapewne kilka (iles) razy
wieksze od oryginalnego pliku, no i trzebe by przebudowywac przy zmianach (ogolnie np

obrabianie 100 k oryginalnych danych i np 900k
indeksu nie wydaje sie zbyt praktyczne),
ale w pewnych przypadkach jak moze przy kompresji itp moze sie przydac - nie wiem
nie interesowalem sie tym :/