Есть задача:
Написать быстрый индекс большого куска данных(1-40 mb). Данные- любой файл на вашем жёстком диске. Индекс должен позволять быстро проверить наличие подфрагмента, т.е задача поиска подстроки.Но требования:
1. Требования к памяти (6-10)n (короче,дерево не рулит)
2. Динамическое создание по мере прохождения файла (вперёд не смотрим)
3. Возможность на каждом шаге найти все одинаковые строки длинной L
4. Возможность реализации скользящего окна по блоку (т.е индексируем последнии 10 mb)

Если кто не догадался, речь идёт об реализации словаря для LZ77, типа как в LZMA Игоря Павлова, но с меньшими затратами памяти и возможностью из пункта 3.

P.s если что не понятно, спрашивайте, прокоментирую

mayton dakdark
Если кто не догадался, речь идёт об реализации словаря для LZ77, типа как в LZMA Игоря Павлова, но с меньшими затратами памяти и возможностью из пункта 3.


Не поверишь! Я-бы в жизни не догадался!

Вообще, такие вопросы лучше задавать на http://forum.compression.ru:8080/

Не поверишь! Туда зайти я бы не догадался.
Только,вот, обсуждается реализация алгоритма, а точнее структур данных, обеспечивающих данные характеристики. Интересен сам вопрос решения данной задачи. Так кто-нибудь может что-то предложить. Ну там список с промежуточными ссылками, patrical tree, binary tree, heap search, dynamic binary array.... А полем структурка типа

Если использовать DBA(dynamic binary array), то скорость выполнения всего перечисленного где-то 500-1000 Kb/s.

Но хотелось услышать какие-то предложения :)