Самый эффективный способ найти верхние K Частые слова в большой последовательности слов

Ответ 1

Это можно сделать за O (n) раз

Решение 1:

Этапы:

1. Считайте слова и хешируйте их, что приведет к структуре, подобной этой

   var hash = {
     "I" : 13,
     "like" : 3,
     "meow" : 3,
     "geek" : 3,
     "burger" : 2,
     "cat" : 1,
     "foo" : 100,
     ...
     ...
   

2. Пройдите через хеш и найдите наиболее часто используемое слово (в данном случае "foo" 100), затем создайте массив такого размера

3. Затем мы можем снова пройти по хешу и использовать количество вхождений слов в качестве индекса массива, если в индексе ничего нет, создать массив, иначе добавить его в массив. Затем мы получим массив вроде:

     0   1      2            3                  100
   [[ ],[cat],[burger],[like, meow, geek],[]...[foo]]
   

4. Затем просто обойдите массив с конца и соберите k слов.

Решение 2:

Этапы:

1. То же, что и выше
2. Используйте min heap и оставьте размер min heap равным k, и для каждого слова в хэше мы сравниваем вхождения слов с min, 1), если оно больше значения min, убираем min (если размер min куча равна к) и вставьте число в мин кучу. 2) Отдыхайте в простых условиях.
3. После обхода массива мы просто конвертируем минимальную кучу в массив и возвращаем массив.

Ответ 2

Вы не получите в целом лучшего времени исполнения, чем решение, которое вы описали. Вы должны выполнить хотя бы O (n) работу, чтобы оценить все слова, а затем O (k) дополнительную работу, чтобы найти верхние k членов.

Если ваша проблема действительно велика, вы можете использовать распределенное решение, такое как map/reduce. Пусть n работники карт подсчитывают частоты на 1/n текста, а для каждого слова посылают его одному из m редукторов, рассчитанному на основе хэша слова. Затем редукторы суммируют подсчеты. Слияние сортировки по выходам редукторов даст вам самые популярные слова в порядке популярности.

Ответ 3

Небольшая вариация на вашем решении дает алгоритм O (n), если мы не хотим ранжировать верхний K, а O (n + k * lg (k) ), если мы это сделаем. Я считаю, что обе эти границы оптимальны в пределах постоянного фактора.

Оптимизация здесь возникает снова после того, как мы просматриваем список, вставляя в хеш-таблицу. Мы можем использовать алгоритм медиан медианы, чтобы выбрать самый большой элемент Kth в списке. Этот алгоритм доказуемо O (n).

После выбора наименьшего элемента Kth мы разбиваем список вокруг этого элемента так же, как и в quicksort. Это, очевидно, также O (n). Все, что находится на "левой" стороне стержня, находится в нашей группе элементов K, поэтому мы закончили (мы можем просто выбросить все остальное по мере продвижения).

Итак, эта стратегия:

• Пройдите через каждое слово и вставьте его в хеш-таблицу: O (n)
• Выберите наименьший элемент Kth: O (n)
• Разделение вокруг этого элемента: O (n)

Если вы хотите ранжировать элементы K, просто сортируйте их с любой эффективной сортировкой сортировки по времени O (k * lg (k)), что дает общее время выполнения O (n + k * lg (k)).

Времена времени O (n) являются оптимальными в пределах постоянного фактора, потому что мы должны рассматривать каждое слово хотя бы один раз.

Времена времени O (n + k * lg (k)) также являются оптимальными, поскольку на основе сравнения нет способа сортировать k элементов меньше, чем k * lg (k).

Ответ 4

Если ваш "большой список слов" достаточно велик, вы можете просто пробовать и получать оценки. В противном случае мне нравится хеш-агрегация.

Edit:

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

Этот подход действительно разумен, если у вас так много данных, что обработка всего этого просто глупо. Если у вас всего несколько мегабайт, вы должны иметь возможность разрывать данные и рассчитывать точный ответ, не разбивая пота, а не пытаться вычислить оценку.

Ответ 5

Вы можете сократить время дальше путем разбиения на разделы с использованием первой буквы слов, а затем разбиение самого большого набора слов с использованием следующего символа до тех пор, пока у вас не будет k наборов с одним словом. Вы бы использовали sortof 256-way tree со списками частичных/полных слов на листах. Вам нужно быть очень осторожным, чтобы везде не приводить строковые копии.

Этот алгоритм O (m), где m - количество символов. Он избегает этой зависимости от k, что очень хорошо для больших k [по тому, как ваше опубликованное время работы неверно, оно должно быть O (n * lg (k)), и я не уверен, что это такое с точки зрения м].

