velikost textu

Výsledky projektu Sufixové datové struktury a jejich aplikace pro kompresi dat

Výsledky

▼▲Typ výsledku ▼▲Autor celku ▼▲Název celku
(Celkem 4 zázn.)
Senft, Martin a Dvořák, Tomáš. Sliding CDAWG Perfection. Lecture Notes in Computer Science, 2008, sv. 5280, s. 109–120. ISSN 0302-9743. [Článek v časopise]
Práce řeší otevřený problém složitosti udržování kompaktního sufixového automatu pro text v posuvném okně a popisuje on-line algoritmus pro tento problém, pracující v asymptoticky optimálním čase.
Výsledky práce byly předneseny na mezinárodní konferenci SPIRE 2008 (15th String Processing and Information Retrieval Symposium, Melbourne, Australia, November 2008).
Senft, Martin, Bottom-Up Implicit Suffix Link Simulation in Suffix Tree Construction, rukopis článku připraven k odeslání na konferenci ESA 2009 (17th Annual European Symposium on Algorithms, IT University of Copenhagen, Denmark, September 2009). V práci je navržena alternativní metoda konstrukce sufixového stromu, založená na postupu od listů ke kořeni. Známé algoritmy konstrukce sufixového stromu (McCreight,Ukkonen) pro týž účel využívají využívají sufixové hrany, vedoucí z předchůdce aktuálního vrcholu. Nahrazení tradičního řešení umožňuje omezit počet větvení, které kvůli závislosti na velikosti abecedy představují nejdražší operaci celé konstrukce. Praktická použitelnost navrženého postupu je podpořena výsledky experimentů nad rozsáhlým datovým korpusem. [Jiný výsledek]
Dvořák, Tomáš a Koubek, Václav, Longest paths in hypercubes with a quadratic number of faults, článek v recenzním řízení v časopise Information Sciences (impaktní faktor 2.147). Práce zkoumá dlouhé cesty mezi zadanými dvojicemi koncových vrcholů v n-rozměrné hyperkrychli s vadnými vrcholy. Hlavním výsledkem je algoritmus, který v případě že počet vad nepřevýší jistou kvadratickou funkci proměnné n, rozhodne o existenci řešení v polynomiálním čase vzhledem k n, a v kladném případě sestrojí hledanou cestu v lineárním čase vzhledem k její délce. Zkoumaný problém má aplikace pro efektivní řešení úlohy komprese bitmapových indexů rozsáhlých databází. [Jiný výsledek]
Dimitrov, Darko; Dvořák, Tomáš; Gregor, Petr a Škrekovski, Riste, Gray Code Compression, článek odeslán jako příspěvek na konferenci IWOCA 2009 (20th International Workshop on Combinatorial Algorithms, Hradec nad Moravicí, June 2009). Cyklický n-bitový Grayův kód je cyklická posloupnost všech n-bitových řetězců, v níž se sousední řetězce liší na jediné pozici. Práce popisuje algoritmus, který pro každé přirozené číslo n sestrojí cyklický n-bitový Grayův kód, jehož graf přechodů je podgrafem d-rozměrné hyperkrychle, kde d je horní celá část dvojkového logaritmu n. To umožní kompresi posloupností, kterí odpovídají tomuto kódu, takže na jeden n-bitový řetězec připadá v průměru Theta(log log n) bitů, což zlepšuje hodnotu Theta(log n) bitů dosažitelnou pro obecný Grayův kód. [Jiný výsledek]