Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Алексей9814
0 / 0 / 0
Регистрация: 08.01.2015
Сообщений: 1
1

Хеш-таблицы, сгенерировать список различных слов в тексте (с количеством вхождений их в этот текст)

08.01.2015, 20:01. Просмотров 446. Ответов 1
Метки нет (Все метки)

Напишите компьютерную программу которая использует хеширование
для следующей задачи. Имеется текст на естественном языке. Требует-
ся сгенерировать список различных слов в тексте (с количеством вхож-
дений их в этот текст). Внесите в программ}' необходимые счетчики
для сравнения эмпирической эффективности хеширования с соответ-
ствующими теоретическими результатами.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2015, 20:01
Ответы с готовыми решениями:

Вывести список слов в порядке убывания количества вхождений слов
Доброго времени суток. Задание такое: вывести на стандартный выходной поток...

Определить в тексте предложение с максимальным количеством слов
Определить в тексте предложение с максимальным количеством слов. Вывести его на...

Определить в тексте предложение с максимальным количеством слов
Определить в тексте предложение с максимальным количеством слов. Вывести его на...

Подсчитать количество вхождений всех слов в текст
Вывести все слова и рядом количество их вхождений в текст, предусмотреть, чтобы...

поправьте меня (Определите, сколько различных слов содержится в тексте)
Во входном файле (вы можете читать данные из файла input.txt) записан текст....

1
grikukan
62 / 62 / 54
Регистрация: 23.09.2012
Сообщений: 212
08.01.2015, 21:28 2
Алексей9814,
Ну вот моя более-менее адекватная реализация хеш-таблицы для этой задачи

Ну а сам алгоритм такой:
1)Возьмем очередное слово из текста
2) Если оно уже есть в хеш-таблице, то идем в пункт 1, иначе дальше
3) Добавляем это слово в хеш-таблицу
4) Добавляем его в какой-нибудь vector<string> ans где храним ответ.

Что касается оценок:
Если мы не используем хеш-таблицу, то на добавление нам потребуется O(сумма длин всех добавленных строк), а с хеш-таблицей амортизированно за O(1). Амортизированная оценка возникает из-за коллизии хешей.

Итог:
заведем 2 переменные: stupid и smart(оценки без таблицы и с ней). При каждом добавлении добавим к stupid сумму длин всех добавленных строк, а к smart (длина_текущего_слова*сколько_раз_пришле_не_туда_в_таблице). Это довольно неплохо покажет сложность.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.01.2015, 21:28

Дан файл, содержащий текст. Сколько слов в тексте? Сколько цифр в тексте?
Дан файл, содержащий текст. Сколько слов в тексте? Сколько цифр в тексте?...

Дан файл, содержащий текст. Сколько слов в тексте? Сколько цифр в тексте?
Здравствуйте, мне вот задание дали. Подскажите алгоритм решения, а то я не...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru