2

Tenho um texto onde estou tratando várias coisas. Agora preciso pegar as 3 palavras que mais se repetem no texto inteiro. Como posso fazer isso? Qual a melhor solução?

Pensei em armazenar em uma lista mas não sei como colocar a palavra e um contador. Também não sei se seria uma forma "inteligente" de se fazer?

2 Respostas 2

4

Assumindo que você já fez o trabalho de separar o texto em palavras, a estrutura de dados que você está procurando é o java.util.Map (também conhecida como "dicionário"). A função dela é justamente mapear um objeto (a "chave") a um outro objeto (o "valor") - ou no seu caso, a palavra ao número de vezes que ela aparece.

Map<String,Integer> quantas = new HashMap<String,Integer>();

quantas.put("foo", 1); // Diz que a palavra "foo" apareceu 1 vez

int x = quantas.get("foo"); // Pega o número de vezes que ela apareceu
quantas.put("foo", x+1);    // Atualiza o valor (sobrescreve)

// Enumera todas as palavras do dicionário
for ( Map.Entry<String,Integer> par : quantas.entrySet() )
    System.out.println(par.getKey() + " apareceu " + par.getValue() + " vezes.");

Se você estiver usando o Java 8, poderá fazer isso de forma ainda mais simples, usando lambdas:

for ( String palavra : listaPalavras )
    quantas.compute(palavra, (k, v) -> v == null ? 1 : v+1);

(i.e. se a palavra não está ainda no dicionário - v == null - marque que ela apareceu 1 vez; caso contrário, incremente 1 no número de vezes que ela apareceu)

Quanto a um modo "inteligente" de achar as N palavras que mais apareceram, eu sugiro uma fila de prioridades (PriorityQueue) onde:

  • O comparador usado na criação ordene pares (palavra, nº ocorrências) pela ordem crescente do número de ocorrências;
  • Depois de criado e populado o Map quantas, você o percorre adicionando elementos a essa fila de prioridades, mantendo seu tamanho limitado ao número que você quer (i.e. remova os menores quando a fila crescer além do ponto que você quer - assim a performance do algoritmo será boa, pois evitará dele ficar comparando elementos que não interessam).

Não vou postar um exemplo completo porque <rant>mesmo as tarefas mais simples em Java levam 10x mais código que numa linguagem decente</rant>. Mas se encontrar dificuldades em usar o método acima pode perguntar que eu explico melhor. Ou, se não estiver preocupado com a performance e só quiser um método simples e direto, coloque esses pares numa lista e a ordene.

Atualização: até que não foi tão mal assim, mas caramba, que falta que uma inferência de tipos não faz...

int max = 3;

PriorityQueue<Map.Entry<String,Integer>> fila = 
    new PriorityQueue<Map.Entry<String,Integer>>(max+1, new Comparator<Map.Entry<String,Integer>>() {
        public int compare(Map.Entry<String,Integer> a, Map.Entry<String,Integer> b) {
            return a.getValue() < b.getValue() ? -1 :
                   a.getValue() > b.getValue() ? 1 :
                   a.getKey().compareTo(b.getKey()); // Desempate
        }
    });

