W dniu środa, 9 stycznia 2013 21:55:13 UTC+1 użytkownik M.M. napisał:
> Po drugie, być może potrzebujesz wiele razy wyszukiwać różny wzorzec w
> tym samym tekście - wtedy warto zastanowić się nad jakimś zahashowaniem
> par (suma,pozycja w tekscie).

Do takich rzeczy używa się drzew sufiksowych.

w.

do góry

W dniu piątek, 11 stycznia 2013 23:12:26 UTC+1 użytkownik Wojciech Muła napisał:
> W dniu środa, 9 stycznia 2013 21:55:13 UTC+1 użytkownik M.M. napisał:
> > Po drugie, być może potrzebujesz wiele razy wyszukiwać różny wzorzec w
> > tym samym tekście - wtedy warto zastanowić się nad jakimś zahashowaniem
> > par (suma,pozycja w tekscie).
> Do takich rzeczy używa się drzew sufiksowych.
Jakie to ma zalety względem hash-table?
Pozdrawiam

do góry

W dniu sobota, 12 stycznia 2013 11:05:05 UTC+1 użytkownik M.M. napisał:
> W dniu piątek, 11 stycznia 2013 23:12:26 UTC+1 użytkownik Wojciech Muła napisał:
>
> > W dniu środa, 9 stycznia 2013 21:55:13 UTC+1 użytkownik M.M. napisał:
>
> > > Po drugie, być może potrzebujesz wiele razy wyszukiwać różny wzorzec w
> > > tym samym tekście - wtedy warto zastanowić się nad jakimś zahashowaniem
> > > par (suma,pozycja w tekscie).
>
> > Do takich rzeczy używa się drzew sufiksowych.
>
> Jakie to ma zalety względem hash-table?

Drzewo budujesz raz w czasie O(n). Następnie dowolny wzorzec o długości
m znajdujesz w czasie O(m), a wszystkie jego k wystąpień w czasie
O(k + m).

w.

do góry

W dniu sobota, 12 stycznia 2013 14:19:26 UTC+1 użytkownik Wojciech Muła napisał:
> > Jakie to ma zalety względem hash-table?
>
>
> Drzewo budujesz raz w czasie O(n).
Hmmm, może coś mylę, ale wydaje mi się, że hash table buduje się
szybciej niz drzewo.

> Następnie dowolny wzorzec o długości m znajdujesz w czasie O(m),
W hash-batle w czsie m + ilość kolizji, nie wiem czy to jest
istotna wada hash-table względem drzewek.

> a wszystkie jego k wystąpień w czasie O(k + m).
W hash-table k + m + ilość kolizji.

Pozdrawiam

do góry

W dniu środa, 9 stycznia 2013 22:10:41 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-01-09 21:55, M.M. pisze:
>
> > W dniu poniedziałek, 7 stycznia 2013 17:44:25 UTC+1 użytkownik identyfikator:
20040501 napisał:
>
> >> zna Ktoś może jakiś cwany, to znaczy prosty algorytm wyszukiwania ciągu w
>
> >> ciągu?
>
> > Jakoś to się robiło taką sumę, którą można obliczać "przyrostowo", i jak
>
> > suma dla wzorca i podciągu była taka sama, to dopiero wtedy porównywało się
>
> > znak po znaku - szczegółów nie pamiętam w tej chwili.
>
>
>
> Algorytm karpa-rabina, już podany ;)
>
>
>

A moze ktos opisac wlasnymi slowami jak wygladalby taki dobry algorytm do
wyszukiwania
podciagu? Nie mam sily sie wglebiac w wiki a
temat ew moze ciekawy - przynajmniej na temat

fir (w trakcie ferii zimowych)

https://dl.dropbox.com/u/42887985/firr2.jpg

do góry

W dniu wtorek, 15 stycznia 2013 08:29:22 UTC+1 użytkownik firr kenobi napisał:
> A moze ktos opisac wlasnymi slowami jak wygladalby taki dobry
> algorytm do wyszukiwania.

