Aplicação em C++ para contagem de frequência de palavras em textos, utilizando e comparando o desempenho de quatro diferentes estruturas de dados: Árvore AVL, Árvore Rubro-Negra, Tabela Hash com Encadeamento e Tabela Hash com Endereçamento Aberto.
- Sobre o Projeto
- Estruturas e Funcionalidades
- Métricas Coletadas
- Arquitetura e UML
- Pré-requisitos
- Instalação e Compilação
- Executando o Programa
- Usando com Docker
- Executando os Testes
- Documentação da API
- Roadmap do Projeto
- Contribuição
- Licença
- Créditos
Este repositório contém um projeto completo para a disciplina de Estruturas de Dados Avançadas (QXD0115) da Universidade Federal do Ceará. O objetivo é duplo:
- Implementar Estruturas de Dados: Desenvolver implementações genéricas, robustas e eficientes de dicionários (mapas chave-valor) usando Árvore AVL, Árvore Rubro-Negra, Tabela Hash com Encadeamento e Tabela Hash com Endereçamento Aberto.
- Analisar Performance: Utilizar essas estruturas em uma aplicação prática de contagem de frequência de palavras para coletar métricas (comparações, rotações, colisões) e realizar uma análise empírica do desempenho de cada uma em um cenário real.
O projeto é dividido em duas partes principais, conforme a especificação:
- Parte 1: Foco na implementação e teste das estruturas de dados.
- Parte 2: Desenvolvimento da aplicação final (contador de frequência) e análise comparativa.
- Status: 🚀 Aplicação Finalizada e Pronta para Análise
- Tecnologias: C++20, STL, GoogleTest, Doxygen, Make
- Objetivo Final: Fornecer uma ferramenta funcional para análise de texto e, mais importante, um estudo comparativo sobre a performance de estruturas de dados clássicas.
O núcleo do projeto é uma interface de dicionário (Dictionary<Key, Value>) que abstrai a implementação subjacente, permitindo que a aplicação principal troque a estrutura de dados dinamicamente.
A interface Dictionary.hpp define o seguinte contrato para todas as estruturas:
insert(const std::pair<Key, Value>&): Adiciona um par chave-valor.remove(const Key&): Remove um par com base na chave.update(const std::pair<Key, Value>&): Atualiza o valor de uma chave existente.contains(const Key&): Verifica a existência de uma chave.at(const Key&): Busca e retorna uma referência ao valor associado a uma chave.operator[](const Key&): Permite acesso ou inserção de um valor (similar aostd::map).clear(): Remove todos os elementos.size(): Retorna o número de elementos.empty(): Verifica se o dicionário está vazio.print(): Imprime o conteúdo do dicionário.forEach(const std::function<...>&): Executa uma função para cada par chave-valor.clone(): Cria uma cópia profunda (deep copy) do dicionário.
Além das estruturas de dados, a aplicação conta com os seguintes componentes principais:
DynamicDictionary: Uma classe wrapper que permite selecionar e usar qualquer uma das implementações de dicionário em tempo de execução.DictionaryFactory: Uma fábrica que simplifica a criação de instâncias de dicionários (AVLTree,RedBlackTree, etc.) com base em umDictionaryType.TextProcessor: Classe responsável por ler um arquivo de texto, normalizar as palavras (convertendo para minúsculas e removendo pontuações) e alimentar o dicionário.
Um requisito central do projeto é a análise de performance. Para isso, as seguintes métricas são rastreadas dentro de cada estrutura:
| Estrutura | Métricas |
|---|---|
| Árvores (AVL e Rubro-Negra) | comparações, rotações |
| Tabelas Hash | comparações, colisões |
Esses dados, juntamente com o tempo de execução, são salvos em arquivos de saída para permitir a análise comparativa.
A arquitetura foi projetada para ser modular e extensível. O diagrama abaixo ilustra a relação entre os principais componentes do sistema:
classDiagram
direction LR
class TextProcessor {
-file_stream: ifstream
-normalize(word: string): string
+toLowerCase(text: string): void
+processFile(wordHandler: function): void
}
class DictionaryFactory {
<<Factory>>
+create_dictionary(type): unique_ptr<Dictionary>
}
class Dictionary~Key, Value~ {
<<Interface>>
+insert(pair): void
+update(pair): void
+remove(key): void
+at(key): Value
+contains(key): bool
+operator\[](key): Value
+clear(): void
+size(): size_t
+empty(): bool
+print(): void
+forEach(func: function):void
+clone(): unique_ptr<Dictionary>
}
class DynamicDictionary {
-dictionary: unique_ptr<Dictionary>
-type: DictionaryType
}
class AVLTree~Key, Value~ {
-comparisons: long long
-rotations: long long
}
class RedBlackTree~Key, Value~ {
-comparisons: long long
-rotations: long long
}
class ChainedHashTable~Key, Value~ {
-comparisons: long long
-collisions: long long
}
class OpenHashTable~Key, Value~ {
-comparisons: long long
-collisions: long long
}
TextProcessor --> DynamicDictionary : "Usa para contar palavras"
DynamicDictionary o-- Dictionary
DictionaryFactory ..> AVLTree : "Cria"
DictionaryFactory ..> RedBlackTree : "Cria"
DictionaryFactory ..> ChainedHashTable : "Cria"
DictionaryFactory ..> OpenHashTable : "Cria"
Dictionary <|-- AVLTree
Dictionary <|-- RedBlackTree
Dictionary <|-- ChainedHashTable
Dictionary <|-- OpenHashTable
Este diagrama UML mostra a relação entre as classes principais do projeto, destacando a interface Dictionary e suas implementações concretas. A classe TextProcessor é responsável por processar o texto e alimentar o dicionário, enquanto a DictionaryFactory facilita a criação das diferentes estruturas de dados.
Diagrama geral do projeto:
Para compilar e executar este projeto, você precisará de:
- Compilador C++:
g++com suporte a C++20 ou superior. - Ferramentas de Build:
makeegit. - Documentação:
Doxygen(opcional, para gerar a documentação da API).
A biblioteca googletest é utilizada para os testes e já está incluída como um submódulo no repositório.
Siga os passos abaixo para obter o código e compilá-lo.
-
Clone o repositório:
git clone https://github.com/WillianSilva51/Dictionary.git cd Dictionary -
Inicialize o submódulo do GoogleTest:
git submodule update --init --recursive
-
Compile o projeto usando o Makefile: O
makefileprincipal oferece vários alvos. Para compilar a aplicação principal e os testes, useall.# Compila o programa principal makePara compilar em modo release (otimizado), use:
make MODE=release
Após a compilação, você pode executar o contador de frequência a partir da raiz do projeto. O programa espera dois argumentos: o tipo de estrutura de dados e o nome do arquivo de texto (que deve estar no diretório files/).
Sintaxe:
./build/bin/Dictionary <estrutura> <arquivo.txt>Argumentos:
<estrutura>: O tipo de dicionário a ser usado. Opções:avl: Árvore AVLrbt: Árvore Rubro-Negrachash: Tabela Hash com Encadeamentoohash: Tabela Hash com Endereçamento Abertoall: Executa e compara todas as quatro estruturas em threads separadas.
<arquivo.txt>: O nome do arquivo de texto localizado na pastafiles/.
Exemplos:
# Executar com a Árvore Rubro-Negra no arquivo bible.txt
./build/bin/Dictionary rbt bible.txt
# Executar e comparar todas as estruturas no arquivo donquijote.txt
./build/bin/Dictionary all donquijote.txtOs resultados, incluindo a contagem de palavras e as métricas de desempenho, serão salvos em um novo arquivo dentro do diretório out/. O programa também exibirá um resumo das métricas no console.
Para ver a mensagem de ajuda, execute:
./build/bin/Dictionary helpVocê também pode executar a aplicação usando o Docker, o que simplifica a configuração do ambiente. A imagem oficial está disponível no Docker Hub. Caso não tenha o Docker instalado, siga as instruções em Get Docker.
Esta é a maneira mais fácil de começar.
-
Puxe a imagem do Docker Hub:
docker pull williansilva51/dictionary
-
Execute o contêiner: Por padrão, o comando
./freq.sh all domcasmurro.txtserá executado.docker run williansilva51/dictionary
Você pode passar outros argumentos, como faria normalmente na linha de comando, para usar outras estruturas e arquivos:
docker run williansilva51/dictionary <estrutura> <arquivo.txt>
Você pode usar arquivos .txt do seu computador e salvar a saída em uma pasta local, sem precisar alterar a imagem. Basta montar dois volumes:
- Entrada: pasta contendo os arquivos
.txtque você quer analisar - Saída: pasta onde os resultados serão gravados
docker run --rm \
-v "$(pwd)/entrada:/app/files" \
-v "$(pwd)/out:/app/out" \
williansilva51/dictionary all domcasmurro.txtEsse comando executa a estrutura
allsobre o arquivodomcasmurro.txt, e o resultado será salvo em um arquivo dentro da pasta./out/. O nome do arquivo de saída pode variar conforme o nome do arquivo de entrada.
Se preferir construir a imagem a partir do código-fonte:
- Construa a imagem do Docker:
docker build -t dictionary . - Execute o contêiner:
docker run dictionary
Você também pode usar o Docker Compose para simplificar a execução da aplicação. Use o arquivo docker-compose.yml que está na raiz do projeto.
Para iniciar a aplicação, execute:
docker compose upA validação das estruturas de dados é realizada através de um conjunto de testes unitários com GoogleTest. Para executá-los, use o seguinte comando:
make testA saída mostrará os resultados de todos os casos de teste para cada estrutura de dados, garantindo que as operações básicas e os casos de borda estão funcionando como esperado.
A documentação completa de todas as classes, métodos e da arquitetura do projeto foi gerada com o Doxygen. Para consultá-la:
-
Gere a documentação (requer Doxygen instalado):
make docs
-
Abra o arquivo principal em seu navegador:
docs/html/index.html
A documentação é a melhor fonte de referência para entender os detalhes de implementação de cada método.
- Parte 1: Implementação das Estruturas de Dados (AVL, RB, Hash com Encadeamento, Hash com Endereçamento Aberto).
- Parte 1: Inclusão de contadores de métricas de performance (comparações, rotações, colisões).
- Parte 1: Desenvolvimento de testes unitários com GoogleTest para validar as estruturas.
- Parte 1: Criação da documentação da API com Doxygen.
- Parte 2: Implementação da aplicação de contador de frequência (leitura de arquivos, processamento de texto).
- Parte 2: Coleta de dados e análise comparativa de performance entre as estruturas.
- Parte 2: Finalização do relatório e apresentação do projeto.
Contribuições são bem-vindas! Se você tiver sugestões para melhorar o projeto, siga estes passos:
- Faça um Fork deste repositório.
- Crie uma nova Branch:
git checkout -b feature/sua-feature. - Faça o Commit de suas mudanças:
git commit -m 'feat: Descrição da sua feature'. - Faça o Push para a Branch:
git push origin feature/sua-feature. - Abra um Pull Request.
Como alternativa, consulte a documentação do GitHub em como criar uma solicitação pull.
Este projeto está licenciado sob a Licença MIT. Veja o arquivo LICENSE para mais detalhes.
- Professor: Prof. Atílio Gomes Luiz – Universidade Federal do Ceará.
- Material de Apoio: Slides e materiais da disciplina de Estruturas de Dados Avançadas.
- Ferramentas: GoogleTest para os testes unitários e Doxygen para a documentação.