Листинг 15.1. Формирование списка используемых в документе слов
1nt mai п (void)
{ set<stnng> S.
set<string> iterator j.
string t.
whi1e (cin >> t)
S.insert(t) . for (j = S begin() : j != S end(). ++j) cout << *j << "\n". return 0:}
Цикл while считывает входные данные и помещает слова в набор S (по спецификации STL набор не может содержать одинаковых элементов). В цикле for мы перебираем элементы набора и выводим их в лексикографическом порядке. Эта программа элегантна и достаточно эффективна (подробнее об эффективности мы поговорим позже).
В следующей задаче нам нужно будет подсчитать количество повторений слова в документе (составить частотный словарь). В табл. 15.1 приведены самые часто встречающиеся слова в Библии короля Иакова , отсортированные в порядке убывания частоты.
Таблица 15.1. Частотный словарь Библии
the 62053 shall 9756 they 6890
and 38546 he 9506 be 6672
of 34375 unto 8929 is 6595
to 13352 I 8699 with 5949
And 12734 his 8352 not 5840
that 12428 a 7940 ail 5238
in 12154 for 7139 thou 4629
Почти 8% из 789 616 слов книги — это слово the. По нашему определению «слова», слова And и and считаются одним и тем же словом.
Эти данные были получены с помощью приведенной в листинге 15.2 программы на C++, также использующей стандартную библиотеку шаблонов, а именно функцию тар — для сопоставления счетчика каждой строке.
Листинг 15.2„ Программа формирования частотного словаря
int main(void )
{ map<stn ng , i nt> M. map<stnng. int> iterator j. string t, while (cin >> t)
M[t]++,
for (j = M begin(). j 1= M end(), ++j)
cout << j->first << " " << j->second << ’Лп" ret urn 0 ,}
В цикле while все слова из t помещаются в таблицу М. При этом одновременно увеличиваются соответствующие счетчики, изначально инициализируемые нулями. В цикле for осуществляется перебор слов и вывод их (first) вместе со счетчиками (second).
Эта программа на C++ проста, ясна и эффективна. На моем компьютере она обрабатывает текст Библии за 7,6 секунды. Примерно 2,4 секунды уходит на считывание файла, 4,9 секунды на вставку слов и 0,3 секунды на вывод результатов.
счетчик
Время работы может быть уменьшено с помощью самостоятельно построенной хэш-таблицы. В узле таблицы будет находиться указатель на слово, счетчик повторений слова и указатель на следующий узел. На рис. 15.1 изображена такая таблица после помещения в нее строк in, the и in, в той маловероятной ситуации, когда функция хэширования даст для всех трех строк одно и то же значение 1:
корзина
Опубликовал vovan666
April 17 2013 00:04:37 ·
0 Комментариев ·
3430 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
