суфф. дерево онлайн - алг. Вайнера

Nov 11, 2014 18:07

Захотелось написать LZSS архиватор, который работает реально на линейное время с неограниченным окном. Скучно и реально больших задач придумать себе не могу. Для этого надо довести префиксное дерево до совсем линейного алгоритма. Суффикское дерево, как в оригинальное работе Зива не подходит, потому что на нужна не просто ссылка на максимальный совпадающий участок данных, а ссылка на ближайший к концу совпадающий участок. Самое главное что ближайший, даже если он не максимальный по размеру. Соотв. почти все линейные алгоритмы не подходят.

Самому ломать голову, это надо время и силы - я полез вспоминать работы Вайнера. Потому что он строит суффиксное дерево задом наперёд. А если подавать данные нормально - то получается отличное префиксное дерево онлайн. Очевидно что надо повернуть, суффиксные связи задом наперёд и почти понятно как всё это делать. Особенно если представить как я удаляю первые символы из готового суффиксного дерева и сделать всё наоборот. Но лучше всё таки пойти в Вайнеру, убедиться что не упустил какую-нибудь мысль.

У него, как оказалось, так и есть. Повернул наизнанку суффиксные связи. Только намутил какие-то индикаторные вектора, векторы связи... Стало очевидно что всё это нафиг не надо. Понятное дело, просто так суффиксные связи не поверну, но и лепить аж целые таблицы на каждый узел!! не надо, на узел достаточно по две ссылки, плюс ещё одну на корень поддерева (хотя эту может уберу). Вобщем, допилить вайнера напильником, додумать и будет не алгоритм, а конфетка. И мне всегда казалось что он гораздо красивее чем алг. Укконена. К вечеру всё придумаю..
Previous post Next post
Up