On the Suitability of Suffix Arrays for Lempel-Ziv Data Compression

Lossless compression algorithms of the Lempel-Ziv (LZ) family are widely used nowadays. Regarding time and memory requirements, LZ encoding is much more demanding than decoding. In order to speed up the encoding process, efficient data structures, like suffix trees, have been used. In this paper, we explore the use of suffix arrays to hold the dictionary of the LZ encoder, and propose an algorithm to search over it. We show that the resulting encoder attains roughly the same compression ratios as those based on suffix trees. However, the amount of memory required by the suffix array is fixed, and much lower than the variable amount of memory used by encoders based on suffix trees (which depends on the text to encode). We conclude that suffix arrays, when compared to suffix trees in terms of the trade-off among time, memory, and compression ratio, may be preferable in scenarios (e.g., embedded systems) where memory is at a premium and high speed is not critical.

Controlo de tráfego

O crescente número de automóveis nas ruas das grandes cidades, assim como o crescente número de transportes urbanos para atender o crescimento das populações, veio fazer com que as cidades cada vez mais fiquem mais congestionadas e mais propícias para acidentes envolvendo viaturas e peões. Devido a isso, foram criados sistemas de controlo de tráfego capazes de melhorar o tráfego urbano nas cidades, sem deixar de lado as preocupações com os peões e nem com as emissões de poluentes para o ar. Baseado nesse cenário, este trabalho tem como objetivo abordar as possíveis soluções existentes no mercado para melhorar o fluxo das viaturas, principalmente dos transportes colectivos, com prioridades para viaturas de emergências e autocarros, assim como, as passagens de peões, e sistemas de mobilidade urbana. Desempenho do transporte público pode ser melhorado através de um melhor controlo e gerenciamento de tráfego em geral. Nos testes realizados em campo: foi medida a velocidade de viagem do autocarro no cruzamento fixo (Praça de Espanha), e correlacionando-os com intervalos do ciclo dos semáforos para este cruzamento. A flexibilidade do controlador actuando, com o auxílio de detectores de veículos, sendo capaz de variar os intervalos dentro do ciclo, bem como o volume de carros e de prestações em velocidade de viagem do autocarro. Resultados mostram que, durante o período em estudo, os benefícios de velocidade da viagem do autocarro, seria possível, através de um verdadeiro controlo de tempo feedback de cooperação entre as áreas urbanas de controlo de tráfego (Gertrude) e do sistema de localização de veículos de transportes públicos (SAEIP). Ao longo prazo, sugerimos a implantação de um sistema integrado. Fazendo com que o volume no carro seja reduzido. Este efeito leva também, a um aumento da velocidade comercial do autocarro urbano, da mesma forma como foi proposto em nossa experiência.