Техническое задание на Индексатор ( практическая часть работы)
Краткое описание: программа должна производить хранение данных в
специальной структуре, а также быстро производить поиск данных.
Основные затрагиваемые темы: динамическое хеширование, деревья,
работа с файлами.
Дано: имеется "неограниченный" набор данных вида:
слово и ассоциировнанные ему целочисленные значения (индексы).
Надо: создать систему, которая будет обеспечивать такое хранение данных,
при котором поиск индексов, ассоциированных слову, занимал как можно
меньше времени. Для этого необходимо создать хеш-функцию и
реализовать динамическое хеширование поступающих в систему данных.
Функции системы:
1. Добавление файла слов.
На вход подаётся текстовый файл слов. Каждая строка содержит слово и через пробел индекс. Слова в файле могут повторяться. Максимальная длина слова -200 символов, диапазон значений индекса: от 0 до (2^32-1) [возможно расширить до (2^64-1)]. Приблизительное количество слов в файле для тестирования – несколько миллионов.
2. Поиск индексов.
На вход подаётся слово. Необходимо вывести все его индексы. Повторяющиеся индексы для одного слова в системе не хранятся и не выводятся. Время поиска для тестирования будет установлено опытным путём, тем не менее необходимо стремиться к минимуму. В идеале поиск должен быть почти мгновенным (сотые доли секунды).
3. Сохранение системы.
Сохранение системы на диск для возможности её быстрой загрузки. Для хранения можно использовать несколько файлов, но лучше один. Максимальное количество файлов должно быть не больше 2^k, где k – количество первых бит хэш-значения для начального разбиения на деревья (то есть 2^k – количество деревьев). Плюс, возможно, ещё один дополнительный файл.
4. Загрузка системы.
Восстановление системы из файла (файлов). Время загрузки должно стремиться к
минимуму. Запрещается производить перехеширование данных.
5. Сброс системы.
Удаление из системы всех данных.
Интерфейсом программы должен быть предусмотрен запуск перечисленных
функций в произвольном порядке неограниченное количество раз (организовать меню).
Обязательная рекомендация:
1. Создать новый или воспользоваться существующим алгоритмом хеш-функции, дающим хеш-значение не менее 128 бит.
2. Создавать 2^k двоичных деревьев, где k – количество первых бит хэш-значения.
3. Ассоциировать с узлом дерева блок, содержащий слова и индексы. Размер блока фиксированный. При переполнеии блока он разбивается на 2 по следующему биту в хеш-значении. Новые блоки становятся потомками переполнившегося узла.
Программа не должна использовать временных файлов.
Опубликован 20.09.2012 в 12:52