-
Notifications
You must be signed in to change notification settings - Fork 0
/
leiame.txt
123 lines (96 loc) · 6.57 KB
/
leiame.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/*
Trabalho Pratico 1 de Algoritimos E Estruturas de Dadados II - APLICACAO COM ARVORES DIGITAIS
Professora: Doutora Glaucia Braga e Silva
Integrantes (Matricula - Nome):
1278 - Angelo Bernar Tessaro Morelo
3513 - Leandro Lazaro Araujo Vieira
3489 - Mateus Pinto da Silva
*/
Trabalho realizado pelo grupo 1278 - Angelo Bernar Tessaro Morelo, 3513 - Leandro Lazaro Araujo Vieira, 3489 - Mateus Pinto da Silva, sobre a orientação da professora Glaucia Braga e Silva na disciplina de Algoritmos e Estruturas de Dados 2.
OBSERVAÇÕES IMPORTANTES: A integridade de execução só é garantida se executado em Linux. Em relação a compiladores, tanto GCC quanto Clang apresentam bons resultados, embora o Clang tenha se mostrado muito eficiente com otimizadores.
O trabalho consiste em armazenar dados em uma estrutura de dados e subsequentemente criar uma seach engine para recuperar esses dados e localização de uma maneira facilitada.
Para isso foram criadas três estruturas de dados, uma estrutura de arvore TST, uma Patrícia, e uma BST.
A árvore TST foi utilizada para facilitar as pesquisas por radicais.
A Patrícia foi criada para armazenar as palavras com o índice invertido.
A BST é usada para os resultados das pesquisas ordenadamente.
Os dados serão palavras contidas em vários arquivos diferentes, e armazenadas usando a técnica de ponderação TF-IDF (Term frequency – Inverse Document Frequency). Mostrando a relevância da palavra em cada um dos documentos.
===> COMO UTILIZAR:
* Para compilar usando o GCC, abra o terminal na pasta principal do trabalho prático e digite "make" (sem aspas).
* Para compilar usando o Clang (preferível), digite "make clang" também na pasta principal (sem aspas).
* Para apagar o arquivo executável, digite "make clear".
* Para executar depois de compilar, digite "make run". A partir disso, o menu é autoexplicativo.
Sobre os arquivos:
As funções foram divididas em várias bibliotecas (TADS) relacionadas a cada função necessária:
===> bstNode: esse TAD contém a estrutura do tipo bstNode, que será usado como base para as funções relacionadas ao nó da arvore BST:
* bstNodeStartTree: Faz a arvore BST vazia.
* bstNodeCreateNode: Cria novo nó
* bstNodeInsertFile: checa se o nome do arquivo não foi inserido e o insere no lugar certo da BST.
* bstNodeInOrder: escreve em tela a arvore BST
* bstNodeDestroy: apaga toda a arvore BST.
===> invertedChainedList: contém a estrutura do tipo usado para a lista de ocorrências das palavras em cada texto “invertedChainedList”, e também as funções usadas para tanto:
* invertedChainedListStartList:
* invertedChainedListCreateNode:
* invertedChainedIncrementOcurrence:
* invertedChainedListInsertNode:
* invertedChainedListGoThrough: escreve em tela as ocorrências.
* invertedChainedListDestroy:
A nomenclatura das funções é semelhante à nomenclatura anterior.
===> listaPesquisa: Possui a estrutura do tipo “listaPesquisa”, e as funções que guardam em uma lista encadeada o nome dos arquivos e os pesos de cada um:
* listaPesquisaInsereItem:
* listaPesquisaDestroy:
* listaPesquisaShow:
A nomenclatura das funções é semelhante à nomenclatura anterior.
===>listAltoFill: possui o tipo “listAutoFill” e as funções usadas para auxiliar a pesquisa das palavras e seus radicais:
* listAutoFillInsereItem:
* listAutoFillShowItens:
* listAutoFillShowItensAux: Função recursiva para auxiliar “listAutoFillShowItens”.
* listAutoFillGetItem: Retorna um item específico da lista.
* listaAutoFillDestroy:
===> patriciaNode: esse arquivo fará uso da biblioteca “invertedChainedList”, e possui os tipos usado para a criação da arvore patricia “patriciaNode”, assim como a enumeração do identificador do tipo de nó “nodeType”. Aqui também são declaradas as funções relacionadas à arvore patrícia:
* patriciaNodeStartTree:
* patriciaNodeIsExternal: Confere o tipo de nó.
* patriciaNodeCheckBitFlow: checa se o caractere do nó interno é maior ou menor que o da posição.
* patriciaNodeCreateExternalNode:
* patriciaNodeCreateInternalNode:
* patriciaNodeWhichIsDifferent: retorna a posição na string que a palavra à ser inserida difere da palavra já inserida.
* patriciaNodeReturnPosition: retorna a posição de um nó interno.
* patriciaNodeInsertBetween: faz a verificação e chama as funções de inserção no local certo da árvore.
* patriciaNodeIncrementOcurrence: em nós externos, chama a função “invertedChainedListInsertNode” para listar o arquivo.
* patriciaNodeInsertWord: faz a inserção da palavra na árvore.
* patriciaNodeGoThrough: mostra as palavras da arvore.
* patriciaNodeGoThroughWithOcurrences: mostra as palavras e as ocorrências das mesmas nos textos.
* patriciaNodeSearchWord: retorna uma palavra específica.
* patriciaNodeDestroy:
===> tstFileNode: aqui foram feitas as funções de tratamento de arquivo, possuí o tipo nó usado na arvore TST “tstFileNode” assim como as funções usadas nessa arvore:
* tstFileNodeStartTree:
* tstFileNodeCreateNode:
tstFileNodeAuxInsertFile: Função recursiva para auxiliar “tstFileNodeInsertFile”.
* tstFileNodeInsertFile:
* tstFileNodeInsertInputs:
* tstFileNodeSearch:
* tstFileNodeDestroy:
===> tstNode: Nesse TAD está o tipo para o nó da arvore TST “tstNode”, assim como são feitas as funções que vão trabalhar diretamente com a árvore:
* tstNodeStartTree:
* tstNodeCreateNode:
* tstNodeSetEndWord:
* tstNodeInsertWord:
* tstNodeSearchWord:
* tstNodeSearchRadical:
* tstNodeAuxGoThrough: Função recursiva para auxiliar “tstNodeGoThrough”.
* tstNodeGoThrough: Mostra toda a arvore TST.
* tstNodeIsNotInTree:
* tstNodeDestroy:
* tstNodeSearch:
===> generalFunctions: Esse TAD tem as funções gerais da Search Engine, e para isso, ele faz uso de todos os outros TADs já citados.
* generalFunctionsSetNumDifferentsWords: conta as palavras.
* generalFunctionsLoadWords: pega os dados dos arquivos e faz a inserção nas várias arvores.
* generalFunctionsAuxLoadTstFile: Função recursiva para auxiliar “generalFunctionsLoadTstFile”.
* generalFunctionsLoadTstFile: abre os vários arquivos e chama as funções para inserção.
* generalFunctionsSearch:
* generalFunctionsSearchWordAux: Função recursiva para auxiliar “generalFunctionsSearch”.
* generalFunctionsLoadListInBST: insere dados na BST
* generalFunctionsShowRadicalsAutoFill: pesquisa com radicais
* generalFunctionsGetRadical:
===> BIBLIOGRAFIA:
* O método de abertura de multiplos arquivos foi extremamente inspirado do link https://www.hardware.com.br/comunidade/arquivos-varrer/1103524/
* Os arquivos de input são a musicografia da banda Queen, e foram retiradas do site https://www.kaggle.com/mousehead/songlyrics