Как получить N наиболее часто встречающихся слов в данном тексте, отсортированных от максимального к минимальному?

Question

Мне дали большой текст в качестве ввода. Я сделал HashMap, в котором каждое отдельное слово хранится в качестве ключа, и сколько раз встречается как значение (целое число).

Теперь мне нужно создать метод mostOften(int k):List, который возвращает List, который дает первые k-слова, от максимального числа вхождений до min количества вхождений (в порядке убывания), используя HashMap, который я создал ранее. Проблема в том, что когда 2 слова имеют одинаковое количество вхождений, они должны быть отсортированы по алфавиту.

Первая мысль, которая пришла мне в голову, состояла в том, чтобы поменять местами ключи и значения заданного HashMap, и поместить его в TreeMap, а TreeMap отсортирует слова по ключу (Integer - номер вхождения слова), а затем просто вытолкнет последний / первые K-записи из TreeMap.

Но я столкнусь наверняка, когда количество 2 или 3 слов будет одинаковым. Я буду сравнивать слова в алфавитном порядке, но какое целое число я должен указать в качестве ключа для второго слова.

Есть идеи, как это реализовать, или другие варианты?

Answer 1

Вот решение, с которым я приду.

1. Сначала вы создаете класс MyWord который может хранить String значение слова и количество появлений.
2. Вы реализуете Comparable интерфейс для этого класса для сортировки по вхождениям сначала, а затем по алфавиту, если число вхождений одинаково
3. Затем для наиболее часто используемого метода вы создаете новый List из MyWord из вашего оригинала map, Вы добавляете записи этого в свой List
4. Вы сортируете этот список
5. Вы берете k-первых элементов этого списка, используя subList
6. Вы добавляете те Strings к List<String> и ты вернешь это

---

public class Test {
    public static void main(String [] args){
        Map<String, Integer> m = new HashMap<>();
        m.put("hello",5);
        m.put("halo",5);
        m.put("this",2);
        m.put("that",2);
        m.put("good",1);
        System.out.println(mostOften(m, 3));
    }

    public static List<String> mostOften(Map<String, Integer> m, int k){
        List<MyWord> l = new ArrayList<>();
        for(Map.Entry<String, Integer> entry : m.entrySet())
            l.add(new MyWord(entry.getKey(), entry.getValue()));

        Collections.sort(l);
        List<String> list = new ArrayList<>();
        for(MyWord w : l.subList(0, k))
            list.add(w.word);
        return list;
    }
}

class MyWord implements Comparable<MyWord>{
    public String word;
    public int occurence;

    public MyWord(String word, int occurence) {
        super();
        this.word = word;
        this.occurence = occurence;
    }

    @Override
    public int compareTo(MyWord arg0) {
        int cmp = Integer.compare(arg0.occurence,this.occurence);
        return cmp != 0 ? cmp : word.compareTo(arg0.word);
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + occurence;
        result = prime * result + ((word == null) ? 0 : word.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        MyWord other = (MyWord) obj;
        if (occurence != other.occurence)
            return false;
        if (word == null) {
            if (other.word != null)
                return false;
        } else if (!word.equals(other.word))
            return false;
        return true;
    }   

}

Выход: [halo, hello, that]

Answer 2

Подсказки:

1. Посмотрите на Javadocs для Collections.sort методы... оба!

2. Посмотрите на Javadocs для Map.entries(),

3. Подумайте о том, как реализовать Comparator это сравнивает экземпляры класса с двумя полями, используя второе как "прерыватель связи", когда другое сравнивается как равное.

Answer 3

В дополнение к вашему Map для хранения количества слов я бы использовал PriorityQueue фиксированного размера K (с естественным порядком). Это позволит достичь O(N) сложности. Вот код, который использует этот подход:

В конструкторе мы читаем входной поток слово за словом, заполняя счетчики на карте.

В то же время мы обновляем приоритетную очередь, сохраняя ее максимальный размер = K (нам нужно подсчитать до K слов)

public class TopNWordsCounter
{

public static class WordCount
{
    String word;
    int count;

    public WordCount(String word)
    {
        this.word = word;
        this.count = 1;
    }
}

private PriorityQueue<WordCount> pq;
private Map<String, WordCount> dict;

public TopNWordsCounter(Scanner scanner)
{
    pq = new PriorityQueue<>(10, new Comparator<WordCount>()
    {
        @Override
        public int compare(WordCount o1, WordCount o2)
        {
            return o2.count-o1.count;
        }
    });
    dict = new HashMap<>();

    while (scanner.hasNext())
    {
        String word = scanner.next();

        WordCount wc = dict.get(word);
        if (wc == null)
        {
            wc = new WordCount(word);
            dict.put(word, wc);
        }

        if (pq.contains(wc))
        {
            pq.remove(wc);
            wc.count++;
            pq.add(wc);
        }
        else
        {
            wc.count++;
            if (pq.size() < 10 || wc.count >= pq.peek().count)
            {
                pq.add(wc);
            }
        }

        if (pq.size() > 10)
        {
            pq.poll();
        }
    }
}

public List<String> getTopTenWords()
{
    Stack<String> topTen = new Stack<>();
    while (!pq.isEmpty())
    {
        topTen.add(pq.poll().word);
    }
    return topTen;
}


}