Arvores

[raqh]

Olá a todos,
Estou a criar uma classe que permita construir uma árvore de letras e estou mesmo a precisar de um empurrãozinho.
A ideia é regrupar as palavras numa árvore na qual cada arco representa uma letra. Uma palavra seria então representada pelo caminho da raíz até ao nó que contem o valor "fimPalavra". É no array que estou a fazer tudo, não utiliso a Jtree.
Na verdade trata-se de uma maneira comptacta de representar um conjunto de palavras, como um dicionario por exemplo.
O meu problema é quero acrescentar dois métodos ao meu código aqui em baixo. Um metodo para acrecentar uma palavra à árvore e outro para testar se uma determinada palavra já existe na árvore. Se alguém tiver alguma ideia ou indicação por minima que seja, não hesite pois será certamente util.


Aqui vai o meu código:

Código: Seleccionar todos

import java.io.*;
import java.util.*;

public class ArvoreLetra
{
   char letra;
   boolean fimPalavra;
   ArrayList letrasSeguintes;
   
/* constructor */
   ArvoreLetra(char c)
   {
      letra = c;
      fimPalavra = false;
      letrasSeguintes = new ArrayList();
   }
   
   
   /* permite modificar a variável fimPalavra
   para indicar se uma subArvore corresponde ou não ao fim de uma palavra*/
   void setFimPalavra(boolean b)
   {
      fimPalavra = b;
   }
   
   
   /*testa si a árvore corresponde ao fim de uma palavra, ultima letra*/
   boolean isFimDePalavra()
   {
      return fimPalavra;
   }
   
   
   /* testa se o caractere c é uma das letras a seguir à letra corrente */
   boolean contemLetra(char c)
   {
      for (int i=0; i<letrasSeguintes.size(); i++)
      {
         ArvoreLetra a = (ArvoreLetra)letrasSeguintes.get(i);
         if (a.letra == c) return true;
      }
      return false;
   }

   
   /* retorna a subArvore (letra seguinte) que corresponde ao caractere c */
   ALettre getSubArvore(char c)
   {
      for (int i=0; i<letrasSeguintes.size();i++)
      {
         ArvoreLetra a = (ArvoreLetra)letrasSeguintes.get(i);
         if (a.letra == c) return a;
      }
      return null;
   }

   

   /*void acrescentarPalavra(String palavra)
   {
       
   }

   
   boolean contemPalavra(String palavra)
   {
       
   }*/
   

}


Obrigado.

[vamosAeles]

Boas,
antes uma consideração sobre o teu código:

pelo que percebi da tua explicação, na classe Árvore tens um arraylist para as seguintes árvores letras, isso significa que se tiveres a palavra 'abc' no 'a' vais ter um array para 'bc' e no 'b' um array para o 'c', certo? Se for assim depois torna-se mais dificil de gerir esses arrays, quando se adiciona uma letra.
Sugeria que alterasses esse ArrayList para uma var do tipo ArvoreLetra que 'apontava' para a próxima letra, se existisse; tipo uma lista ligada (ou seja, uma espécie de implementação da LinkedList para a ArvoreLetra).

Neste caso o método de acrescentar palavra torna-se mais simples. Se for como tens acima, terás que percorrer todos os arrays da ÁrvoreLetra para acrescentar as letras dessa palavra.

Cumps,
[[]]

[raqh]

Olá,
Obrigado pela resposta
O que quero fazer é: criar os metodos contemPalavra e acrescentarPalavra. Depois utilizar a classe para construir uma árvore de letras a partir de um ficheiro de texto. Por fim, ler o ficheiro e mostrar todas as palavras que não se encontrem na árvore construida a partir do primeiro ficheiro.

É na criação destes 2 metodos que estou a ter dificuldades. Para o resto, não tenho problemas.

Eu penso que a solução mais facil é fazer com recursividade e então seria preciso utilizar os metodos contemLetra e getSubArvore numa chamada recursiva para os dois metodos contemPalavra e acrescentarPalavra.

O principio é o mesmo, por isso se eu conseguir encontrar o algoritmo correcto para o metodo acrescentarPalavra será exacatamente o mesmo principio para o metodo contemPalavra, só que em vez de acrescentar ele vai retornar um boolean.

Mas...até agora ainda não consegui.

[raqh]

