Novos Algoritmos para a Compressão de Sequências Parcialmente Comutativas

Andresso da Silva, Francisco M. Assis

DOI: 10.14209/sbrt.2022.1570824559

Evento: XL Simpósio Brasileiro de Telecomunicações e Processamento de Sinais (SBrT2022)

Keywords: Compressão Ordem Parcial Lempel-Ziv 78 Forma Normal de Foata

Abstract

Neste artigo, são apresentados dois novos métodos para a compressão de sequências definidas em alfabetos com ordem parcial. Os métodos utilizam conceitos dos monoides de comutatividade e da forma normal de Foata associada com o LZ78 para proporcionar maiores taxas de compressão. São obtidos alguns limitantes para a complexidade de sequências. Os métodos propostos apresentam ganho na compressão de sequências nos exemplos considerados quando comparados o Sequitur comutativo e com o LZ78.

Download