Forum Debian Users Gang

ethanak · 2014-08-13 14:24:03

Ja jak zwykle pewnie nie zadałem właściwego pytania do wujcia G - ale juz wymiękkam. Wszystkie artykuły na ten temat traktują o prefiksach IP, a ja po prostu potrzebuję algorytmu, który znajdzie mi najdłuższy początkowy substring w podanym napisie, pasujący do znanych substringów.
Czyli:

znane substringi to powiedzmy "a", "al", "ale", "alu".
aluminium pasuje do alu
aleja pasuje do ale
alona pasuje do al
acholera pasuje do a

Znanych prefiksów jest stosunkowo dużo (szacuję na dziś na kilkadziesiąt tysięcy ale o rząd wielkości mogę się mylić, czyli może być ich nieco więcej).

Jakiś pomysł?

Ostatnio edytowany przez ethanak (2014-08-13 18:29:07)

Piotr3ks · 2014-08-13 15:58:04

Poczytaj o drzewie Patricia. Inna nazwa drzewa z którą możesz się spotkać to "skompresowane drzewo trie".

ethanak · 2014-08-13 16:00:39

Dzięki - to chyba dokładnie to o co mi chodziło!
Dlaczego ja nie potrafię sam tego znaleźć? :(

Piotr3ks · 2014-08-13 16:11:46

Jeżeli chodzi o temat drzew to na polskich stronach ogólnie ciężko jest coś sensownego znaleźć. Trzeba szukać na zagranicznych forach/portalach. Myślę, że drzewo Patricia rozwiąże Twój problem - w dodatku ma niezłą złożoność.

ethanak · 2014-08-13 16:16:47

Dokładnie rozwiązuje - ja nie mam wstawiania/usuwania tylko wyszukiwanie, konstrukcja drzewa jest i tak w fazie kompilacji, a kawałek kodu w C to ja już swojem programistycznem wewnętrznem okiem widzę :)
Niestety - chyba takie głupie problemy samouków, że czasem potrzebne jest jakieś słowo które powiedział pan docent na wykładzie :(

Piotr3ks · 2014-08-13 16:46:35

Ogólnie warto się zapoznać z różnymi strukturami danych(kolejki priorytetowe, tablice haszujące, drzewa). Już nie raz mi tyłek ratowały :D Można wiele rzeczy zoptymalizować właśnie korzystając z tych struktur.

Z książek to mogę Tobie śmiało polecić:
Thomas Cormen - "Wprowadzenie do algorytmów"

ethanak · 2014-08-13 17:29:13

Akurat większość algorytmów (hm...większość o których wiem że istnieją...) znam i nie sprawia mi trudności implementacja (vide ostatni temat o kolorowych drzewach). Moim podręcznikiem był "Algorytmy i struktury danych" (przyznasz chyba, że sztandarowa pozycja, np. implementację drzew wyważonych robiłem jeszcze na Commodore 16), staram się być na bieżąco ze wszystkim - tylko tak jak powiedziałem, jeśli pan docent na wykładzie jakieś jedno słowo rzucił, to mogę zapamiętać albo nie, ale w razie czego sobie mogę przypomnieć. Niestety - jak nie było wykładu i docenta to człowiek jest w czarnej rzyci :(
A kilka ładnych lat siedzenia w usenecie nauczyło mnie prostej rzeczy - jak ci facet odpowiada jednym słowem to jest ono pewnie ważniejsze niż pięć stron wykładu wielce mądrych moderatorów różniastych forów o tym co ja powinienem wiedzieć i jaka dokumentację przeczytać :)
W każdym razie dziękuję - pewnie masz swój wkład w rozwoju Mileny :)

unsense · 2014-08-13 17:57:43

nie wiem ,rozmawiacie o drzewach , jestescie dendrologami. nie prosciej uzyc slowa ; graf , jak prawdziwy programista od grafow. :grafolog <:

Ostatnio edytowany przez unsense (2014-08-13 18:03:03)

ethanak · 2014-08-13 18:01:37

a drzewo nie jest grafem?
Ciekawe, ciekawe... od kiedy mianowicie?
BTW. ja jestem programistą od NLP a nie od dendrologii. O NLP możemy sobie pogadać.

Chociaż wątpię - nawet najdurniejszy programisty od NLP zna zasady typografii.

A tak przy okazji - pomieniatcziki przyleźli na duga???

Ostatnio edytowany przez ethanak (2014-08-13 18:13:51)

unsense · 2014-08-13 18:14:31

ethanak , bez nerw , WTF " programista od NLP" :" . a tu bym polemizowal . nie :"drzewo nie jest grafem?"
graf jest matematycznym symbolem . drzewo oczywiscie tez .ale sa inne idealizacje .graf to jest symbol wzgledny .na przyklad moje wyjscia i powroty ze sklepu po browara (zalozenie jest , nie wracam ta droga ktora doszedlem ) jakby wykreslil w przestrzeni (na powierzchni plaskiej) , za pomoca cyrkla i liniaju , tez bedzie graf. to tak w filozoficznym skrocie.

Ostatnio edytowany przez unsense (2014-08-13 18:16:17)

ethanak · 2014-08-13 18:18:27

Towariszcz pomieniatczik... drzewo jest to graf jednokierunkowy bez powtórzeń.
(o ile pamiętam definicję, bo to już chyba 20 lat minęło...)
BTW. ja znam skrót WTF - a Ty się naucz co to jest NLP.

Tak przy okazji... może ktoś zamknąć temat?

Ostatnio edytowany przez ethanak (2014-08-13 18:29:46)

unsense · 2014-08-13 19:05:42

" drzewo jest to graf jednokierunkowy bez powtórzeń." ., a tu sie znowu nie zgodze , i bede polemizowal.
widzial kolega kiedys drzewo ,. takie normalne w przyrodzie , jezeli ono sie rozrasta jednokierunkowo , to Boze miej nasz w Swej opiece . to blizej im do fraktali ( tym drzewom) .

Forum Debian Users Gang

Ogłoszenie

#1 2014-08-13 14:24:03

ethanak - Użytkownik

[SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#2 2014-08-13 15:58:04

Piotr3ks - Też człowiek :-)

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#3 2014-08-13 16:00:39

ethanak - Użytkownik

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#4 2014-08-13 16:11:46

Piotr3ks - Też człowiek :-)

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#5 2014-08-13 16:16:47

ethanak - Użytkownik

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#6 2014-08-13 16:46:35

Piotr3ks - Też człowiek :-)

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#7 2014-08-13 17:29:13

ethanak - Użytkownik

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#8 2014-08-13 17:57:43

unsense - Nowy użytkownik

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#9 2014-08-13 18:01:37

ethanak - Użytkownik

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#10 2014-08-13 18:14:31

unsense - Nowy użytkownik

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#11 2014-08-13 18:18:27

ethanak - Użytkownik

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

#12 2014-08-13 19:05:42

unsense - Nowy użytkownik

Re: [SOLVED] najdłuższy pasujący prefiks (string) - jakieś propozycje?

Stopka forum