Как получить N наиболее часто слова в заданном тексте, отсортированные от max до min?

Question

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

Теперь я должен сделать метод, называемый mostOften (интермедиат к): Список, возвращающий список, который дает первые K-слова, которые от максимального числа появления до Минимального количества возникновения (убыванию), используя 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; 
} 


}