До этого момента считалось, что словарем LZW служит массив из строк переменной длины. Чтобы понять, почему специальное дерево будет являться лучшей структурой для словаря, следует напомнить работу кодера. Он считывает символы и добавляет их в строку I до тех пор, пока I находится в словаре. В некоторый момент строка 1х в словаре не обнаруживается, и тогда строка 1х помеш;ается в словарь. Значит, при добавлении новых строк в словарь поступает всего один новый символ х. Это предложение можно перефразировать еще так: для каждой словарной строки в словаре найдется «родительская» строка, которая короче ровно на один символ. Поэтому для наших целей хорошим выбором будет структура дерева, которая уже использовалось в LZ78, при построении которого добавление новых строк 1х делается добавлением всего одного нового символа х. Основная проблема состоит в том, что каждый узел дерева LZW может иметь много потомков (дерево не двоичное, а q-ичное, где q - это объем алфавита). Представим себе узел буквы а с номером 97.

В начале у него нет потомков, но если к дереву добавится строка аЬ, то у а появится один потомок. Если позже добавится новая строка, скажем, ае, то потомков станет два, и так далее. Значит, дерево следует сконструировать так, чтобы каждый узел в нем мог бы иметь любое число потомков, причем без резервирования дополнительной памяти для них заранее. Один путь конструирования такой структуры данных - это построение дерева в виде массива узлов, в котором каждый узел является структурой из двух полей: символа и указателя на узел родителя. В самом узле нет указателей на его потомков. Перемещение вниз по дереву от родителя к потомку делается с помощью процесса хеширования (перемешивания или рандомизации), в котором указатели на узлы и символы потомков перемешиваются некоторой функцией для создания новых указателей. Предположим, что строка аЬс уже была на входе, символ за символом, и ее сохранили в трех узлах с адресами 97, 266, 284. Пусть далее за ними следует символ d. Теперь кодер ищет строку abed, а точнее, узел, содержащий символ d, чей родитель находится по адресу 284. Кодер хеширует адреса 284 (указатель на строку аЬс) и 100 (ASCH код d) и создает указатель на некоторый узел, скажем, 299. Потом кодер проверяет узел 299. Возможны три случая.

1. Этот узел не используется. Это означает строки abed еще нет в словаре и его следует туда добавить. Кодер делает это путем сохранения родительского указателя и ASCH кода 100 в этом узле.
2. Узел содержит родительский указатель 284 и ASCII код символа d. Это означает, что строка abed уже есть на дереве. Тогда кодер вводит следующий символ, скажем, е и ищет на дереве строку abede.
3. В узле хранится что-то другое. Это означает, что хеширование другой пары указателя и кода ASCII дало адрес 299, и узел 299 уже содержит в себе информацию про другие строки. Такая ситуация называется коллизией^ и ее можно разрешить несколькими путями. Простейший путь разрешения коллизии - это увеличивать адрес до 300, 301,... до тех пор, пока не будет найден пустой узел или узел с содержимым (284: «d»). На практике узлы строятся состоящими из трех полей: указателя на родительский узел, указателя (или индекса), созданного в процессе хеширования, и кода (обычно, ASCII) символа, лежащего в этом узле. Второе поле необходимо для разрешения коллизий. Таким образом, узел имеет вид триплета parent index symbol. Пример: Проиллюстрируем эту структуру данных с помощью строки «ababab. . .» из примера. Словарем будет служить массив diet , элементами которого являются структуры с тремя полями parent, index, symbol.