Если вы запускаете оба алгоритма бок о бок, вы получите то, что я уверен, что это асимптотически оптимальный алгоритм O (min (m, n * lg (k))), но мой должен быть быстрее в среднем, потому что он не работает 't включать хеширование или сортировку.

Ответ 6

У вас есть ошибка в вашем описании: подсчет занимает время O (n), но сортировка принимает O (m * lg (m)), где m - количество слов unique. Обычно это намного меньше, чем общее количество слов, поэтому, вероятно, нужно просто оптимизировать, как создается хэш.

Ответ 7

Ваша проблема такая же, как и эта-  http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

Используйте Trie и min heap для эффективного решения.

Ответ 8

Если вы используете список наиболее часто встречающихся слов в тексте для любого практического k и для любого естественного langage, тогда сложность вашего алгоритма не имеет значения.

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

В качестве побочного примечания сложность фиктивного алгоритма (1. подсчитайте все 2. соберите подсчеты 3. возьмите лучшее) - это O (n + m * log (m)), где m - число разных слова в вашем тексте. log (m) много меньше (n/m), поэтому остается O (n).

Практически длинный шаг подсчитывается.

Ответ 9

• Использовать эффективную структуру данных памяти для хранения слов
• Используйте MaxHeap, чтобы найти верхние K частые слова.

Вот код

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import com.nadeem.app.dsa.adt.Trie;
import com.nadeem.app.dsa.adt.Trie.TrieEntry;
import com.nadeem.app.dsa.adt.impl.TrieImpl;

public class TopKFrequentItems {

private int maxSize;

private Trie trie = new TrieImpl();
private PriorityQueue<TrieEntry> maxHeap;

public TopKFrequentItems(int k) {
    this.maxSize = k;
    this.maxHeap = new PriorityQueue<TrieEntry>(k, maxHeapComparator());
}

private Comparator<TrieEntry> maxHeapComparator() {
    return new Comparator<TrieEntry>() {
        @Override
        public int compare(TrieEntry o1, TrieEntry o2) {
            return o1.frequency - o2.frequency;
        }           
    };
}

public void add(String word) {
    this.trie.insert(word);
}

public List<TopK> getItems() {

    for (TrieEntry trieEntry : this.trie.getAll()) {
        if (this.maxHeap.size() < this.maxSize) {
            this.maxHeap.add(trieEntry);
        } else if (this.maxHeap.peek().frequency < trieEntry.frequency) {
            this.maxHeap.remove();
            this.maxHeap.add(trieEntry);
        }
    }
    List<TopK> result = new ArrayList<TopK>();
    for (TrieEntry entry : this.maxHeap) {
        result.add(new TopK(entry));
    }       
    return result;
}

public static class TopK {
    public String item;
    public int frequency;

    public TopK(String item, int frequency) {
        this.item = item;
        this.frequency = frequency;
    }
    public TopK(TrieEntry entry) {
        this(entry.word, entry.frequency);
    }
    @Override
    public String toString() {
        return String.format("TopK [item=%s, frequency=%s]", item, frequency);
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + frequency;
        result = prime * result + ((item == null) ? 0 : item.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;
        TopK other = (TopK) obj;
        if (frequency != other.frequency)
            return false;
        if (item == null) {
            if (other.item != null)
                return false;
        } else if (!item.equals(other.item))
            return false;
        return true;
    }

}   

}

Ниже приведены модульные тесты

@Test
public void test() {
    TopKFrequentItems stream = new TopKFrequentItems(2);

    stream.add("hell");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("hero");
    stream.add("hero");
    stream.add("hero");
    stream.add("hello");
    stream.add("hello");
    stream.add("hello");
    stream.add("home");
    stream.add("go");
    stream.add("go");
    assertThat(stream.getItems()).hasSize(2).contains(new TopK("hero", 3), new TopK("hello", 8));
}

Подробнее см. этот тестовый пример

Ответ 10

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

• Вставляя себя в hashmap, держите Treeset (специфичный для java, есть реализации на каждом языке) размером 10 (k = 10), чтобы сохранить 10 самых популярных слов. До размера меньше 10, продолжайте добавлять его. Если размер равен 10, если вставленный элемент больше минимального элемента, то есть первого элемента. Если да, удалите его и вставьте новый элемент

Чтобы ограничить размер дерева, см. эта ссылка

Ответ 11

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

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

Ответ 12

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

Ответ 13

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

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

Недостатком этого является список, возможно большой - можно оптимизировать с помощью 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);
    }

}

Ответ 14

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

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

Ответ 15

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

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

Ответ 16

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

Также существует реализация здесь.

Ответ 17

Простейший код для получения наиболее часто используемого слова.

 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])
}

Ответ 18

В этих ситуациях я рекомендую использовать встроенные функции 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. Надеюсь, это поможет.

Ответ 19

**

С++ 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;

}

};