Comparação de palavras em textos com um banco de palavras ordenadas

Bem… da uma olhada nas minhas emnsagens nesse topico que te da uma ideia para comparar as palavras com um banco de palavras.

http://www.guj.com.br/posts/list/45/202214.java#1024199

Esta TreeMap é um Objeto que implementa uma árvore binária de busca, certo?

Quando você faz “lista.removeAll(wordsMapping);”, esta remoção respeita a busca binária para comparação dos elementos?

Show! Eu tava até pensando em fazer um mapeanto dos primeiros caracteres pra ajudar na busca, mas vou usar essa árvore binária mesmo. Muito boa idéia, e vai me poupar trabalho!

Pode me dar um exemplinho de 5 linhas de como usar TreeMap?

Olá,

Terminei de implementar o código e achei que a melhor forma de fazer seria da seguinte maneira:

1. Guardar as palavras do texto numa lista encadeada;
2. Guardar as palavras que eu quero remover numa árvore de busca binária;
3. Percorrer a lista encadeada, procurando usas palavras na árvore de busca binária. Se ela estiver lá, ele remove.

Uma lista encadeada é percorrida em O(n). A busca numa árvore binária é O(log (m)). A remoção do elemento da lista encadeanda, nesse caso, será O(1).
No final das contas, esse algoritmo será executado em O(n*log(m)).

O código fica assim:

/*Guardando palavras do texto numa lista encadeada*/
String texto = "minha casa fica no rio de janeiro"; //Exemplo de texto.
LinkedList<String> palavrasTexto = new LinkedList<String>();
String [] palavra = texto.split(" ");
for (String p : palavra) palavrasTexto.add(p);
		
/*Guardando Stopwords numa árvore de busca binária*/
String stopwords = "minha no de"; //Stopwords que queremos remover.
TreeSet<String> arvoreStopwords = new TreeSet<String>();
String [] stop = stopwords.split(" ");
for (String s : stop) arvoreStopwords.add(s);
		
/*Removendo Stopwords*/
palavrasTexto.removeAll(arvoreStopwords);

texto = "";
for (String p : palavrasTexto) texto += p + " ";
texto.trim();
		
System.out.println(texto);

Depois vou procurar fazer uns testes, pois a documentação da sun não é bem clara quanto ao método removeAll(). Implementar ele na mão do jeito correto é bem simples.

É isso mesmo. Agora li a documentação com mais calma e é isso que ele faz mesmo.

Acredito que essa seja a melhor implementação. Obrigado.

Caros,

ainda estou trabalhando com mineração de texto, e tenho mais uma dúvida que eu acredito que tenha tudo a ver com esse tópico.

Na pergunta anterior, eu falei sobre ter um texto e remover as palavras segundo uma lista de palavras. Agora eu tenho uma lista de sinônimos e palavras que eu gostaria que fossem substituidas, ao invés de removidas.

A idéia eh a seguinte:

Procurar em texto1 as palavras que estao em lista1. Se a palavra for encontrada, ele subtitue a palavra encontrada atraves de uma relação direta com uma palavra que esta na lista2. O ideal é que a procura da palavra na lista2 seja O(1).

Alguem pode me dar uma bola?

Caros,

Eu desenvolvi uma solução um pouco complicada, mas acredito que seja uma boa solução. A minha árvore de busca binária irá conter elementos de uma classe especial que eu escrevi. Segue esta classe:

public class String2 implements Comparable<String2> {
	String primeira, segunda; // A primeira palavra deve ser procurada. Se for encontrada, deve ser substituída pela segunda palavra.
	public String2(String primeira, String segunda) {
		this.primeira = primeira;
		this.segunda = segunda;
	}
	@Override
	public boolean equals(Object obj) {
		// TODO Auto-generated method stub
		if(obj == null || !(obj instanceof String2)) {
			return false;
		} else {
			return ((String2) obj).primeira.equals(this.primeira);
		}
	}
	@Override
	public int hashCode() {
		return primeira.hashCode();
	}
	@Override
	public int compareTo(String2 o) {
		return o.primeira.compareTo(primeira);
	}
	
	public String2 substitute(TreeSet<String2> tree) {
		if(tree.contains(this)) {
			primeira = tree.subSet(this, true, this, true).first().segunda;
		}
		
		return this;
	}
}

Abaixo estão alguns techos do código principal:

LinkedList<String2> listaTexto = new LinkedList<String2>(); //lista encadeada que guardará as palavras do texto
for(String p : palavrasTexto) listaTexto.add(new String2(p, null));

// árvore de busca binária que guardará seus sinônimos
TreeSet<String2> arvoreSinonimos = new TreeSet<String2>();
for(i = 0; i < sinonimos.length; i++) {
	arvoreSinonimos.add(new String2(sinonimos[i][0],sinonimos[i][1])); // os sinônimos são adicionados à árvore.
}