for ( Map.Entry<String,Integer> entry : quantas.entrySet() ) {
    fila.add(entry);
    if ( fila.size() > max )
        fila.poll(); // Remove o menor
}
10
  • 1
    @Pacíficão Isso mesmo. E não precisa colocar um literal, pode ser uma variável também: String palavra = "bar"; int x = quantas.get(palavra);. Só é preciso ter cuidado se a palavra ainda não existe no dicionário - o resultado do get será null (e provocará um NullPointerException ao fazer o cast pra int). Por isso pode ser bom testar antes se a palavra já está lá (if ( quantas.containsKey(palavra) ) { ... }) e, se não estiver, colocá-la. A segunda parte também está certa - seja qual for o valor de x, você pode fazer uma operação com ele e salvar o resultado de volta no Map.
    – mgibsonbr
    Commented 10/09/2014 às 20:02
  • 1
    @Pacíficão Sim, funciona... Veja um exemplo no ideone
    – mgibsonbr
    Commented 12/09/2014 às 2:27
  • 1
    Se você preencheu o Map, então você tem uma coleção de Map.Entry (i.e. pares de String e Integer). Para pegar as 3 palavras que mais aparecem, bastaria ordenar uma lista ou array de Map.Entry de modo crescente pelo Integer, e pegar os 3 últimos elementos, mas isso é meio que um desperdício, pois ordenar é n*log(n) e você vai jogar fora a maior parte dos elementos. A ideia da fila de prioridades é justamente eliminar esse desperdício. Você adiciona 3 elementos nela, depois a cada elemento novo que você adicionar você remove o menor. Exemplo no ideone
    – mgibsonbr
    Commented 24/09/2014 às 1:23
  • 1
    @Pacíficão Coloque numa lista e ordene. Ou - se quiser reaproveitar o comparador já escrito - ordene em ordem crescente mesmo e depois inverta. Atualizei o exemplo. Se tiver mais dúvidas, sugiro abrir uma nova pergunta, antes que esta se torne uma "pergunta camaleão"... :P
    – mgibsonbr
    Commented 24/09/2014 às 13:57
  • 1
    @Pacíficão Esse número não é obrigatório, ele diz qual é a capacidade inicial da fila. Como sabemos que o máximo de elementos que ela conterá será 4 (os 3 que você quer e mais 1 que você está testando contra todos os outros) então colocar esse valor garante que terá "espaço" suficiente pra eles [sem a estrutura de dados ter que se redimensionar para acomodar outros] e não desperdiça memória, por só alocar o espaço que realmente será precisado. É uma micro-otimização, e normalmente nem seria necessária, mas como o construtor que recebe um Comparator pede esse parâmetro, eu dei o mais indicado
    – mgibsonbr
    Commented 25/09/2014 às 14:23
2
  • Crie um HashMap de String e inteiros varra o texto adicionando palavras ao mapa caso não estejam no mesmo.

    A vantagem do mapa é justamente o fato de ser uma estrutura que opera com chaves (neste caso as palavras) e com valores (inteiros).
    Desta forma é só incrementar o valor, caso o mesmo já estiver no mapa.

  • Verifique entre todas as entradas do mapa quais as que possuem a maior frequência.

Código exemplo:

import java.util.HashMap;
import java.util.Map;

public class FreqPalavra {
    private static final String LOREM_IPSUM = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Donec a diam lectus. Sed sit amet ipsum mauris. Maecenas congue ligula ac quam viverra nec consectetur ante hendrerit. Donec et mollis dolor. Praesent et diam eget libero egestas mattis sit amet vitae augue. Nam tincidunt congue enim, ut porta lorem lacinia consectetur. Donec ut libero sed arcu vehicula ultricies a non tortor. Lorem ipsum dolor sit amet, consectetur adipiscing elit. Aenean ut gravida lorem. Ut turpis felis, pulvinar a semper sed, adipiscing id dolor. Pellentesque auctor nisi id magna consequat sagittis. Curabitur dapibus enim sit amet elit pharetra tincidunt feugiat nisl imperdiet. Ut convallis libero in urna ultrices accumsan. Donec sed odio eros. Donec viverra mi quis quam pulvinar at malesuada arcu rhoncus. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. In rutrum accumsan ultricies. Mauris vitae nisi at sem facilisis semper ac in est."
            + "Vivamus fermentum semper porta. Nunc diam velit, adipiscing ut tristique vitae, sagittis vel odio. Maecenas convallis ullamcorper ultricies. Curabitur ornare, ligula semper consectetur sagittis, nisi diam iaculis velit, id fringilla sem nunc vel mi. Nam dictum, odio nec pretium volutpat, arcu ante placerat erat, non tristique elit urna et turpis. Quisque mi metus, ornare sit amet fermentum et, tincidunt et orci. Fusce eget orci a orci congue vestibulum. Ut dolor diam, elementum et vestibulum eu, porttitor vel elit. Curabitur venenatis pulvinar tellus gravida ornare. Sed et erat faucibus nunc euismod ultricies ut id justo. Nullam cursus suscipit nisi, et ultrices justo sodales nec. Fusce venenatis facilisis lectus ac semper. Aliquam at massa ipsum. Quisque bibendum purus convallis nulla ultrices ultricies. Nullam aliquam, mi eu aliquam tincidunt, purus velit laoreet tortor, viverra pretium nisi quam vitae mi. Fusce vel volutpat elit. Nam sagittis nisi dui."
            + "Suspendisse lectus leo, consectetur in tempor sit amet, placerat quis neque. Etiam luctus porttitor lorem, sed suscipit est rutrum non. Curabitur lobortis nisl a enim congue semper. Aenean commodo ultrices imperdiet. Vestibulum ut justo vel sapien venenatis tincidunt. Phasellus eget dolor sit amet ipsum dapibus condimentum vitae quis lectus. Aliquam ut massa in turpis dapibus convallis. Praesent elit lacus, vestibulum at malesuada et, ornare et est. Ut augue nunc, sodales ut euismod non, adipiscing vitae orci. Mauris ut placerat justo. Mauris in ultricies enim. Quisque nec est eleifend nulla ultrices egestas quis ut quam. Donec sollicitudin lectus a mauris pulvinar id aliquam urna cursus. Cras quis ligula sem, vel elementum mi. Phasellus non ullamcorper urna."
                    .replaceAll("[.,]", "");

