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) .

Time (s)	Query
0.00017	SET CHARSET latin2
0.00007	SET NAMES latin2
0.00136	SELECT u., g., o.logged FROM punbb_users AS u INNER JOIN punbb_groups AS g ON u.group_id=g.g_id LEFT JOIN punbb_online AS o ON o.ident='3.137.217.163' WHERE u.id=1
0.00127	UPDATE punbb_online SET logged=1716115988 WHERE ident='3.137.217.163'
0.00054	SELECT * FROM punbb_online WHERE logged<1716115688
0.00111	SELECT t.subject, t.closed, t.num_replies, t.sticky, f.id AS forum_id, f.forum_name, f.moderators, fp.post_replies, 0 FROM punbb_topics AS t INNER JOIN punbb_forums AS f ON f.id=t.forum_id LEFT JOIN punbb_forum_perms AS fp ON (fp.forum_id=f.id AND fp.group_id=3) WHERE (fp.read_forum IS NULL OR fp.read_forum=1) AND t.id=26255 AND t.moved_to IS NULL
0.00008	SELECT search_for, replace_with FROM punbb_censoring
0.00266	SELECT u.email, u.title, u.url, u.location, u.use_avatar, u.signature, u.email_setting, u.num_posts, u.registered, u.admin_note, p.id, p.poster AS username, p.poster_id, p.poster_ip, p.poster_email, p.message, p.hide_smilies, p.posted, p.edited, p.edited_by, g.g_id, g.g_user_title, o.user_id AS is_online FROM punbb_posts AS p INNER JOIN punbb_users AS u ON u.id=p.poster_id INNER JOIN punbb_groups AS g ON g.g_id=u.group_id LEFT JOIN punbb_online AS o ON (o.user_id=u.id AND o.user_id!=1 AND o.idle=0) WHERE p.topic_id=26255 ORDER BY p.id LIMIT 0,25
0.00126	UPDATE punbb_topics SET num_views=num_views+1 WHERE id=26255
Total query time: 0.00852 s

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

Informacje debugowania