Jeżeli trzeba wyszukać jeden raz, to nie wiem czy implementowanie
dobrego algorytmu ma w ogóle sens. Wczytanie tekstu z dysku lub
pobranie go z sieci trwa tak długo, że wyszukiwanie dowolnym, nawet
bardzo kiepskim algorytmem, raczej nie będzie wąskim gardłem.

Natomiast gdy trzeba wyszukiwać wiele razy, to wszystko jest kwestią
zbudowania dobrego indeksu. Jakbym musiał teraz taki indeks to bym
posłużył się jakimiś sumami, a następnie bym do hash-table wrzucił
pary (suma, pozycja w stringu).

Napisz w czystym C wersję na hash-table i na drzewie prefixowym,
zrobimy benchmark, a przy okazji czegoś się nauczymy.

Pozdrawiam

do góry

W dniu wtorek, 15 stycznia 2013 09:33:28 UTC+1 użytkownik M.M. napisał:
> W dniu wtorek, 15 stycznia 2013 08:29:22 UTC+1 użytkownik firr kenobi napisał:
>
> > A moze ktos opisac wlasnymi slowami jak wygladalby taki dobry
>
> > algorytm do wyszukiwania.
>
>
>
> Jeżeli trzeba wyszukać jeden raz, to nie wiem czy implementowanie
>
> dobrego algorytmu ma w ogóle sens. Wczytanie tekstu z dysku lub
>
> pobranie go z sieci trwa tak długo, że wyszukiwanie dowolnym, nawet
>
> bardzo kiepskim algorytmem, raczej nie będzie wąskim gardłem.
>
>
>
> Natomiast gdy trzeba wyszukiwać wiele razy, to wszystko jest kwestią
>
> zbudowania dobrego indeksu. Jakbym musiał teraz taki indeks to bym
>
> posłużył się jakimiś sumami, a następnie bym do hash-table wrzucił
>
> pary (suma, pozycja w stringu).
>
>
>
> Napisz w czystym C wersję na hash-table i na drzewie prefixowym,
>
> zrobimy benchmark, a przy okazji czegoś się nauczymy.
>

Nie wiem wlasnie do czego mogloby sie to przydac, ale ew moglbym miec kiedys ambicje
by napisac sobie wlasny edytor czy np disasembler (tak zeby dzialal z duzymi
tekstami) I wtedy może? (Poki co nic takiego nie pisałem)
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..

firr

(wogole ostatnio odechcialo mi sie kodowac, jest to zaprawde ciezka robota :\ no ale
coz
z wolna bedzie trzeba sie zbierac znowu do roboty :/)

do góry

> to indeksowanie byloby lepszym wyjsciem niz
> szybki algorytm wyszukiwania. :-? Za duzo
>

swoja droga np taki algorytm wyszukiwania w acrobet reader nie jest za szybki - pliki
po 5 czy 15 MB a na wyszukiwania sie czeka (o ile pamietam)

do góry

On 15.01.2013 12:39, firr kenobi wrote:
>> to indeksowanie byloby lepszym wyjsciem niz
>> szybki algorytm wyszukiwania. :-? Za duzo
>>
>
> swoja droga np taki algorytm wyszukiwania w acrobet reader nie jest za szybki -
pliki po 5 czy 15 MB a na wyszukiwania sie czeka (o ile pamietam)

A algorytm wyszukiwania w kpdf albo okular jest wyjątkowo szybki -
wyszukiwanie w standardzie C++ działa płynnie w trakcie pisania. To jest
pewnie różnica algorytmu naiwnego vs. algorytmu dedykowanego. (+ pewnie
jakieś cache danych tekstowych)

--
Pozdrawiam
Michoo

do góry

najpewniej wersja z ktora ja bym na poczatku kombinował to np cos takiego:
szukamy np ciagu "dafob gnozdyrr daf",
okolo 18 znakow - skaczemy wic co okolo
18 znakow jesli natrafiony znak nie nalezy
do podciagu (np 'x') to dalej jesli nalezy
to sprawdzamy przyległe itp - tym samym
dla dlugich ciagow mozna by przeskanowaywac
kilka razy szybiciej w optymistycznym
wypadku - nieststy trzebs ie troche pokombinowac - moze sa tez jakies lepsze pomysly

do góry