3.4.13 Структуры данных для метода Зива-Лемпела
Наиболее распространенной СД в методе
Зива-Лемпела и для моделирования в целом
является дерево цифрового поиска. Такая
СД и ее вариации обсуждаются в [51]. Для
работающих с окнами схем можно пpименять
линейный поиск, поскольку размер области
поиска постоянен (хотя сжатие может
быть очень медленным). В качестве
компромисса между быстpотой дерева
цифрового дерева поиска и экономным
расходованием памяти линейного поиска
можно применить двоичное дерево [5]. Для
этой цели также можно использовать
хеширование [12]. Подобное применение
хеширования можно обнаружить в [110].
Сравнение СД, используемых для сжатия
Зива-Лемпела, приводится у Белла [7].
Работающие с окнами схемы имеют то
неудобство, что подстроки после своего
исчезновения из окна должны уничтожаться
в индексной СД. В [85] описан метод,
позволяющий избежать этого посредством
поддерживания нескольких индексов
окна, что т.о. позволяет осуществлять
поиск в СД, где уничтожение затруднительно.
Однако, особая предложенная там СД была
без необходимости сложной для pаботы с
окнами.
Проблема поиска вполне поддается
мультипроцессорной реализации, поскольку
на самом деле существует N независимых
строчных соответствий, которые необходимо
оценить. В [34] описана параллельная
реализация сжатия Зива-Лемпела.
