W dniu czwartek, 17 stycznia 2013 18:16:30 UTC+1 użytkownik firr kenobi napisał:
> co robi ten klucz? czy to identyfikator
> danego slowa (chunka) z ktorego mozna pozniej
> odtworzyc jego pozycje czy co to jest?
W przybliżeniu tak, to jest coś w rodzaju id
słowa (albo początku słowa). Potem takie id
można łatwo/szybko znaleźć. Średnia ilość operacji
jakie trzeba wykonać jest równa średniej ilości
kolizji w hash-table, czyli może być stała, w zależości
od szczegółów nawet rzędu O(1). Nie należy mylić tego
z czasem stałym, wyszukiwanie w zwiększającej się
pamięci nigdy nie będzie stałe, choćby dlatego że
sygnał musi pokonać dłuższą trasę, aby odczytać dane
z coraz bardziej oddalonej od procesora kości RAM.

Mamy np. tekst do wyszukania:
const char pattern[] = "ala";

Mamy tablicę kluczy:
const unsigned int keys[256] = {rand,rand...rand};

Czyli klucz testu "ala" będzie:
unsigned int key = keys[ 'a' ] ^ keys[ 'l' ] ^ keys[ 'a' ];

Potem mamy tekst który przeszukujemy:
const char text[] = "asalam";

Dla tego tekstu można policzyć kolejne klucze, dla kolejnych 3 zakowych
pod ciągów:

key0 = keys['a'] ^ keys['s'] ^ keys['a'];
key1 = keys['s'] ^ keys['a'] ^ keys['l'];
key2 = keys['a'] ^ keys['l'] ^ keys['a'];
key3 = keys['l'] ^ keys['a'] ^ keys['m'];

Klucz key2 jest tak samo liczony jak key, więc będzie miał taką
samą wartość, więc zostanie (szybko) odnaleziony w hash-table, więc
będziemy mieli pozycję równą 2 (licząc od zera), więc przeszukamy
tekst od pozycji dwa, więc zajdziemy tam pattern ala :D


> tez nie wiem ale z tego wynika ze z
> trzymaniem bolastego indeksu np wszystkich
> ciagow na miliardzie stron moglbybyc tem
> problem ze to byloby wieksze niz ten miliard
> stron - pewnie cos tam jest jedynie czesciowo poindeksowane
Trzymanie indeksu wiąże się z narzutem, ale czy istnieje
jakaś inna droga? Może jakiś lepszy indeks?

Pozdrawiam