    public static void main(String[] args) {
        Map<String, Integer> mapaFreq = new HashMap<>();
        // Cria o mapa de Frequências
        for (String palavra : LOREM_IPSUM.split("\\s+")) {
            if (!mapaFreq.containsKey(palavra)) {
                mapaFreq.put(palavra, 1);
            } else {
                mapaFreq.put(palavra, 1 + mapaFreq.get(palavra));
            }
        }
        // Arrays para armazenar os 3 valores mais frequentes.
        String[] palavrasMaisFrequentes = new String[3];
        int[] freqPalavras = new int[3];
        //Percorre todos os valores do mapa
        for (Map.Entry<String, Integer> entrada : mapaFreq.entrySet()) {
            //Se achar algo mais frequente que a primeira posição
            if (entrada.getValue() >= freqPalavras[0]) {
                freqPalavras[0] = entrada.getValue();
                palavrasMaisFrequentes[0] = entrada.getKey();

            } else {
                if (entrada.getValue() >= freqPalavras[1]) {
                    freqPalavras[1] = entrada.getValue();
                    palavrasMaisFrequentes[1] = entrada.getKey();
                } else if (entrada.getValue() >= freqPalavras[2]) {
                    freqPalavras[2] = entrada.getValue();
                    palavrasMaisFrequentes[2] = entrada.getKey();
                }
            }
//          System.out.println(entrada.getKey() + "/" + entrada.getValue()); imprime todo o mapa
        }
        for (int i = 0; i < freqPalavras.length; i++) {
            System.out.println(i + 1 + " palavra: " + palavrasMaisFrequentes[i]
                    + " \nFrequência: " + freqPalavras[i]
                    + "\n------------------------\n");
        }

    }
}

Pode ver este exemplo rodando no ideone.

Observação

Para efeito de simplificação o código acima não repassa o valor para as demais posições do array (o que é um erro de lógica, pois se um termo é mais frequente ele deveria ir atualizando o array em cascata)

  • Exemplo:
freqPalavras[]     |   palavrasMaisFrequentes[]
      13           |          "estouro"
      11           |          "da"
      09           |          "pilha"

Se uma palavra "batman" com frequência 14 aparecer a nova ordem deveria ser:

freqPalavras[]     |   palavrasMaisFrequentes[]
      14           |          "batman"
      13           |          "estouro"
      11           |          "da"

Mas no programa acima ficaria:

freqPalavras[]     |   palavrasMaisFrequentes[]
      14           |          "batman"
      11           |          "da"
      09           |          "pilha"
1
  • 2
    "Para efeito de simplificação o código acima..." é justamente por essa complexidade que uma lista de prioridades quebraria um galho... se ao menos fosse mais fácil de usá-la. Mas pelo que eu vejo, Java não possui uma estrutura de dados genérica para representar pares [ordenáveis]. De todo modo, +1 pelo exemplo completo, apesar dessa limitação.
    – mgibsonbr
    Commented 9/09/2014 às 3:14

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .