Имя (желательно полное):

E-Mail:

URL:

Город:

Страна:

Вежливый и подробный комментарий:
(Форматируйте его, пожалуйста, как почту - короткими строками
Еnter в конце строки, пустая строка между параграфами).
> Hi again! > > > Далее при выполнении LZ можно просто > > > выполнять поиск по этому дереву > > > (деревьям), правда, отсекая строки, > > > не входящие в скользящее окно. > > Чей-то я не понял, как должен работать > > декодер. Допускаются ссылки только > > на прошлый блок? ;) > Да. ПРи ссылках на любую подстроку значительно усложняется декодер. А простой и быстрый декодер - IMHO, главное достоинство LZ. Кстати, есть ли вообще алгоритмы, использующие LZ77-ссылки в будущее? SEQUITUR не предлагать! :) > > А чем это дерево отличается > > от классического? > > Сначала мне показалось, что > > предлагается просто использовать > > BWT для сортировки строк и > > построения оптимального дерева. > Именно. А вся затея как раз в том, чтобы строить дерево только один раз для всего блока. Плюс ко всему дерево это идеально сбалансировано. Поэтому на больших (соизмеримых с размером блока) словарях в идеале только поиски должны быть в 2 раза быстрее (т.к. высота RB и AVL деревьев не превышает 2*Logn). Не говоря о том, что добавления и удаления вообще не нужны. > Плюс, на мой взгляд, имеются два неоспоримых преимущества: > 1) Неполный поиск : необязательно перебирать полностью - дерево ведь статическое. Поэтому появляется возможность простой и эффективной реализации различных Fast-методов. > 2) Для каждой вершины можно завести дополнительный атрибут - LCP ее строки и родительской. И при сравнении просто скипать общие префиксы. Это гораздо быстрее будет, чем скипанье Min(MaxLeftCommonPrefix, MaxRightCommonPrefix), которое используется в большом количестве LZ-компрессоров. Так как дерево статическое, то сложностей с обновлением значений LCP просто нет. > Плюс ко всему при его расчете можно использовать эту же Min(MaxLeft, MaxRight) эвристику. > Так что, IMHO, должно работать довольно быстро. :) > > > > > Мне бы хотелось узнать мнение > > > специалистов об этом алгоритме. > > > Достаточно ли он эффективен, > > > чтобы его применять на практике? > > Вообще-то непохоже. ;) > > Кстати, следует еще упомянуть исключительную простоту реализации. > Но несмотря на нее, у меня что-то нет особого желания проверять этот алгоритм, так как может оказаться, что он - нерабочий труп. Если же кому-то кажется, что он достаточно практичен, то, пожалуйста, черкните пару строк. > Regards, > Никита Лесников (mailto: nlo_one@mail.ru) >

Пожалуйста, заполните все поля.
И не нажимайте по два раза на кнопку! Дождитесь ответа сервера.