W dniu wtorek, 15 stycznia 2013 12:21:52 UTC+1 użytkownik firr kenobi napisał:
> NIe jestem przekonany czy gdybym chioial
> np napisac takie edytor ktory by mial sprawnie
> pomagac w edycji 100 megabajtowych plikow txt
> to indeksowanie byloby lepszym wyjsciem niz
> szybki algorytm wyszukiwania. :-? Za duzo
> tekstu do indeksowania pewnie..
To kolejny ciekawy i trudny aspekt tego i wielu innych
zadań programistycznych. Czy lepiej coś zaindeksować, czy
lepiej zostawić użytkownikowi więcej wolnej pamięci RAM?
Gdy pamięci zabraknie na indeks, to lepiej dać sobie
spokój, ale zwykle nie wiemy na jakim statystycznym
komputerze będzie odpalany nasz program.

Poza tym z indeksami jest drugi problem, chyba nie da się
efektywnie zaindeksować wzorców o różnych długościach, a w praktyce
rzadko kiedy chcemy wyszukiwać tekst o stałej długości.

W praktyce jest jeszcze gorszy problem, jak poniżej pisałeś,
w edytorach możemy mieć listę wierszy a nie ciąg znaków. Wiersze
mogą być alokowane dynamicznie, czyli każdy wiersz może
zaczynać się pod losowym adresem. Wąskim gardłem w wyszukiwaniu
może okazać się problem z cashowaniem takiej struktury danych i
żaden algorytm nie przyspieszy.

Kolejny problem - w praktyce często chcemy wyszukiwać krótkie podciągi, a
to może oznaczać że wyrafinowane algorytmy odpadną z powodu zbyt
dużego narzutu liniowego.

Pozdrawiam

do góry

W dniu wtorek, 15 stycznia 2013 20:18:24 UTC+1 użytkownik M.M. napisał:
> W dniu wtorek, 15 stycznia 2013 12:21:52 UTC+1 użytkownik firr kenobi napisał:
>
> > NIe jestem przekonany czy gdybym chioial
>
> > np napisac takie edytor ktory by mial sprawnie
>
> > pomagac w edycji 100 megabajtowych plikow txt
>
> > to indeksowanie byloby lepszym wyjsciem niz
>
> > szybki algorytm wyszukiwania. :-? Za duzo
>
> > tekstu do indeksowania pewnie..
>
> To kolejny ciekawy i trudny aspekt tego i wielu innych
>
> zadań programistycznych. Czy lepiej coś zaindeksować, czy
>
> lepiej zostawić użytkownikowi więcej wolnej pamięci RAM?
>
> Gdy pamięci zabraknie na indeks, to lepiej dać sobie
>
> spokój, ale zwykle nie wiemy na jakim statystycznym
>
> komputerze będzie odpalany nasz program.
>
>
>
> Poza tym z indeksami jest drugi problem, chyba nie da się
>
> efektywnie zaindeksować wzorców o różnych długościach, a w praktyce
>
> rzadko kiedy chcemy wyszukiwać tekst o stałej długości.
>
>
>
> W praktyce jest jeszcze gorszy problem, jak poniżej pisałeś,
>
> w edytorach możemy mieć listę wierszy a nie ciąg znaków. Wiersze
>
> mogą być alokowane dynamicznie, czyli każdy wiersz może
>
> zaczynać się pod losowym adresem. Wąskim gardłem w wyszukiwaniu
>
> może okazać się problem z cashowaniem takiej struktury danych i
>
> żaden algorytm nie przyspieszy.
>
>
>
> Kolejny problem - w praktyce często chcemy wyszukiwać krótkie podciągi, a
>
> to może oznaczać że wyrafinowane algorytmy odpadną z powodu zbyt
>
> dużego narzutu liniowego.
>
>
W zyciu nic nie indeksowałem totez nie mam
wiekszego pojecia jak to sie robi, podejrzewam ze moze byc to problematyczne.
Co jesli np zindeksujesz wszystkie słowa 'kot'
w pliku
Przy edycji wszystkie indeksy (tj przynajmniej czesc indeksow) sie uniewaznia i
pewnie trzeba by je 'poprawiac' na biezaco itd

do góry

W dniu wtorek, 15 stycznia 2013 20:44:45 UTC+1 użytkownik firr kenobi napisał:
> Przy edycji wszystkie indeksy (tj przynajmniej czesc indeksow) sie
> uniewaznia i pewnie trzeba by je 'poprawiac' na biezaco itd
W przypadku indeksowania za pomocą hash-table to wydaje się proste.
Przy założeniu że podciąg ma długość N znaków, z pominięciem skrajnych
podciągów, każdy znak należy do N pociągów. Trzeba więc przed edycją
wyszukać N podciągów w hash-table, usunąć z niej wpisy, a po edycji
dodać wpisy nowe.

Bardziej martwi mnie to, że w praktyce chcemy wyszukiwać podciągi o
różnych długościach.

Pozdrawiam

do góry