Olá,
Obrigado pela resposta.
O que quero fazer é: criar os metodos contemPalavra e acrescentarPalavra. Depois utilizar a classe para construir uma árvore de letras a partir de um ficheiro de texto. Por fim, ler o ficheiro e mostrar todas as palavras que não se encontrem na árvore construida a partir do primeiro ficheiro.

É na criação destes 2 metodos que estou a ter dificuldades. Para o resto, não tenho problemas.

Eu penso que a solução mais facil é fazer com recursividade e então seria preciso utilizar os metodos contemLetra e getSubArvore numa chamada recursiva para os dois metodos contemPalavra e acrescentarPalavra.

O principio é o mesmo, por isso se eu conseguir encontrar o algoritmo correcto para o metodo acrescentarPalavra será exacatamente o mesmo principio para o metodo contemPalavra, só que em vez de acrescentar ele vai retornar um boolean.

Mas...até agora ainda não consegui. Alguma ideia?

Aqui vai uma versao mais recente do meu codigo:

Código: Seleccionar todos


import java.io.*;
import java.util.*;

public class ArvoreLetra
{
   char letra;
   boolean fimPalavra;
   ArrayList letrasSeguintes;
   
/* constructor */
   ArvoreLetra(char c)
   {
      letra = c;
      fimPalavra = false;
      letrasSeguintes = new ArrayList();
   }
   
   
   /* permite modificar a variável fimPalavra
   para indicar se uma subArvore corresponde ou não ao fim de uma palavra*/
   void setFimPalavra(boolean b)
   {
      fimPalavra = b;
   }
   
   
   /*testa si a árvore corresponde ao fim de uma palavra, ultima letra*/
   boolean isFimDePalavra()
   {
      return fimPalavra;
   }
   
   
   /* testa se o caractere c é uma das letras a seguir à letra corrente */
   boolean contemLetra(char c)
   {
      for (int i=0; i<letrasSeguintes.size(); i++)
      {
         ArvoreLetra a = (ArvoreLetra)letrasSeguintes.get(i);
         if (a.letra == c) return true;
      }
      return false;
   }

   
   /* retorna a subArvore (letra seguinte) que corresponde ao caractere c */
   ArvoreLetra getSubArvore(char c)
   {
      for (int i=0; i<letrasSeguintes.size();i++)
      {
         ArvoreLetra a = (ArvoreLetra)letrasSeguintes.get(i);
         if (a.letra == c) return a;
      }
      return null;
   }

   

   /*void acrescentarPalavra(String palavra)
   {
       
   }

   
   boolean contemPalavra(String palavra)
   {
       
   }*/

/* leitura du ficheiro, construção da árvore e verificação */
   public static void main(String[] args)
   {
      String ficheiro ="test.txt";
      String ficheiro1 = "test1.txt";
      String palavra, lin;
      StringTokenizer linhaToken;
       
      ArvoreLetr p;
      p = new ArvoreLetra('A');
      System.out.println("OK!");
      
      //leitura do ficheiro de texto         
      try
      {
         InputStream input = new FileInputStream(ficheiro);
         InputStreamReader streamReader = new InputStreamReader(input);
         BufferedReader br = new BufferedReader(streamReader);
           
         while ((lin = br.readLine())!=null)
         {
            System.out.println("Ok!!");
            linhaToken = new StringTokenizer(lin);
            
            while (linhaToken.hasMoreTokens())
            {
               System.out.println("OK!!");
               palavra = (linhaToken.nextToken());
               
               System.out.println(palavra);
               p.acrescentarPalavra(palavra.toLowerCase());           
            }           
         }
      br.close();
      }
      catch (Exception e)
      {
      }
      
      //pesquisa  no ficheiro de texto         
      try
      {
         InputStream input = new FileInputStream(ficheiro1);
         InputStreamReader streamReader = new InputStreamReader(input);
         BufferedReader br = new BufferedReader(streamReader);
         
         while ((lin = br.readLine())!=null)
         {
            System.out.println("Ok!!");
            linhaToken = new StringTokenizer(lin);
             
            while (linhaToken.hasMoreTokens())
            {
               System.out.println("OK!!");
               palavra = (linhaToken.nextToken());
               System.out.println(palavra);
                   
               if(p.contemPalavra(palavra.toLowerCase()))
                  System.out.println("Ok!! Palavra encontrada : "+palavra);
               else
                  System.out.println("Palavra nao encontrada : "+palavra);
            }             
         }
      br.close();
      }
      catch (Exception e)
      {
      }
   }
}


