Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > Технологии > Общие вопросы по программированию, компьютерным наукам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Ответ
 
Опции темы
Старый 21.05.2012, 20:08   #1
vedro-compota
любитель-далеко не
Профессионал
 
Аватар для vedro-compota
 
Регистрация: 13.04.2010
Адрес: Россия. Славный город Воронеж )
Сообщений: 1,155
Репутация: 639
По умолчанию Оптимальный алгоритм - получить список из N наиболее часто встречающихся элементов

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

Если кто когда-то уже размышлял над проблемой указанной в заголовке выскажите какие-нибудь соображения по поводу решения задачи вроде следующей:
Цитата:
есть здоровенный текстовый файл - из него можно так ли иначе получить длинный массив элементов .задача: получить N наиболее часто встречающихся элементов (подразумевается, что полученный массив при решении "в лоб" обрабатывается недопустимо долго)
Насколько я понимаю - если отбросить вопрос о методе получения данных, то задача делиться на следующие подзадачи:
  • 1) Получения списка "уникальных " элементов из исходного списка
  • 2) Определение "веса " каждого элемента при повторном просмотре исходного списка
  • 3) Сортировка второго списка уникальных элементов с учётом веса

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

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

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

Заранее благодарю)
__________________
против абортов=за + жизнь;.фкн вгу;_______________________мойблг
vedro-compota вне форума   Ответить с цитированием
Старый 21.05.2012, 21:07   #2
Levsha100
Влюбленный в С++
Профессионал
 
Аватар для Levsha100
 
Регистрация: 20.07.2008
Адрес: город, которого нет.
Сообщений: 4,033
Репутация: 1376

icq: 590368735
По умолчанию

Самый простой способ это двоичное дерево, где хранится слово и число раз сколько оно встретилось. Проходим по файлу, если не нашли слово, то добаляем в дерево и счетчик ставим 1, иначе увеличиваем счетчик.
Это сбор уникальных слов и их количества.
Как найти наиболее часто встречаемые нужно подумать, но думаю нужно этим занимается при увеличении счетчика.
__________________
Смотри в корень!
use linux - be happy
Levsha100 вне форума   Ответить с цитированием
Старый 21.05.2012, 21:32   #3
Utkin
Профессионал
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Адрес: DuckBurg
Сообщений: 18,303
Репутация: 3917
По умолчанию

Ну да, мне тоже видится список образцов и частота их использования... Вариант 2. Отсортировать все слова (в смысле текст) и считать количество повторений. Но не знаю что будет быстрей... Для русского языка наверно это будет союз и
__________________
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума   Ответить с цитированием
Старый 21.05.2012, 22:11   #4
akasex
Форумчанин
 
Аватар для akasex
 
Регистрация: 31.03.2008
Адрес: Cleveland, OH
Сообщений: 179
Репутация: 64
По умолчанию

Цитата:
Сообщение от Levsha100 Посмотреть сообщение
Как найти наиболее часто встречаемые нужно подумать, но думаю нужно этим занимается при увеличении счетчика.
Maybe use a binary heap instead? http://en.wikipedia.org/wiki/Binary_heap

Последний раз редактировалось akasex; 22.05.2012 в 00:41. Причина: Added link
akasex вне форума   Ответить с цитированием
Старый 21.05.2012, 22:30   #5
Stilet
Белик Виталий :)
Профессионал
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Адрес: Украина, Донецкая область, г. Краматорск
Сообщений: 57,842
Репутация: 6832
По умолчанию

Цитата:
Самый простой способ это двоичное дерево
Это не просто самый простой, это пожалуй самый быстрый - содержать список, сортируемый по мере внесения в него данных, при этом определение места для внесения нового, еще не содержащегося слова в списке или нахождение элемента, содержащего такое слово, проводится бинарным поиском.
По-моему так свои индексы обновляют все серьезные СУБД при вставке записи.
__________________
I'm learning to live...
Stilet вне форума   Ответить с цитированием
Старый 21.05.2012, 22:49   #6
Аватар
Модератор
Заслуженный модератор
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Адрес: Северодонецк.ua
Сообщений: 18,005
Репутация: 6348
По умолчанию

Возможно поможет эта реализация http://morpher.ru/Russian/Stats.aspx
__________________
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар на форуме   Ответить с цитированием
Старый 22.05.2012, 08:42   #7
vedro-compota
любитель-далеко не
Профессионал
 
