W dniu czwartek, 22 listopada 2012 12:50:56 UTC-5 użytkownik slawek napisał:
> U�ytkownik "Roman W" <r...@g...com> napisa� w wiadomo�ci
>
> grup dyskusyjnych:48c54ee1-461c-46ed-9506-39a5220ef0b3@go
oglegroups.com...

>
> Jeszcze raz zadanko, jakby kto� zapomnia�: dany jest d�ugi ci�g N bajtowy
> (np. kilka-kilkana�cie GB), nale�y znale�� w nim najcz�ciej
wyst�puj�cy
> podci�g kolejnych M bajt�w (gdzie M jest np. 16), a dane mog� by� dowolnie
> z�o�liwie "spreparowane" (i to przez kogo�, kto b�dzie zna� nasz algorytm

> szukania). Podci�g�w M-bajtowych jest na tyle du�o, aby nie op�aca�o
siďż˝
> przechowywanie w pami�ci jaki� licznik�w czy czego� tam. Ci�g N bajtowy
jest
> dostatecznie d�ugi, aby chcie� go czyta� tylko jeden raz (i nie mie� w
> ca�o�ci w RAM).

Powiedz mi, czy dobrze kombinuje, nie chce mi sie pisac kodu.

Zalozmy na chwile, ze bajty to DNA - cztery wartosci, 0 1 2 3. Zbudujmy graf,
gdzie wierzcholkami sa mozliwe przejscia kolejnych "bajtow", czyli
ile jest w sumie przejsc od 0 do 1 itd. Idea jest taka, ze najczesciej
spotykana sekwencja ma swoje odwzorowanie w tym grafie.

I teraz mozemy zbudowac taki graf dla par bajtow "DNA", znowu zliczajac
przejscie od jednego wierzcholka do drugiego.

Nie wiem tylko jak z tego wyciagnac na koniec sekwencje ani do jakiej
maksymalnie "podciagow szukanego podciagu" da sie dojsc przy mozliwej pamieci,
ale tak czy inaczej da sie w ten sposob eliminowac rzadziej spotykane
sekwencje.

Dobrze kombinuje?

--
Edek