[vamosAeles]

Boas, aqui vai a minha opinião:

1)o teu objectivo é comparar as palavras de dois files, de uma maneira qualquer, ou queres/tens de usar essa ÁrvoreLetra? (Se por acaso é a primeira, há soluções mais simples)

2)assumindo que tens de usar a ÁrvoreLetra:

A resposta à tua pergunta (criar o metodo acrescentarPalavra sobre a uma instância ArvLetra) poderá não fazer sentido dependendo de algumas questões que ainda não percebi.

Como explicação para a resposta dada no paragrafo anterior, olhando para o main e para os métodos da classe em si:
O que é suposto representar uma instância da ArvoreLetra?
- um caracter de uma palavra que estava no ficheiro?
- uma palavra que estava no ficheiro?
- é suposto que a partir da instância que crias no main, teres acesso a todas as palavras/letras presentes no ficheiro?
- a 'instância principal' é suposta indicar o primeiro caracter, e o arraylist q tem umas lista dos caracteres que compoêm a palavra? ou cada posição do arraylist é o caracter seguinte de uma outra palavra?

EDIT: depois de ler de novo o teu 1º post, fico com a ideia de que cada posição do arraylist é o caracter seguinte de uma outra palavra, se for o caso, tens de alterar o main para poderes ter as 23 letras (ou considerar que a instancia q defines no main nao inicia nehuma palavra em si), e nesta caso 'basta' implementar os métodos q indicas. Também neste caso o boolean nao deverá indicar se A palavra terminou, mas se UMA palavra terminou, isto porque pode haver palavras 'dentro' de outras palavras. Diz qq coisa q depois se quiseres dou-te uma ajuda

Cumps,
[[]]

[raqh]

Olá,
Obrigado pela resposta. Tenho mesmo que usar a ArvoreLetra. O primeiro ficheiro serve para construir a árvore, ele lê o ficheiro palavra a palavra e percorre cada palavra letra a letra para então construir a árvore. (p.acrescentarPalavra(palavra.toLowerCase())).

Depois o segundo, serve como disseste para comparar à árvore construida com o primeiro ficheiro. Para cada palavra deste segundo ficheiro chama-se o metodo contemPalavra e retorna true se pertence ao lexico(p.contemPalavra(palavra.toLowerCase())) .

Em relação à instância, é suposta indicar o primeiro caracter e o arraylist uma lista dos caracteres seguintes. No main só tem para palavras começadas por « A », que será a raíz. A partir daí imensas palavras podem se formar, só que neste caso todas começarão por A.
Por exemplo se eu substituir A por S e tiver 4 palavras:
Sol
sair
soma
somas

Daria isto:
A* I* R°
*
S* O* L °
*
M
*
A
°
S
°

Imagina que as letras estao sobre os arcos, o * é um nó e o ° representa o nó de fim de palavra.

O principio é o mesmo para os dois metodos, só que um vai acrescentar a palavra e o outro vai retornar um boolean.

Parece que a solução mais simples é utilizar os metodos contemLetra e getSubArvore numa chamada recursiva para os dois metodos contemPalavra e acrescentarPalavra. Só que....bloqueio total, não consigo avançar e no entanto nao parece muito complicado.:/ O que tenho no código é mesmo só o cabecalho para os dois metodos, pois cada vez que tento completar, nao sai nada de jeito.

Se me puderes então ajudar, agradecia-te infinitamente.


Mais uma vez obrigado.

[vamosAeles]

Olá,

pelo esquema com esse exemplo a ideia é que o array de uma ArvoreLetra contenha os proximo caracteres da palavra, ie, se o array tiver 5 posições, logo à partida podes assumir que há registas-te anteriormente mais 5 palavras (pelo menos), em que os caracteres iniciais dessas 5 palavras são comuns até ao caracter (ÁrvoreLetra em que te 'encontras').

Nesse caso:

Código: Seleccionar todos

static int getIndiceChar(List letras, char c){
  for(int i = 0; i < letras.lenght; i++){
    if(((ArvLetra)letras.get(i)).letra == c)) return i;
  }
  return -1;//caractar ainda nao existe na lista
}