for (String2 p : listaTexto) {
	p.substitute(arvoreSinonimos);
}

Uma breve explicação:

O método TreeSet.contains() irá rodar uma busca que está implementada dentro da classe TreeSet, que por sua vez chama o método compareTo() (que é implementado por padrão pela classe Object, mas que qualquer clase pode sobrescreve-la). O mesmo acontece com o método equals() e o método hashCode().

O que eu fiz foi forçar a comparação dos elementos do tipo String2 para comparar apenas a primeira String (String2.primeira). O método substitute() irá procurar a primeira palavra da String2 que chamou o método dentro da árvore de busca binária e, caso encontre, irá pegar e elemento encontrado e capturar a segunda palavra deste elemento. Depois, fará a substituição.

Já tentou utilizar operações de coleções?

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;


public class TesteCollections {
	
	Set<String> wordsMapping = new TreeSet<String>();
	
	public TesteCollections() {
		//Obtem dicionario
		populateWordsMapping();
		
		List<String> lista = new ArrayList<String>();
		
		//Obtem a frase
		String comparar = "Este e um teste com alfa";
		
		//Transforma a mesma em uma coleção (ArrayList)
		String[] arrayComparar = comparar.split(" ");
		for (String wordToCompare : arrayComparar) {
			lista.add(wordToCompare);
		}
		
		//Operação de coleções
		lista.removeAll(wordsMapping);
		
		//Obtem as palavras que sobraram
		printCollection(lista);
		
	}

	/*
	 * Popula o dicionario de dados. 
	 */
	private void populateWordsMapping() {
		//As palavras estarão em ordem alfabética.
		wordsMapping.add("seta");
		wordsMapping.add("alfa");
		wordsMapping.add("beta");
		wordsMapping.add("cabeca");
		wordsMapping.add("gama");
		
		printCollection(wordsMapping);
		
		System.out.println();
	}
	
	private void printCollection(Collection<String> col){
		for (String word : col) {
			System.out.println(word);
		}
	}
	
	public static void main(String[] args) {
		new TesteCollections();
		System.exit(0);
	}

}

Augusto_:

Esta TreeMap é um Objeto que implementa uma árvore binária de busca, certo?
Quando você faz “lista.removeAll(wordsMapping);”, esta remoção respeita a busca binária para comparação dos elementos?

Não sei se poderia ser mais eficiente na busca mas, para o dicionário de palavras, vc poderia ter um Map (TreeMap) de String-Set (TreeSet) onde a chave seria a primeira letra do alfabeto e o Set seriam apenas as palavras que começem com a letra indicada na chave.

Augusto_:

Pode me dar um exemplinho de 5 linhas de como usar TreeMap?

De uma olhada no tutorial da sun sobre o assunto...
The Map Interface

import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;


public class TesteTreeMap {
	
	public TesteTreeMap() {
		Map<String, Set<String>> arvoreMap = new TreeMap<String, Set<String>>();
		
		populate(arvoreMap);
		
		Set<String> palavrasA = arvoreMap.get("a");
		for (String palavraA : palavrasA) {
			System.out.println(palavraA);
		}
		
	}

	private void populate(Map<String, Set<String>> arvoreMap) {
		TreeSet<String> treeSetA = new TreeSet<String>();
		arvoreMap.put("a", treeSetA);
		//Propositalmente fora de ordem
		treeSetA.add("aurora");
		treeSetA.add("agulha");
		treeSetA.add("alfa");
	}
	
	public static void main(String[] args) {
		new TesteTreeMap();
		System.exit(0);
	}

}

Olá, não entendo bem o que vc quer dizer sobre jeito correto.

A implementação é a seguinte: Para cada item da List ele verifica no Set se existe (é feito por busca binária e, assim que encontra o item, termina a busca). Existindo ele remove e segue para o próximo elemento.
Acho q já está feito de forma correta.

Augusto_:

Caros,

ainda estou trabalhando com mineração de texto, e tenho mais uma dúvida que eu acredito que tenha tudo a ver com esse tópico.

Na pergunta anterior, eu falei sobre ter um texto e remover as palavras segundo uma lista de palavras. Agora eu tenho uma lista de sinônimos e palavras que eu gostaria que fossem substituidas, ao invés de removidas.

A idéia eh a seguinte:

Procurar em texto1 as palavras que estao em lista1. Se a palavra for encontrada, ele subtitue a palavra encontrada atraves de uma relação direta com uma palavra que esta na lista2. O ideal é que a procura da palavra na lista2 seja O(1).

Alguem pode me dar uma bola?