Розробкаалгоритмів для побудови частотних словників, Стаття у журналі «Молодий ученый»
Бібліографічний опис:
Метою даної є розробка алгоритмів для побудови частотних словників. При виборі методики рішення було розглянуто два способи представлення даних: двійкові дерева та хеш-таблиця [2].
Хеш-таблиця - структура даних, що реалізує інтерфейс асоціативного масиву. Є ефективною структурою даних для реалізації словників, а саме, вона дозволяє зберігати пари ключ-значення і виконувати три операції: операцію додавання нової пари, операцію пошуку та операцію видалення пари по ключу.
Двійкове дерево — деревоподібна структура даних, у якій кожен вузол має трохи більше двох нащадків (дітей). Як правило, перший називається батьківським вузлом, а діти називаються лівим та правим спадкоємцями.
За результатами порівняння для реалізації був обраний метод на основі побудови хеш-таблиці як найбільш оптимальний для вирішення цього завдання. Для організації хеш-таблиці доцільно використовувати тип даних структуру. В ній необхідно визначити поле для ключа, поле для значення та поле для посилання на наступний елемент.
Код створеної структури виглядає так:
Як хеш-функція була обрана Djb, тому що це проста та швидка хеш-функція загального призначення. Так само з переваг функції можна відзначити гарний розподіл і простоту конструкції. Ця функція розроблена професором Деніелом Берштейном, американським математиком та програмістом. Вона не є криптографічно безпечною, повертає 32-розрядне беззнакове число як хеш-суми. Код хеш-функції, що використовується, виглядає наступним чином ( Підпишіться на нашу розсилку: Підписатися