void acrescentarPalavra(String palavra)
{
   if(palavra.lenght() == 0) {
     fimPalavra = true;
     return;
   }
   if(contemPalavra(palavra)) return;
   int ind = getIndiceChar(letrasSeguintes, palavra.charAt(0));
   if(ind == -1){
       ArvoreLetra av = new ArvoreLetra(palavra.chatAt(0);
       arv.letrasSeguintes.add(av);
       return av.acrescentarPalavra(palavra.substring(1, palavra.lenght());
   }
   else{
       return arv.letrasSeguintes.get(ind).acrescentarPalavra(palavra.substring(1, palavra.lenght()));
   }
}

   
boolean contemPalavra(String palavra)
{
     if(palavra.lenght == 0) return fimPalavra;
     int ind = getIndiceChar(letrasSeguintes, palavra.charAt(0));
     if(ind == -1) return false;
     else return letrasSeguintes.get(ind).contemPalavra(palavra.substr(1, palavra.lenght());

}



Pode haver erros ortográficos, faltar alguns cast... ou faltar mesmo qq coisa para funcar

De qq maneira assumi que a instância ArvoreLetra que tens no main, nao inicia nenhuma palavra em si, ou seja a letras que ela tem é irrelevante, a partir do seu array é que se iniciam as palavras.

Se não perceberes diz qq coisa

Cumps,
[[]]
[/code]

[raqh]

Olá,
Muito obrigado pela ajuda. Como tenho o metodo contemLetra, nao é necessário ter o metodo getIndiceChar, pois nao? Também tenho o metodo getSubarvore. Estive a tentar modficar o teu metodo para utilizar os metodos contemLetra e getSubArvore mas n tenho a certeza se está bem, principalmente o getSubarvore. Também aproveitei ter o metodo setFimDepalavra para pôr a true.
Podes me o corrigir pff?
Aqui vai:

Código: Seleccionar todos

void acrescentarPalavra(String palavra)
   {
      if(palavra.length() == 1)
      {
         setFimDePalavra(true);
         return;
      }
      if(contemPalavra(palavra))
         return;
      
      if (palavra.charAt(0) == letra)
      {
         char c = palavra.charAt(1);
         if (!contemLetra(c))
         {
            ArvoreLetra av = new ArvoreLetra(palavra.chatAt(0));
            av.letrasSeguintes.add(av);
            av.acrescentarPalavra(getSubArvore(c), palavra.substring(1));
         }
      
      }
   }


Mais uma vez obrigado pela atenção.

[vamosAeles]

Boas,

sim podes usar o contemLetra, e devia tb ter usado, mas não devo ter reparado nele, assim não é necessário o getIndChar.

Da maneira como mudas-te o método acrescentarPalavra, parece que quando invocas o acrescentar palavra já assumes que a letra da instância é igual à primeira letra na palavra que passas como argumento. Se for o caso parece-me bem, excepto o último if:
1)Nao estás a fazer nada se a próxima letra existir...
2)não é ao av em que fazes add mas a 'this'

esse if fica tipo:

Código: Seleccionar todos

    if (!contemLetra(c))
    {
      ArvoreLetra av = new ArvoreLetra(palavra.chatAt(1)); //tinhas 0
      letrasSeguintes.add(av); // tinhas av.letras....
      av.acrescentarPalavra(palavra.substring(1));
    }
    else
    {
      getSubArvore(c).acrescentarPalavra(palavra.substring(1));
    }


Assim como o teste "if (palavra.charAt(0) == letra) " será desnecessário, pois deverá dar sempre true.

Para isso depois no main ou onde for, quando invocas pela primeira o acrescentaPalavra, já tens de ter a confirmação que a letra da instância é igual à primeira da palavra.

PS - vendo melhor o teste contemPalavra() é redundante, pois se da primeira vez da falso, já nunca dá true nas invocações recursivas, pelo que podias retirar esse if e fazer esse teste antes da invocação do acrescentaPalavra, mas é como preferires

[raqh]

Olá! Muito obrigado!! Olha então como não tem utilidade tirei o teste "if (palavra.charAt(0) == letra) "? O código está a funcionar. Só não sei se percebi bem a ultima parte da tua explicação:

Para isso depois no main ou onde for, quando invocas pela primeira o acrescentaPalavra, já tens de ter a confirmação que a letra da instância é igual à primeira da palavra.

PS - vendo melhor o teste contemPalavra() é redundante, pois se da primeira vez da falso, já nunca dá true nas invocações recursivas, pelo que podias retirar esse if e fazer esse teste antes da invocação do acrescentaPalavra, mas é como preferires.

Por isso não tenho a certeza se levei em conta tudo o que disseste. Mas envio aqui o codigo completo para veres se está tudo bem.

Mais uma vez muito obrigado.

Código: Seleccionar todos

import java.io.*;
import java.util.*;

public class ArvoreLetra
{
   char letra;
   boolean fimPalavra;
   ArrayList letrasSeguintes;
   
   /* constructor */
   ArvoreLetra(char c)
   {
      letra = c;
      fimPalavra = false;
      letrasSeguintes = new ArrayList();
   }
   
   
   /* permite modificar a variável fimPalavra
   para indicar se uma subArvore corresponde ou não ao fim de uma palavra*/
   void setFimPalavra(boolean b)
   {
      fimPalavra = b;
   }
   
   
   /*testa si a árvore corresponde ao fim de uma palavra, ultima letra*/
   boolean isFimDePalavra()
   {
      return fimPalavra;
   }
   
   
   /* testa se o caractere c é uma das letras a seguir à letra corrente */
   boolean contemLetra(char c)
   {
      for (int i=0; i<letrasSeguintes.size(); i++)
      {
         ArvoreLetra a = (ArvoreLetra)letrasSeguintes.get(i);
         if (a.letra == c) return true;
      }
      return false;
   }

   
   
   /* retorna a subArvore (letra seguinte) que corresponde ao caractere c */
   ArvoreLetra getSubArvore(char c)
   {
      for (int i=0; i<letrasSeguintes.size();i++)
      {
         ArvoreLetra a = (ArvoreLetra)letrasSeguintes.get(i);
         if (a.letra == c) return a;
      }
      return null;
   }

   
   void acrescentarPalavra(String palavra)
   {
      if(palavra.length() == 1)
      {
         setFimPalavra(true);
         return;
      }
      if(contemPalavra(palavra))
         return;
      
      char c = palavra.charAt(1);
      if (!contemLetra(c))
      {
         ArvoreLetra av = new ArvoreLetra(palavra.charAt(1));
         letrasSeguintes.add(av);
         av.acrescentarPalavra(palavra.substring(1));
      }
      else
      {
         getSubArvore(c).acrescentarPalavra(palavra.substring(1));
      }
   }
   

   boolean contemPalavra(String palavra)
   {
      if(palavra.length() == 1)
         return fimPalavra;
     
      char c = palavra.charAt(1);
      
      if (!contemLetra(c))
      {
         return false;
      }
      else
         return getSubArvore(c).contemPalavra(palavra.substring(1, palavra.length()));
      
   }


/* leitura du ficheiro, construção da árvore e verificação */
   public static void main(String[] args)
   {
      String ficheiro ="test.txt";
      String ficheiro1 = "test1.txt";
      String palavra, lin;
      StringTokenizer linhaToken;
       
      ArvoreLetra p;
      p = new ArvoreLetra('A');
      System.out.println("OK!");
     
      //leitura do ficheiro de texto         
      try
      {
         InputStream input = new FileInputStream(ficheiro);
         InputStreamReader streamReader = new InputStreamReader(input);
         BufferedReader br = new BufferedReader(streamReader);
           
         while ((lin = br.readLine())!=null)
         {
            System.out.println("Ok!!");
            linhaToken = new StringTokenizer(lin);
           
            while (linhaToken.hasMoreTokens())
            {
               System.out.println("OK!!");
               palavra = (linhaToken.nextToken());
               
               System.out.println(palavra);
               p.acrescentarPalavra(palavra.toLowerCase());           
            }           
         }
      br.close();
      }
      catch (Exception e)
      {
      }
     
      //pesquisa  no ficheiro de texto         
      try
      {
         InputStream input = new FileInputStream(ficheiro1);
         InputStreamReader streamReader = new InputStreamReader(input);
         BufferedReader br = new BufferedReader(streamReader);
         
         while ((lin = br.readLine())!=null)
         {
            System.out.println("Ok!!");
            linhaToken = new StringTokenizer(lin);
             
            while (linhaToken.hasMoreTokens())
            {
               System.out.println("OK!!");
               palavra = (linhaToken.nextToken());
               System.out.println(palavra);
                   
               if(p.contemPalavra(palavra.toLowerCase()))
                  System.out.println("Ok!! Palavra encontrada : "+palavra);
               else
                  System.out.println("Palavra nao encontrada : "+palavra);
            }             
         }
      br.close();
      }
      catch (Exception e)
      {
      }
   }
}

[vamosAeles]

Boas,

parece bem, menos uma cena no main,

repara que o primeiro caracter de todas as palavras vai ser 'comido' e substituido por um 'A' porque é o caracter com que inicializas a ArvoreLetra.
Dai ter dito:

Para isso depois no main ou onde for, quando invocas pela primeira o acrescentaPalavra, já tens de ter a confirmação que a letra da instância é igual à primeira da palavra.

.

Podes por exemplo criar um Hashmap (ou arraylist) de ArvoreLetra no main em que a chave é o caracter (correspondendo ao primeiro char das palavras) que vais encontrando e antes de acrecentares uma palavra obtens a ArvoreLetra do hashmap correspondente ao primeiro caracter da respectiva palavra.
Em alternativa é como disse num post anterior: a instância Arvoreletra do main nao inicia nenhuma palavra em si, apenas 'começam' no seu arraylist (mas para isso tens q efectuar ligeiras alteracoes nos metodos acrescente e contem palavra).


Se depois ainda tiveres com dificuldade diz qq q se nao houver prob posso postar uma solução qq, apenas tem de decidir qual das alternativas acima explicadas preferes.

Cumps,
[[]]

[raqh]

Boa tarde,

Pois é, não tinha reparado nisso... Mas então acho estranho que ele diga, por exemplo, que a palavra solário está contida na árvore. Porque se a primeira letra é substituida por um A, ele deveria retornar false, não era? Mas se mesmo assim for necessário modificar o main, acho que prefiro a tua segunda alternativa, ou seja, a instancia no main não iniciar nenhuma palavra em si.

Obrigado.

[vamosAeles]

Olá,

se acrescentares uma palavra qq, e verificares se ela existe, deverá dar true, mesmo a comer o 1º caracter, porque o contemPalavra faz a mesma cena , ie, assume que o primeiro caracter é um 'a'. (dai o exemplo que deste dar sempre true)

Para a instância do main não inciar nenhum palavra em si, tens que adaptar o acrescenta e contemPalavra tipo:

Código: Seleccionar todos

void acrescentarPalavra(String palavra)
   {
      if(palavra.length() == 0)
      {
         setFimPalavra(true);
         return;
      }
      if(contemPalavra(palavra))
         return;
     
      char c = palavra.charAt(0);
      if (!contemLetra(c))
      {
         ArvoreLetra av = new ArvoreLetra(palavra.charAt(0));
         letrasSeguintes.add(av);
         av.acrescentarPalavra(palavra.substring(1));
      }
      else
      {
         getSubArvore(c).acrescentarPalavra(palavra.substring(1));
      }
   }
   

   boolean contemPalavra(String palavra)
   {
      if(palavra.length() == 0)
         return fimPalavra;
     
      char c = palavra.charAt(0);
     
      if (!contemLetra(c))
      {
         return false;
      }
      else
         return getSubArvore(c).contemPalavra(palavra.substring(1));
     
   }


É praticamente q tinhas, mudou apenas nos charAt(1), passou a ser 0, e no if da palavra.lenght == 1, passou tb a ser 0.

Cumps,
[[]]

[raqh]

Ah, então por isso é q tava sempre a dar true...lol Já modifiquei, obrigado Uma última pergunta, tenho que tirar a instrução que instancia aqui em baixo? Como os metodos ja foram alterados, será que posso deixar? Já não substitui a primeira letra pelo A, se percebi bem.

Código: Seleccionar todos

  ArvoreLetra p;
      p = new ArvoreLetra('A');

[vamosAeles]

Boas,

tens sempre que ter isso, por um 'A' ou 'B' é irrelevante para criares a instância, para tirar esse 'A' só criando outro constructor sem argumentos, e fazias p = new ArvoreLetra();

Cumps,
[[]]