Perfectly Clustering Words / Dokonale se shlukující slova
| školitel: | prof. Ing. Edita Pelantová, CSc. |
| e-mail: | zobrazit e-mail |
| typ práce: | bakalářská práce |
| zaměření: | MI_MM, MINF |
| klíčová slova: | Burrows-Wheeler transformace, kódování výměny intervalů |
| popis: | Burrows-Wheelerova transforamce se využívá při bezztrátové kompresi dat. BWT vyrobí ze slova w nad abecedou 1,2,...,d slovo, kde sousedící písmena jsou často stejná. Slovo w se nazývá clustering, pokud BWT(w) je zřetězením d bloků stejných písmen. Clustering slovo w je navíc perfektní pokud první blok v BWT(w) je tvořen písmenem d, druhý písmenem d-1, atd. a poslední písmenem 1. Zná se přesný popis clustering slov nad binární abecedou - jsou to sturmovská slova. Nad víceprvkovou abecedou je otázka otevřená. Spojitost perfectly clustering slov se symetrickou výměnou d intervalů je ukázána v práci [2], v práci [1] je vyslovena domněnka o tom, že jistá třída ternárních slov je dokonale clustering. Cílem práce je seznámit se s BWT a jejím využitím [3], nastudovat vlastnosti slov kódujících výměnu intervalů a důkaz charakteristiky binárních perfectly clustering slov. Dále pak otestovat domněnku vyslovenou v práci [1] a v ideálním případě ji dokázat nebo vyvrátit. |
| literatura: | [1] M. Lapointe: Perfectly Clustering Words are Primitive Positive Elements of the Free, Group WORDS (2021) LNCS 12847. [2] S. Ferenczi, L. Zamboni: Clustering Words and Interval exchange, Journal of Integer Sequences, Vol. 16 (2013),Article 13.2.1 [3] G. Manzini: The Burrows–Wheeler Transform: Theory and Practice, in Proceedings of 24th International Symposium MFCS\'99, Springer Science & Business Media. |
| naposledy změněno: | 24.02.2023 10:08:06 |
za obsah této stránky zodpovídá:
Pavel Strachota | naposledy změněno: 9.9.2021