WordSort

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
Ferooooo

WordSort

Příspěvek od Ferooooo »

Zdar

vedel by niekto ludsky, sedliacky, jednoducho vysvetlit wordsort? :) ten pseudokod mi hlavne v poslednej casti nedava zmysel a vobec to nevidim :/
ps
Matfyz(ák|ačka) level III
Příspěvky: 137
Registrován: 1. 6. 2006 08:47
Typ studia: Informatika Mgr.
Bydliště: Praha 4
Kontaktovat uživatele:

Re: WordSort

Příspěvek od ps »

Mě už Wordsort také začíná zajímat, když jdu zítra na zkoušku :) Také mi to není úplně jasné, i když to bude nějaký primitivní algoritmus, leč úmyslně zašifrovaný tak, aby studentům přetížil mozek.
Až dointegruju, chci do sběru
Uživatelský avatar
Tuetschek
Supermatfyz(ák|ačka)
Příspěvky: 657
Registrován: 15. 6. 2005 13:54
Typ studia: Nestuduji ale učím na MFF
Kontaktovat uživatele:

Re: WordSort

Příspěvek od Tuetschek »

No v podstate to neco takoveho je :P ... jde o normalni lexikograficke trideni, ktere ale na zmateni nepritele:

1. si slova nejdriv roztridi podle jejich delek
2. vytvori dvojice [poradi ve slove;pismeno] (napr. pro slovo ahoj vznikne [1,a], [2,h], [3,o], [4,j]) a ty setridi podle abecedy podle pismen
3. pak uz takto setrideny seznam jeste jednou setridi podle poradi (oboji je bucket-sortem, takze je to stabilni)
4. takto setridene dvojice rozdelim do mnozin (nazveme je Si) podle stejneho poradi pismene ve slove (napr. [1,a] a [1,d] jdou do stejne mnoziny, ale [2,a] do dalsi; de facto se jen odstrani duplicity)
5. zacne hlavni cyklus -- postupuju podle poradi pismenek ve slove, od konce (tj. kdyz nejdelsi tridene slovo ma delku 20, jdu od 20 k 1), kde v kazdem (i-tem) kroku:

I. rozdelim vsechna slova delky >= i do mnozin Tx podle i-teho pismena (tj. vsechna slova, ktera maji na i-tem miste stejne pismenko, padnou do stejne mnoziny), slova kratsi nez i pismen zatim neuvazuji
II. vyberu vsechny neprazdne mnoziny Tx (podle obsahu Si vim, ktere to jsou), a seradim je za sebe.
III. k vysledku pridam slova delky i-1 a jdu na dalsi krok (opet pouzivam k deleni podle i-teho pismena bucket-sort, takze je operace stabilni a zachovava poradi podle uz projitych kroku)

6. na konci vsechno setridim i podle prvniho pismene a dostanu spravne setridena slova

Takhle jsem to chapal ja, pred zkouskou koncem prosince ... tak ale nevim, jestli a jak moc to bylo spravne (k praktickemu overeni nedoslo :-P). Kdyztak to nekdo doplnte nebo opravte, urcite tu je spousta "proc", na ktery mozna nevim odpoved.
Plug 'n' Pray.
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: WordSort

Příspěvek od pasky »

Delalo mi vazne velke potize to odkudkoliv pochopit, nakonec jsem cast vycetl z Knutha (kde primo tenhle algoritmus neni) a zbytek pak nakonec sam vymyslel a namatchoval na popsane. Zkusil jsem to vysvetlit lidsteji na:

http://wiki.matfyz.cz/wiki/TIN066_P%C5% ... #Word_sort

Snad to bude srozumitelnejsi. Prijde mi, ze popisem toho preprocessingu na zacatku se cela idea hrozne zamlzi, kdyz je to pritom jen optimalizacni trik.
Next lecture on time travel will be held on previous Monday.
hellboy
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 5. 6. 2008 20:43
Typ studia: Informatika Mgr.

Re: WordSort

Příspěvek od hellboy »

No sakra, to je radost!

Nestacilo by kratsi slova doplnit nejakym dummy znakem ktery budu brat jako nejmensi? a setridit to pak normalne kyblikovanim?

A jinak podle wiki se mi nedaripochopit jak potom ten preprocessing z (poradi pismenka ve slove, pismenko) vyuziju.. Vzdyt ty slova jsou tim uplne rozsypany. Uvazuji spravne, ze by se to ev. dalo napravit, tim, ze z toho udelam trojici (poradi pismenka ve slove, pismenko, cislo slova) a na konci linearnim pruchodem pres ruzne prihradky postavit vystupni slova? (na slozitosti by to asi nic nemenilo, ale - je to tak mysleno? nebo to muzu vyuzit nejak fikaneji a elegantneji? )

Krom toho mi neni u Hybrid sortu o chlup vyse jasne proc "Jedno přidání do přihrádky velikosti Xi je O(1 + Xi log Xi)"; nemelo by to byt spis jenom (1 + log Xi) = nalezeni prihradky + mozne probublani na vrchol haldy..
A jestli je tomu tak, nevite kde se potom v odhadu celkovy slozitosti E ( SUM (1+ Xi * log Xi)) bere ta 1cka? protoze jestli je to za nalezeni tech prihradek tak by misto ni melo byt spis Xi, ne?
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: WordSort

Příspěvek od pasky »

hellboy píše:No sakra, to je radost!

