Сжатие и индексация дерева: различия между версиями

Деревья – одна из базовых структур любых вычислений. Они используются практически в любых аспектах моделирования и представления таких вычислительных процессов, как поиск ключей, ведение каталогов и представление трассировки разбора или выполнения – и это лишь малая часть примеров. Один из новейших способов использования деревьев – XML, формат номер один для хранения и интеграции данных и обмена ими через Интернет (см. http://www.w3.org/XML/). Явное хранение деревьев, под одному указателю на потомка плюс указатели на некоторую дополнительную информацию (например, метки) нередко рассматривается как данность; однако хранение в таком виде может потребовать значительных расходов на память. Чтобы получить представление об их размерах, вспомним, что при простом кодировании дерева необходимо по меньшей мере 16 байт на вершину дерева: один указатель на дополнительную информацию (например, метку вершины) плюс три указателя – на родителя, первого ребенка и следующего брата. Подобные требования к объему памяти могут стать препятствием для обработки даже деревьев среднего размера – например, XML-документов. Далее будут рассмотрены лучшие решения для хранения непомеченных и помеченных деревьев, эффективные по объему занимаемой памяти и поддерживающие быстрые операции навигации и поиска над структурой дерева. В литературе такие решения носят название решений для индексации сокращенных или сжатых деревьев.