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á: Čestmír Burdík | naposledy změněno: 9.9.2021
Trojanova 13, 120 00 Praha 2, tel. +420 770 127 494
České vysoké učení technické v Praze | Fakulta jaderná a fyzikálně inženýrská | Katedra matematiky