/EDII_arvores

Implementação de atividade prática com árvores

Primary LanguagePython

Tópicos

  1. Observações Iniciais
    1. Parâmetros de Entrada
      1. Documentos
      2. Quantidade de caracteres retidos
    2. Observações
  2. Progresso
    1. Implementações [5/5]
  3. Estruturação
    1. Objeto Word
    2. Idéia básica
  4. Resultados
    1. 2º cenário
    2. 3º cenário
      1. Entrada 67MB + 262MB

Observações Iniciais

Parâmetros de Entrada

Documentos

  • Quantidade N de caminhos de documentos na linha de comando

Quantidade de caracteres retidos

  • Parâmetro C que irá dizer a quantidade de caracteres comparados nas palavras

Observações

  • Ignorar sinais de pontuação (TODOS)
  • Todas as palavras devem ser colocadas em LOWERCASE
  • Duas palavras que não diferem nos primeiros caracteres C são identicas
  • Palavras que possuem menos de C caracteres são desconsideradas
  • Criar própria coleção de testes

Progresso

Implementações [5/5]

  • Hashing Aberto
  • Árvore Binária
  • Árvore AVL
  • Árvore Rubro Negra
  • Árvore B

Estruturação

Objeto Word

  • Estruturação padrão em todo o programa
  • Objeto Word será guardardo na estrutura de dado escolhida e dentro dele uma mesma estrutura de dados irá guardas o objeto FilesOccur

img

Idéia básica

img

img

Resultados

2º cenário

Hash C=3        
Tamanho do Hash CeC do IV Memoria IDF1 IDF2  
20 2.629169 26800 0.000512000000000068 0.00047999999999959186  
60 2.724151 26736 0.0005869999999998932 0.0006500000000002615  
120 2.669139 26788 0.0005990000000002382 0.000412000000000301  
           
           
C = 3 BST AVL ARB BTree G=10 BTree G=100
CeC do IV 2.788035 2.697705 3.2378199999999997 2.736724 2.699848
Memoria 26728 26764 26668 26728 26772
IDF1 0.0008880000000002219 0.0012080000000000979 0.0006839999999996849 0.0007709999999998551 0.0005899999999998684
IDF2 0.0008659999999998114 0.0007129999999997416 0.0008110000000001172 0.0008919999999998929 0.0013150000000003992
           
           
Hash C=5        
Tamanho do Hash CeC do IV Memoria IDF1 IDF2  
20 1.9840140000000002 26804 0.0005489999999999107 0.0007359999999998479  
60 2.070367 26804 0.0006969999999997256 0.0005329999999998947  
120 1.9946290000000002 26368 0.0006309999999998261 0.0006259999999995713  
           
           
C = 5 BST AVL ARB BTree G=10 BTree G=100
CeC do IV 2.1238409999999996 2.024773 1.9617159999999998 2.015054 2.056037
Memoria 30904 26704 26608 26604 26700
IDF1 0.0006810000000001537 0.0005260000000002485 0.0008019999999997474 0.0006439999999998669 0.0005550000000003052
IDF2 0.0006710000000000882 0.0007519999999998639 0.0007049999999999557 0.0005639999999997869 0.0011540000000000994

3º cenário

Entrada 67MB + 262MB

Hash C=1        
Tamanho do Hash CeC do IV Memoria IDF1 IDF2  
20 137.743045 27076 0.00028800000001183435 0.00038500000002272827  
60 140.79580199999998 26804 0.00034499999998161 0.00041899999999372994  
120 131.657103 27004 0.0005660000000204946 0.0002689999999745396  
           
           
C = 1 BST AVL ARB BTree G=10 BTree G=100
CeC do IV 137.885787 194.28471100000002 207.075305 168.479665 166.195416
Memoria 26644 26576 26800 26804 26832
IDF1 0.00042099999998868043 0.00021399999999971442 0.00045399999999062857   0.0006629999999745451
IDF2 0.00048300000000267573 0.0008780000000001564 0.0008270000000152322   0.0008799999999951069
           
           
Hash C=3        
Tamanho do Hash CeC do IV Memoria IDF1 IDF2  
20 173.040934 26836 0.0005079999999964002 0.0004500000000007276  
60 181.379853 27084 0.0005869999999958964 0.0006109999999921456  
120 160.836913 26720 0.0005000000000165983 0.0005089999999938755  
           
           
C = 3 BST AVL ARB BTree G=10 BTree G=100
CeC do IV 195.054941 157.097983 191.092486 127.254069 128.95186
Memoria 26824 26824 26824 26604 26776
IDF1 0.0003059999999948104 0.0007350000000201362 0.00036500000001638 0.00029299999999921056 0.00026799999997706436
IDF2 0.00083399999999755893 0.0005390000000033979 0.00040799999999308056 0.0005469999999974107 0.0005889999999908468
           
           
Hash C=5        
Tamanho do Hash CeC do IV Memoria IDF1 IDF2  
20 173.040934 26836 0.0005079999999964002 0.0004500000000007276  
60 181.379853 27084 0.0005869999999958964 0.0006109999999921456  
120 160.836913 26720 0.0005000000000165983 0.0005089999999938755  
           
           
C = 5 BST AVL ARB BTree G=10 BTree G=100
CeC do IV 153.19824699999998 148.77687600000002 147.75920200000002 114.60230700000001 121.563428
Memoria 26780 26644 26620 26796 26768
IDF1 0.0007249999999885404 0.0006160000000079435 0.0007759999999734646 0.0006610000000080163 0.0007409999999907768
IDF2 0.0006040000000098189 0.0007350000000201362 0.0009050000000172531 0.0007869999999883248 0.0006960000000049149