Skip to content

One of the types of tasks that the programmer faces quite often. Here is one of the optimal algorithms for solving it.

License

Notifications You must be signed in to change notification settings

averov90/Word-Frequrency

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Word Frequrency

License Version

Данный код позволяет выстроить рейтинг слов по частоте употребления в исходном тексте, который должен находиться в файле text.txt в исходной папке (папке, в которой находится программа).
Для подсчёта частоты используется опитимизированная под данную задачу структура unordered dictionary. Благодаря использованию структуры вместо прохода по массиву циклом, удаётся значимо ускорить программу. Под конкретную ситуацию может быть изменён порог создания нового блока (UD_BLOCK_THRESHOLD), а так же размер блока структуры (по умолчанию - 1024 слова). Так же может появиться необходимость замены хэш-функции т.к. текущая была выбрана из соображений скорости вычисления на большом числе архитектур (в том числе, и микроконтроллеры) и сравнительно приемлемой частоте коллизий.
Выигрыш алгоритма unordered dictionary в этой ситуации заключается в отсутствии необходимости прохода по массиву слов в поиске нужного - сначала от слова вычисляется хэш-функция (эффективность - O(1)), а затем это значение используется как индекс в хэш-таблице (эффективность - O(1), в худшем случае - O(B * N), где B - количестов блоков, N - число слов в каждом блоке). Вероятности худшего случая (и близкого к нему) в эффективности хэш-таблиц крайне мала, поэтому наиболее часто будет эффективность O(1). Худший случай хэш-таблицы эквивалентен худшему случаю массива (у массива эффективность O(n)).

Формат файла

Для работы программы с файлов в нём должен быть набор слов, разделённых следующими знаками препинания: .,:;-?!"() или пробелом, или переносом строки. После последнего слова так же должен стоять знак препинания. Любое число знаков препинания может стоять подряд. Вы можете поправить правила определения знака препинания без особых проблем в коде программы (в switch).

Пример:

hello, hello,some.test here?