Perfectly Clustering Words / Dokonale se shlukující slova
advisor: | prof. Ing. Edita Pelantová, CSc. |
e-mail: | show e-mail |
type: | bachelor thesis |
branch of study: | MI_MM, MINF |
key words: | Burrows-Wheeler transformace, kódování výměny intervalů |
description: | 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. |
references: | [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. |
last update: | 24.02.2023 10:08:06 |
administrator for this page:
Ľubomíra Dvořáková | last update: 09/12/2011