Аватар для vedro-compota
 
Регистрация: 13.04.2010
Адрес: Россия. Славный город Воронеж )
Сообщений: 1,155
Репутация: 639
По умолчанию

Цитата:
Вариант 2. Отсортировать все слова (в смысле текст) и считать количество повторений.
Utkin , придётся же выполнять сортировку строк , но для этого для каждой строки (слова) надо будет какой-то ключ сформировать - напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?
(но вообще -насколько я понимаю - это лишь конкретный способ определения "веса слова" - так как после того, как текст отсортирован - нам придётся считать повторы - после же сортировать результирующий массив и получать эти самые N значений)
Аватар, akasex благодарю за ссылки.
Levsha100 , Stilet наверное правда лучше всего что-то "бинарное"...буду смотреть.
__________________
против абортов=за + жизнь;.фкн вгу;_______________________мойблг
vedro-compota вне форума   Ответить с цитированием
Старый 22.05.2012, 09:38   #8
Utkin
Профессионал
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Адрес: DuckBurg
Сообщений: 18,303
Репутация: 3917
По умолчанию

Цитата:
напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?
Не знаю, хеши строк это отдельный вопрос Надо подумать
__________________
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума   Ответить с цитированием
Старый 22.05.2012, 20:55   #9
Stilet
Белик Виталий :)
Профессионал
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Адрес: Украина, Донецкая область, г. Краматорск
Сообщений: 57,842
Репутация: 6832
По умолчанию

Цитата:
напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?
На коллизии не боишься нарваться? Впрочем существуют методы индексации по хешам и битовым маскам (В Оракле я подобное встречал)
__________________
I'm learning to live...
Stilet вне форума   Ответить с цитированием
Старый 23.05.2012, 02:50   #10
pu4koff
Профессионал
 
Аватар для pu4koff
 
Регистрация: 22.05.2007
Сообщений: 9,442
Репутация: 3613
По умолчанию

Решил вспомнить молодость, написал на плюсах какую-то фигню, но баги вылазят, судя по результатам, но сути дела эти ошибки не должны менять.
Скачал где-то войну и мир на 3 метра, написал прогу. Она насчитала вот это:
Цитата:
Всего слов: 466023
20319: и
10223: ве
8469: нес
7850: что
5760: сн
3866: его
3705: как
3408: кt
2130: яз
2016: сказал
В диспетчере задач почти 26 метров памяти занятой показывается, а по скорости буквально секунд 5 на моём Core i3. Баги на скорость работы вряд ли повлияли, а по памяти можно еще много оптимизировать при желании.
Описываю принцип:
Слова загоняются в дерево (не помню только уже как оно называется, в разделах про поиск описывается оно). Ветви дерева - буквы слов, а листья - специальный маркер, показывающий конец слова. В общем, ветви корня дерева - первые буквы всех найденных слов. От всех этих первых букв идут уже вторых буквы этих самых слов. Если слово состоит из одной буквы, то вместо второй буквы должен быть маркер, который можно совместить со счетчиком популярности слова. Таким образом, если идти от корня к листьям, то можно прочесть все найденные слова.
Ну, а потом нужно найти N листьев этого дерева, с наибольшим счетчиком. Я сделал это через тупую рекурсию. Из STL использовал только list и его sort с merge для сортировки и объединения упорядоченных списков, соответственно.
Попробовал скопировать этот же текст несколько раз. В итоге получил 64 метра на диске, оперативки в диспетчере жрала прога столько же, а время выполнения не больше 15 секунд (основное время заняло чтение из файла и создание дерева на основе этих данных).
pu4koff вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
из текстового файл получить 5 наиболее часто встречающихся слов и число их появлений (на Delphi) sifa Помощь студентам 5 09.01.2012 18:34
в тексте слова, содержащие ровно одну из 10 наиболее часто встречающихся букв yaroslav_bondarev Паскаль 3 16.12.2011 10:11
дан текст, написать код, нахождения 10 наиболее часто встречающихся букв yaroslav_bondarev Паскаль 9 14.12.2011 22:08
Получить массив из элементов, встречающихся в исходном массиве ровно один раз без повторений Shikarmo4000 Помощь студентам 0 25.05.2010 01:27
Найти (в процентах) частоту появления каждого из m наиболее часто встречающихся элементов sk1p Паскаль 2 26.09.2008 23:57


00:44.


Powered by vBulletin® Version 3.8.8 Beta 2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru