Самый эффективный способ найти наиболее часто встречающиеся слова в большой последовательности слов

Question

Ввод: положительное целое число K и большой текст. Текст на самом деле можно рассматривать как последовательность слов. Поэтому нам не нужно беспокоиться о том, как разбить его на последовательность слов.
Вывод: наиболее часто встречающиеся слова K в тексте.

Мое мышление таково.

1. используйте хэш-таблицу для записи частоты всех слов при обходе всей последовательности слов. На этом этапе ключ - «слово», а значение - «частота слова». Это занимает O (N) время.

2. сортировка (слово, частота слова) пары; и ключ "частота слова". Это занимает O (n * lg (n)) время с обычным алгоритмом сортировки.

3. После сортировки мы просто берем первые K слов. Это занимает O (K) время.

Подводя итог, можно сказать, что общее время составляет O (n + n lg (n) + K) ， Поскольку K, безусловно, меньше, чем N, значит, на самом деле это O (n lg (n)).

Мы можем улучшить это. На самом деле, мы просто хотим топ-К слов. Частота других слов не беспокоит нас. Итак, мы можем использовать «частичную сортировку кучи». Для шагов 2) и 3) мы не просто делаем сортировку. Вместо этого мы изменим его на

2 ') построить кучу (слово, частота слова) пары с "частотой слова" в качестве ключа. Требуется O (n) время, чтобы построить кучу;

3 ') извлеките верхние слова K из кучи. Каждое извлечение является O (LG (N)). Итак, общее время O (k * lg (n)).

Подводя итог, можно сказать, что это решение стоит времени O (n + k * lg (n)).

Это только моя мысль. Я не нашел способ улучшить шаг 1).
Я надеюсь, что некоторые эксперты по поиску информации смогут пролить больше света на этот вопрос.

Answer 1

**

C ++ 11 Реализация вышеуказанной мысли

**

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {

    unordered_map<int,int> map;
    for(int num : nums){
        map[num]++;
    }

    vector<int> res;
    // we use the priority queue, like the max-heap , we will keep (size-k) smallest elements in the queue
    // pair<first, second>: first is frequency,  second is number 
    priority_queue<pair<int,int>> pq; 
    for(auto it = map.begin(); it != map.end(); it++){
        pq.push(make_pair(it->second, it->first));

        // onece the size bigger than size-k, we will pop the value, which is the top k frequent element value 

        if(pq.size() > (int)map.size() - k){
            res.push_back(pq.top().second);
            pq.pop();
        }
    }
    return res;

}

};

Answer 2

В этих ситуациях я рекомендую использовать встроенные функции Java. Так как они уже хорошо проверены и стабильны. В этой задаче я нахожу повторения слов с помощью структуры данных HashMap. Затем я помещаю результаты в массив объектов. Я сортирую объект по Arrays.sort () и печатаю первые k слов и их повторений.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class TopKWordsTextFile {

    static class SortObject implements Comparable<SortObject>{

        private String key;
        private int value;

        public SortObject(String key, int value) {
            super();
            this.key = key;
            this.value = value;
        }

        @Override
        public int compareTo(SortObject o) {
            //descending order
            return o.value - this.value;
        }
    }


    public static void main(String[] args) {
        HashMap<String,Integer> hm = new HashMap<>();
        int k = 1;
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("words.in")));

            String line;
            while ((line = br.readLine()) != null) {
                // process the line.
                //System.out.println(line);
                String[] tokens = line.split(" ");
                for(int i=0; i<tokens.length; i++){
                    if(hm.containsKey(tokens[i])){
                        //If the key already exists
                        Integer prev = hm.get(tokens[i]);
                        hm.put(tokens[i],prev+1);
                    }else{
                        //If the key doesn't exist
                        hm.put(tokens[i],1);
                    }
                }
            }
            //Close the input
            br.close();
            //Print all words with their repetitions. You can use 3 for printing top 3 words.
            k = hm.size();
            // Get a set of the entries
            Set set = hm.entrySet();
            // Get an iterator
            Iterator i = set.iterator();
            int index = 0;
            // Display elements
            SortObject[] objects = new SortObject[hm.size()];
            while(i.hasNext()) {
                Map.Entry e = (Map.Entry)i.next();
                //System.out.print("Key: "+e.getKey() + ": ");
                //System.out.println(" Value: "+e.getValue());
                String tempS = (String) e.getKey();
                int tempI = (int) e.getValue();
                objects[index] = new SortObject(tempS,tempI);
                index++;
            }
            System.out.println();
            //Sort the array
            Arrays.sort(objects);
            //Print top k
            for(int j=0; j<k; j++){
                System.out.println(objects[j].key+":"+objects[j].value);
            }


        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

Для получения дополнительной информации, пожалуйста, посетите https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java. Я надеюсь, что это помогает.

Answer 3

Самый простой код для получения наиболее часто встречающегося слова.

 function strOccurence(str){
    var arr = str.split(" ");
    var length = arr.length,temp = {},max; 
    while(length--){
    if(temp[arr[length]] == undefined && arr[length].trim().length > 0)
    {
        temp[arr[length]] = 1;
    }
    else if(arr[length].trim().length > 0)
    {
        temp[arr[length]] = temp[arr[length]] + 1;

    }
}
    console.log(temp);
    var max = [];
    for(i in temp)
    {
        max[temp[i]] = i;
    }
    console.log(max[max.length])
   //if you want second highest
   console.log(max[max.length - 2])
}

Answer 4

Это интересная идея для поиска, и я мог найти эту статью, связанную с Top-K https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf

Также есть реализация этого здесь .

Answer 5