Nestacilo by kratsi slova doplnit nejakym dummy znakem ktery budu brat jako nejmensi? a setridit to pak normalne kyblikovanim?
To by dopadlo stejne, jako kdybys proste vynechal ten preprocessing. Musel bys prochazet zbytecne spoustu prihradek navic a mel horsi slozitost, krom toho treba u skutecneho slovniku kde vetsina slov je kratka, ale nektere fakt dlouhe, by to asi nebyl zdaleka jen teoreticky problem.
A jinak podle wiki se mi nedaripochopit jak potom ten preprocessing z (poradi pismenka ve slove, pismenko) vyuziju.. Vzdyt ty slova jsou tim uplne rozsypany. Uvazuji spravne, ze by se to ev. dalo napravit, tim, ze z toho udelam trojici (poradi pismenka ve slove, pismenko, cislo slova) a na konci linearnim pruchodem pres ruzne prihradky postavit vystupni slova? (na slozitosti by to asi nic nemenilo, ale - je to tak mysleno? nebo to muzu vyuzit nejak fikaneji a elegantneji? )
Pozor, vysledek toho preprocessingu neni neco, nad cim pak delas dal to trideni. Ten preprocessing ti jen vytvori pomocnou tabulku, kterou si das stranou, a pouze ji vyuzijes na rychle iterovani po existujicich pismenkach v dane hloubce, na nic jineho! Samotna data na trideni tim preprocessingem vubec nejsou ovlivnena. Presne tohle puvodne zmatlo i mne. Jestli uz je to jasnejsi, prosim uprav to v te wiki, aby to z toho pochopil i nekdo jiny nez ja. :)
Krom toho mi neni u Hybrid sortu o chlup vyse jasne proc "Jedno přidání do přihrádky velikosti Xi je O(1 + Xi log Xi)"; nemelo by to byt spis jenom (1 + log Xi) = nalezeni prihradky + mozne probublani na vrchol haldy..
To je pekne zaludna otazka, priznam se, ze nevim, takhle je to v Koubkovi... Jestli na neco prijdes, bude to skvele.
A jestli je tomu tak, nevite kde se potom v odhadu celkovy slozitosti E ( SUM (1+ Xi * log Xi)) bere ta 1cka? protoze jestli je to za nalezeni tech prihradek tak by misto ni melo byt spis Xi, ne?
Jednu prihradku najdu v O(1), proste skocim na spravne misto pameti.
Next lecture on time travel will be held on previous Monday.
Jochanan
Matfyz(ák|ačka) level II
Příspěvky: 85
Registrován: 12. 5. 2007 15:58
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: WordSort

Příspěvek od Jochanan »

možná někomu pomůže kratší popis v angličtině, který jsem našel před zkouškou. I když je to prakticky to samé, co tam má koubek

Kód: Vybrat vše

string sort(L)
{
	make list of pairs (i,str[i])
	bucket sort pairs by str[i]
	bucket sort pairs by i (giving lists chars[i])
	bucket sort strings by length
	i = max length
	L = empty
	while (i > 0)
	{
	    concatenate strings of length = i before start of L
	    distribute into buckets by chars in position i
	    coalesce by concatenating buckets in chars[i]
	    i--
	}
	concatenate list of empty strings at start of L
	return L
}
kde:
coalesce = nechej srust / srustej
concatenate = spoj
peterblack
Matfyz(ák|ačka) level III
Příspěvky: 153
Registrován: 10. 12. 2006 19:26

Re: WordSort

Příspěvek od peterblack »

Tuetschek píše:No v podstate to neco takoveho je :P ... jde o normalni lexikograficke trideni, ktere ale na zmateni nepritele:

1. si slova nejdriv roztridi podle jejich delek
2. vytvori dvojice [poradi ve slove;pismeno] (napr. pro slovo ahoj vznikne [1,a], [2,h], [3,o], [4,j]) a ty setridi podle abecedy podle pismen
3. pak uz takto setrideny seznam jeste jednou setridi podle poradi (oboji je bucket-sortem, takze je to stabilni)
4. takto setridene dvojice rozdelim do mnozin (nazveme je Si) podle stejneho poradi pismene ve slove (napr. [1,a] a [1,d] jdou do stejne mnoziny, ale [2,a] do dalsi; de facto se jen odstrani duplicity)
5. zacne hlavni cyklus -- postupuju podle poradi pismenek ve slove, od konce (tj. kdyz nejdelsi tridene slovo ma delku 20, jdu od 20 k 1), kde v kazdem (i-tem) kroku:

I. rozdelim vsechna slova delky >= i do mnozin Tx podle i-teho pismena (tj. vsechna slova, ktera maji na i-tem miste stejne pismenko, padnou do stejne mnoziny), slova kratsi nez i pismen zatim neuvazuji
II. vyberu vsechny neprazdne mnoziny Tx (podle obsahu Si vim, ktere to jsou), a seradim je za sebe.
III. k vysledku pridam slova delky i-1 a jdu na dalsi krok (opet pouzivam k deleni podle i-teho pismena bucket-sort, takze je operace stabilni a zachovava poradi podle uz projitych kroku)

6. na konci vsechno setridim i podle prvniho pismene a dostanu spravne setridena slova

Takhle jsem to chapal ja, pred zkouskou koncem prosince ... tak ale nevim, jestli a jak moc to bylo spravne (k praktickemu overeni nedoslo :-P). Kdyztak to nekdo doplnte nebo opravte, urcite tu je spousta "proc", na ktery mozna nevim odpoved.
Vsechno je super vysvetleny ale tady mas podle me chybu, melo by tam byt:
II. Tx podle Si seradim je za sebe

jinak by tam bylo Si celkem k nicemu
Odpovědět

Zpět na „TIN066 Datové struktury I“