Алгоритм: лучший способ вычислить частоты списка слов

Этот вопрос на самом деле довольно прост, но я хотел бы услышать некоторые идеи, прежде чем перейти к программированию. Учитывая файл со словом в каждой строке,calculating most n frequent numbers.

 Первая и, к сожалению, единственная вещь, которая всплывает в моей памяти, - это использоватьstd::map, Я знаю, что коллеги по С ++ скажут, чтоunordered_map было бы очень разумно.

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

Есть идеи?

 Ali18 апр. 2012 г., 01:53
@Jesse Спасибо за комментарий и рассчитать их в кратчайшие сроки.
 Jesse Good18 апр. 2012 г., 01:53
Хотите узнать, как лучше хранить частоты или рассчитать их? Я в замешательстве.
 Benjamin Lindley18 апр. 2012 г., 01:55
@Jesse:map<string,int>
 Ali18 апр. 2012 г., 01:56
Я думаю, что использовал бы это так. карта [слово] ++; Таким образом, индексом будет слово, а счетчиком будет его частота.
 Jesse Good18 апр. 2012 г., 01:54
Что значитstd::mapи т.д. связаны с расчетом частоты?

Ответы на вопрос(5)

я мог быnot начать сstd::map (или жеunordered_map) если бы у меня был большой выбор (хотя я не знаю, какие другие ограничения могут применяться).

Здесь у вас есть два элемента данных, и один из них используется в качестве ключевой части времени, а другой - в качестве ключевой другой части времени. Для этого вы, вероятно, хотите что-то вродеBoost Bimap или возможноУвеличить мультииндекс.

Вот общая идея использования Bimap:

#include <boost/bimap.hpp>
#include <boost/bimap/list_of.hpp>
#include <iostream>

#define elements(array) ((sizeof(array)/sizeof(array[0])))

class uint_proxy {
    unsigned value;
public:
    uint_proxy() : value(0) {}
    uint_proxy& operator++() { ++value; return *this; }
    unsigned operator++(int) { return value++; }
    operator unsigned() const { return value; }
};

int main() {    
    int b[]={2,4,3,5,2,6,6,3,6,4};

    boost::bimap<int, boost::bimaps::list_of<uint_proxy> > a;

    // walk through array, counting how often each number occurs:
    for (int i=0; i<elements(b); i++) 
        ++a.left[b[i]];

    // print out the most frequent:
    std::cout << a.right.rbegin()->second;
}

На данный момент я только распечатал наиболее частое число, но итерация N раз для распечатки наиболее частого N довольно тривиальна.

 18 апр. 2012 г., 04:36
Элегантное решение. Мотивирует меня использовать бимапы в будущем. Тем не менее, я думаю, что ему не хватаетa.right.sort() до окончательной распечатки. По умолчанию элементы в представлении списка будут отсортированы по порядку вставки (а не по значению), см.here.

Есть много разных подходов к этому вопросу. Наконец, это будет зависеть от сценария и других факторов, таких как размер файла (если файл имеет миллиард строк), тоHashMapне будет эффективным способом сделать это. Вот несколько вещей, которые вы можете сделать в зависимости от вашей проблемы:

If you know that the number of unique words are very limited, you can use a TreeMap or in your case std::map. If the number of words are very large then you can build a trie and keep count of various words in another data structure. This could be a heap (min/max depends on what you want to do) of size n. So you don't need to store all the words, just the necessary ones.
 Ali18 апр. 2012 г., 01:57
Спасибо за альтернативный подход! Я буду помнить об этих предложениях.

Лучшая структура данных для этой задачи - Trie:

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

Это превзойдет хэш-таблицу для подсчета строк.

 18 апр. 2012 г., 05:46
@jogojapan: На странице, на которую я ссылаюсь, есть графики эффективности со сравнениями. Таблицы символов хранят отдельные токены и обычно хранятся как попытки, в качестве примера см. Boost :: spirit.
 18 апр. 2012 г., 04:45
Три может быть очень хорошим дляlongest-match поиск в словаре, то есть совпадения, которые не ограничиваются отдельными токенами, но могут продолжаться по неопределенному количеству токенов. Но для поиска и вставкиsingle токены, по одному, хорошо реализованный хеш (включаяstd::unordered_map) являетсяmuch быстрее в моем опыте. У вас есть данные, подтверждающие вашу претензию?
 18 апр. 2012 г., 06:58
Хорошо, признал.nedtries особенно впечатляют. Но следует также отметить, что (насколько я понимаю) эти тесты предназначены для маленьких ключей («размер указателя»), и даже там хэш обеспечивает сопоставимую производительность, если у вас более 10 тыс. Записей. Тем не менее, я признаю, что было бы интересно увидеть сравнение хешей с недтри для токенов естественного языка и (особенно для целей подсчета частоты).

Если вас интересуют только самые популярные N слов, и вам не нужно, чтобы они были точными, то есть очень умная структура, которую вы можете использовать. Я слышал об этом через Уди Манбера, он работает следующим образом:

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

Это звучит просто, и ничто в алгоритме не создает впечатление, что он даст что-то полезное, но для типичных реальных данных он, как правило, работает очень хорошо. Обычно, если вы хотите отслеживать N лучших вещей, вы можете создать эту структуру с емкостью 10 * N, так как в ней будет много пустых значений. Используя Библию короля Иакова в качестве входных данных, вот что эта структура перечисляет как наиболее часто встречающиеся слова (в произвольном порядке):

0 : in
1 : And
2 : shall
3 : of
4 : that
5 : to
6 : he
7 : and
8 : the
9 : I

И вот десятка самых распространенных слов (по порядку):

0 : the ,  62600
1 : and ,  37820
2 : of ,  34513
3 : to ,  13497
4 : And ,  12703
5 : in ,  12216
6 : that ,  11699
7 : he ,  9447
8 : shall ,  9335
9 : unto ,  8912

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

Вот реализация topN, которую я использовал, написанная на Go:

type Event string

type TopN struct {
  events  []Event
  counts  []int
  current int
  mapped  map[Event]int
}
func makeTopN(N int) *TopN {
  return &TopN{
    counts: make([]int, N),
    events: make([]Event, N),
    current: 0,
    mapped: make(map[Event]int, N),
  }
}

func (t *TopN) RegisterEvent(e Event) {
  if index, ok := t.mapped[e]; ok {
    t.counts[index]++
  } else {
    if t.counts[t.current] == 0 {
      t.counts[t.current] = 1
      t.events[t.current] = e
      t.mapped[e] = t.current
    } else {
      t.counts[t.current]--
      if t.counts[t.current] == 0 {
        delete(t.mapped, t.events[t.current])
      }
    }
  }
  t.current = (t.current + 1) % len(t.counts)
}

Given a file with a word in each line, calculating most n frequent numbers. ... I've searched it over the internet and read that hash table and a priority queue might provide an algorithm with O(n)

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

Могут быть вероятностные приближенные алгоритмы с сублинейной памятью.

 Ali18 апр. 2012 г., 02:03
Я имел в виду как линейный да, спасибо за ответ!

Ваш ответ на вопрос