Постарайтесь придумать особую структуру данных для решения такого рода проблем. В этом случае особый вид дерева, например три, для хранения строк определенным образом, очень эффективен. Или второй способ создать собственное решение, например, подсчет слов. Я предполагаю, что этот ТБ данных будет на английском языке, тогда у нас будет около 600 000 слов в общем, так что будет возможно хранить только эти слова и подсчитывать, какие строки будут повторяться + этому решению потребуется регулярное выражение для устранения некоторых специальных символов. Первое решение будет быстрее, я уверен.

http://en.wikipedia.org/wiki/Trie

Answer 6

Я просто нахожу другое решение этой проблемы. Но я не уверен, что это правильно. Решение:

1. Используйте хэш-таблицу для записи частоты всех слов T (n) = O (n)
2. Выберите первые k элементов хеш-таблицы и восстановите их в одном буфере (пространство которого = k). T (n) = O (k)
3. Каждый раз, во-первых, сначала нам нужно найти текущий элемент min буфера и просто сравнить один за другим элемент min буфера с (n - k) элементами хэш-таблицы. Если элемент хеш-таблицы больше, чем этот минимальный элемент буфера, то отбросьте минимальный текущий буфер и добавьте элемент хеш-таблицы. Таким образом, каждый раз, когда мы находим минимальное значение в буфере, нужно T (n) = O (k), а для обхода всей хеш-таблицы нужно T (n) = O (n - k). Таким образом, сложность всего времени для этого процесса составляет T (n) = O ((n-k) * k).
4. После обхода всей хеш-таблицы результат находится в этом буфере.
5. Вся сложность по времени: T (n) = O (n) + O (k) + O (kn - k ^ 2) = O (kn + n - k ^ 2 + k). Так как, к действительно меньше, чем п в целом. Таким образом, для этого решения временная сложность составляет T (n) = O (kn) . Это линейное время, когда k действительно мало. Это правильно? Я действительно не уверен.

Answer 7

Я тоже боролся с этим и вдохновился @aly. Вместо последующей сортировки мы можем просто сохранить предварительно отсортированный список слов (List<Set<String>>), и слово будет в наборе в позиции X, где X - текущий счетчик слова. В общем, вот как это работает:

1. для каждого слова, сохраните его как часть карты его появления: Map<String, Integer>.
2. затем, основываясь на количестве, удалите его из предыдущего набора и добавьте его в новый набор.

Недостатком этого списка может быть большой - его можно оптимизировать с помощью TreeMap<Integer, Set<String>> - но это добавит некоторые накладные расходы. В конечном итоге мы можем использовать сочетание HashMap или нашей собственной структуры данных.

код

public class WordFrequencyCounter {
    private static final int WORD_SEPARATOR_MAX = 32; // UNICODE 0000-001F: control chars
    Map<String, MutableCounter> counters = new HashMap<String, MutableCounter>();
    List<Set<String>> reverseCounters = new ArrayList<Set<String>>();

    private static class MutableCounter {
        int i = 1;
    }

    public List<String> countMostFrequentWords(String text, int max) {
        int lastPosition = 0;
        int length = text.length();
        for (int i = 0; i < length; i++) {
            char c = text.charAt(i);
            if (c <= WORD_SEPARATOR_MAX) {
                if (i != lastPosition) {
                    String word = text.substring(lastPosition, i);
                    MutableCounter counter = counters.get(word);
                    if (counter == null) {
                        counter = new MutableCounter();
                        counters.put(word, counter);
                    } else {
                        Set<String> strings = reverseCounters.get(counter.i);
                        strings.remove(word);
                        counter.i ++;
                    }
                    addToReverseLookup(counter.i, word);
                }
                lastPosition = i + 1;
            }
        }

        List<String> ret = new ArrayList<String>();
        int count = 0;
        for (int i = reverseCounters.size() - 1; i >= 0; i--) {
            Set<String> strings = reverseCounters.get(i);
            for (String s : strings) {
                ret.add(s);
                System.out.print(s + ":" + i);
                count++;
                if (count == max) break;
            }
            if (count == max) break;
        }
        return ret;
    }

    private void addToReverseLookup(int count, String word) {
        while (count >= reverseCounters.size()) {
            reverseCounters.add(new HashSet<String>());
        }
        Set<String> strings = reverseCounters.get(count);
        strings.add(word);
    }

}

Answer 8

Я считаю, что эту проблему можно решить с помощью алгоритма O (n). Мы могли бы сделать сортировку на лету. Другими словами, сортировка в этом случае является подзадачей традиционной проблемы сортировки, поскольку при каждом обращении к хеш-таблице только один счетчик увеличивается на единицу. Первоначально список сортируется, так как все счетчики равны нулю. Поскольку мы продолжаем увеличивать счетчики в хеш-таблице, мы ведем учет другого массива хеш-значений, упорядоченного по частоте, следующим образом. Каждый раз, когда мы увеличиваем счетчик, мы проверяем его индекс в ранжированном массиве и проверяем, превышает ли его счет его предшественник в списке. Если это так, мы поменяем эти два элемента. Таким образом, мы получаем решение, которое не больше O (n), где n - количество слов в исходном тексте.

Answer 9

Предположим, у нас есть последовательность слов «ad», «ad», «boy», «big», «bad», «com», «come», «cold». И К = 2. как вы упомянули «разделение по первой букве слов», мы получили ("ad", "ad") ("boy", "big", "bad") ("com" "come" "cold") msgstr "затем разделить самый большой набор из нескольких слов, используя следующий символ, пока у вас не будет k наборов из одного слова." он разделит («мальчик», «большой», «плохой») («com», «пришел», «холодный»), первый раздел («ad», «ad») пропущен, тогда как «ad» фактически самое частое слово.

Возможно, я неправильно понимаю вашу мысль. Можете ли вы подробно описать процесс разделения?