W dniu wtorek, 15 stycznia 2013 21:08:34 UTC+1 użytkownik M.M. napisał:
> W dniu wtorek, 15 stycznia 2013 20:44:45 UTC+1 użytkownik firr kenobi napisał:
>
> > Przy edycji wszystkie indeksy (tj przynajmniej czesc indeksow) sie
>
> > uniewaznia i pewnie trzeba by je 'poprawiac' na biezaco itd
>
> W przypadku indeksowania za pomocą hash-table to wydaje się proste.
>
> Przy założeniu że podciąg ma długość N znaków, z pominięciem skrajnych
>
> podciągów, każdy znak należy do N pociągów. Trzeba więc przed edycją
>
> wyszukać N podciągów w hash-table, usunąć z niej wpisy, a po edycji
>
> dodać wpisy nowe.
>
>
>
> Bardziej martwi mnie to, że w praktyce chcemy wyszukiwać podciągi o
>
> różnych długościach.
>
>
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?

do góry

W dniu środa, 16 stycznia 2013 09:29:22 UTC+1 użytkownik firr kenobi napisał:
> W dniu wtorek, 15 stycznia 2013 21:08:34 UTC+1 użytkownik M.M. napisał:
>
> > W dniu wtorek, 15 stycznia 2013 20:44:45 UTC+1 użytkownik firr kenobi napisał:
>
> >
>
> > > Przy edycji wszystkie indeksy (tj przynajmniej czesc indeksow) sie
>
> >
>
> > > uniewaznia i pewnie trzeba by je 'poprawiac' na biezaco itd
>
> >
>
> > W przypadku indeksowania za pomocą hash-table to wydaje się proste.
>
> >
>
> > Przy założeniu że podciąg ma długość N znaków, z pominięciem skrajnych
>
> >
>
> > podciągów, każdy znak należy do N pociągów. Trzeba więc przed edycją
>
> >
>
> > wyszukać N podciągów w hash-table, usunąć z niej wpisy, a po edycji
>
> >
>
> > dodać wpisy nowe.
>
> >
>
> >
>
> >
>
> > Bardziej martwi mnie to, że w praktyce chcemy wyszukiwać podciągi o
>
> >
>
> > różnych długościach.
>
> >
>
> >
>
> 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?

wydawaloby sie ze zeby cos indeksowac to
same te tworzone 'linki' powinny byc
mniejsze niz zaindeksowane tresci, np jak masz
milion stron internetowych to ze mozna
zaindeksowac po 'tagach' ale gorzej po samej
tresci, jak np zaindeksujesz slowo kot
w internecie? nie wiem np jak google
to robi

do góry

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

do góry

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 :/

do góry

>
> for( int i=0 ; i<N ; i++ )
> key ^= keys[ text[i] ];
>


co tu sie w szczegolnosci robi?

do góry

W dniu środa, 16 stycznia 2013 15:43:24 UTC+1 użytkownik firr kenobi napisał:
> > for( int i=0 ; i<N ; i++ )
> > key ^= keys[ text[i] ];
> co tu sie w szczegolnosci robi?

Liczy się klucz zobrista. Taki klucz jest "odpory" a kolejność w
jakiej się nalicza składniki sumy, nie trzeba więc liczyć za każdym
razem całej sumy, a wystarczy tylko zrobić xor z ostatnim elementem i
następnym:
key ^= text[i-N] ^ text[i];

Taką samą zaletę ma zwykła suma (+) i mnożenie (*), jeżeli tylko nie
przepełni zakresów. Xor nie ma problemu z przepełnieniem.

Co do zapotrzebowania zasobów na indeks, to się zgadzam, w praktycznych
zastosowaniach może to stanowić problem.

A jak to robi google, to nie wiem. Ciekawe na czym w ogóle trzymają te
indeksy.

Pozdrawiam

do góry

W dniu środa, 16 stycznia 2013 19:36:51 UTC+1 użytkownik M.M. napisał:
> W dniu środa, 16 stycznia 2013 15:43:24 UTC+1 użytkownik firr kenobi napisał:
>
> > > for( int i=0 ; i<N ; i++ )
>
> > > key ^= keys[ text[i] ];
>
> > co tu sie w szczegolnosci robi?
>
>
>
> Liczy się klucz zobrista. Taki klucz jest "odpory" a kolejność w
>
> jakiej się nalicza składniki sumy, nie trzeba więc liczyć za każdym
>
> razem całej sumy, a wystarczy tylko zrobić xor z ostatnim elementem i
>
> następnym:
>
> key ^= text[i-N] ^ text[i];
>
>
>
> Taką samą zaletę ma zwykła suma (+) i mnożenie (*), jeżeli tylko nie
>
> przepełni zakresów. Xor nie ma problemu z przepełnieniem.
>
>
nadal tego nie rozumiem (ale zaznaczam ze
nigdy w zyciu nie zajmowalem sie hashowaniem
czy czyms takim bo ja bardziej na codzien zajmuje sie małym gamedevem itp)

co robi ten klucz? czy to identyfikator
danego slowa (chunka) z ktorego mozna pozniej
odtworzyc jego pozycje czy co to jest?



>
> Co do zapotrzebowania zasobów na indeks, to się zgadzam, w praktycznych
>
> zastosowaniach może to stanowić problem.
>
>
>
> A jak to robi google, to nie wiem. Ciekawe na czym w ogóle trzymają te
> indeksy.
>

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



>
>
> Pozdrawiam

do góry