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

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

75 голосов
/ 09 октября 2008

Ввод: положительное целое число 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).
Я надеюсь, что некоторые эксперты по поиску информации смогут пролить больше света на этот вопрос.

Ответы [ 19 ]

59 голосов
/ 12 марта 2014

Это можно сделать за 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
[[ ],[ ],[burger],[like, meow, geek],[]...[foo]]

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

Решение 2:

Шаги:

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

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

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

13 голосов
/ 26 декабря 2008

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

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

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

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

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

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

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

Граница времени O (n + k * lg (k)) также является оптимальной, поскольку не существует способа сортировки k элементов за менее чем k * lg (k) времени.

8 голосов
/ 09 октября 2008

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

Редактировать

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

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

2 голосов
/ 15 марта 2016
  1. Использование эффективной структуры памяти для хранения слов
  2. Используйте MaxHeap, чтобы найти наиболее часто встречающиеся слова.

Вот код 

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

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

2 голосов
/ 06 мая 2015

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

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

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

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

2 голосов
/ 25 января 2015

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

Используйте Trie и минимальную кучу, чтобы эффективно ее решить.

2 голосов
/ 09 октября 2008

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

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

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

2 голосов
/ 26 декабря 2008

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

1 голос
/ 11 апреля 2017

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

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

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

Страница:
...