Оптимальный алгоритм - получить список из N наиболее часто встречающихся элементов

[vedro-compota]

Друзья, приветствую всех и здравия желаю)

Если кто когда-то уже размышлял над проблемой указанной в заголовке выскажите какие-нибудь соображения по поводу решения задачи вроде следующей:

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

Насколько я понимаю - если отбросить вопрос о методе получения данных, то задача делиться на следующие подзадачи:

• 1) Получения списка "уникальных " элементов из исходного списка
• 2) Определение "веса " каждого элемента при повторном просмотре исходного списка
• 3) Сортировка второго списка уникальных элементов с учётом веса

Собственно - буду очень благодарен за любые советы комментарии по поводу задачи - как по-вашему это сделать "оптимальнее".

Особенно алгоритм сортировки .

p.s. - да - знаю, что об этом писал великий Дональд Кнут - и буду очень благодарен если вы не просто отошлёте меня к данной книги (надеюсь, что к книге))) и ещё и скажите название алгоритма (который рассматривается у Кнута) наиболее оптимального в данном случае.

Заранее благодарю)

[Levsha100]

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

[Utkin]

Ну да, мне тоже видится список образцов и частота их использования... Вариант 2. Отсортировать все слова (в смысле текст) и считать количество повторений. Но не знаю что будет быстрей... Для русского языка наверно это будет союз и

[akasex]

Сообщение от Levsha100

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

Maybe use a binary heap instead? http://en.wikipedia.org/wiki/Binary_heap

[Stilet]

Самый простой способ это двоичное дерево

Это не просто самый простой, это пожалуй самый быстрый - содержать список, сортируемый по мере внесения в него данных, при этом определение места для внесения нового, еще не содержащегося слова в списке или нахождение элемента, содержащего такое слово, проводится бинарным поиском.
По-моему так свои индексы обновляют все серьезные СУБД при вставке записи.

[Аватар]

Возможно поможет эта реализация http://morpher.ru/Russian/Stats.aspx

[vedro-compota]

Вариант 2. Отсортировать все слова (в смысле текст) и считать количество повторений.

Utkin , придётся же выполнять сортировку строк , но для этого для каждой строки (слова) надо будет какой-то ключ сформировать - напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?
(но вообще -насколько я понимаю - это лишь конкретный способ определения "веса слова" - так как после того, как текст отсортирован - нам придётся считать повторы - после же сортировать результирующий массив и получать эти самые N значений)
Аватар, akasex благодарю за ссылки.
Levsha100 , Stilet наверное правда лучше всего что-то "бинарное"...буду смотреть.

[Utkin]

напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?

Не знаю, хеши строк это отдельный вопрос Надо подумать

[Stilet]

напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?

На коллизии не боишься нарваться? Впрочем существуют методы индексации по хешам и битовым маскам (В Оракле я подобное встречал)

[pu4koff]

Решил вспомнить молодость, написал на плюсах какую-то фигню, но баги вылазят, судя по результатам, но сути дела эти ошибки не должны менять.
Скачал где-то войну и мир на 3 метра, написал прогу. Она насчитала вот это:

Всего слов: 466023
20319: и
10223: ве
8469: нес
7850: что
5760: сн
3866: его
3705: как
3408: кt
2130: яз
2016: сказал

В диспетчере задач почти 26 метров памяти занятой показывается, а по скорости буквально секунд 5 на моём Core i3. Баги на скорость работы вряд ли повлияли, а по памяти можно еще много оптимизировать при желании.
Описываю принцип:
Слова загоняются в дерево (не помню только уже как оно называется, в разделах про поиск описывается оно). Ветви дерева - буквы слов, а листья - специальный маркер, показывающий конец слова. В общем, ветви корня дерева - первые буквы всех найденных слов. От всех этих первых букв идут уже вторых буквы этих самых слов. Если слово состоит из одной буквы, то вместо второй буквы должен быть маркер, который можно совместить со счетчиком популярности слова. Таким образом, если идти от корня к листьям, то можно прочесть все найденные слова.
Ну, а потом нужно найти N листьев этого дерева, с наибольшим счетчиком. Я сделал это через тупую рекурсию. Из STL использовал только list и его sort с merge для сортировки и объединения упорядоченных списков, соответственно.
Попробовал скопировать этот же текст несколько раз. В итоге получил 64 метра на диске, оперативки в диспетчере жрала прога столько же, а время выполнения не больше 15 секунд (основное время заняло чтение из файла и создание дерева на основе этих данных).