estrutura de dados / c, c++ e webassembly
A* e Huffman no navegador
Trabalhos da faculdade em C e C++, compilados para WebAssembly.
Os dois algoritmos abaixo não foram reescritos em JavaScript. É o código em C e C++ dos repositórios, compilado com o Emscripten e rodando no seu navegador. Ao preparar esta página, revisei o código e corrigi alguns bugs; o que mudou está explicado em cada seção.
A* no metrô de Paris
códigoQual o caminho mais rápido entre duas estações, contando o tempo de trocar de linha? O A* responde explorando primeiro as estações que parecem mais perto do destino: ele soma o tempo já gasto ao tempo estimado em linha reta até lá. Clique em duas estações ou use os seletores.
–
- A* expandiu
- –
- Dijkstra expandiria
- –
- linha amarela
- linha azul
- linha verde
- linha vermelha
O que corrigi no código original
- Índices: as estações vão de 1 a 14 nos arquivos, mas as matrizes de 0 a 13. A estação 14 lia fora do vetor.
- Baldeação:
linhas.txtera lido e nunca usado. Agora o estado da busca é (estação, linha) e trocar de linha custa o tempo escolhido acima. - Unidade: distâncias em km viram minutos, com o trem a 30 km/h.
- Dados:
estacoes.txtligava as estações 7 e 6, mas nenhuma linha passa entre elas. A ligação foi descartada.
Posições do mapa reconstruídas a partir da própria matriz de distâncias (MDS clássico, erro médio de 0,3 km).
Compressão de Huffman
códigoLetras que aparecem muito ganham códigos curtos; letras raras, códigos longos. O algoritmo junta sempre os dois símbolos menos frequentes numa fila de prioridade até sobrar uma árvore, e o caminho até cada folha vira o código. Digite qualquer texto.
- original
- –
- compactado
- –
- economia
- –
- ida e volta
- –
O tamanho compactado não inclui a árvore, que também precisaria ser salva no arquivo. O algoritmo trabalha em bytes: em UTF-8, "ç" e "ã" ocupam 2 bytes cada.
| símbolo | vezes | código |
|---|
O que corrigi no código original
- Acentos: a tabela de frequência era indexada com
charcom sinal. Qualquer byte acima de 127 virava índice negativo. - Fim do arquivo: a descompactação não sabia quantos bits eram válidos e decodificava o enchimento do último byte como caracteres extras.
- Um só símbolo: em "aaaa" a árvore tem uma folha e o código ficava vazio. Agora o símbolo recebe "0".
- Memória: a decodificação alocava um byte a menos que o necessário para o terminador da string.
A fila de prioridade em lista ordenada, a montagem da árvore e a geração do dicionário são as do código original.