Автор: Eugene D. Shelwien,
11 августа 2003 года в 23:22:15
В ответ на : Вопрос: поиск подстрок в LZ сортировкой от Никита Лесников
в 11 августа 2003 года в 16:08:45:
Hi!> Мне в голову пришел следующий метод
> поиска подстрок в поблочном LZ.
> Я даже подозреваю, что он
> используется в IMP. :) ХЗ. По-моему, (я смотрел 1.12) там
используется непосредственно таблица
BWT-индексов, без всяких деревьев. > Далее при выполнении LZ можно просто
> выполнять поиск по этому дереву
> (деревьям), правда, отсекая строки,
> не входящие в скользящее окно. Чей-то я не понял, как должен работать
декодер. Допускаются ссылки только
на прошлый блок? ;) > Конечно же, есть и отрицательные
> стороны: на малых (относительно
> размера блока) словарях процент
> отсекаемых строк будет слишком
> велик. В то же время, когда размер
> словаря соизмерим с размером блока,
> данная реализация в среднем должна
> работать очень эффективно. Кроме
> того, становится возможным неполный
> поиск по дереву, который
> трудно реализовать на "классических"
> деревьях. А чем это дерево отличается
от классического?
Сначала мне показалось, что
предлагается просто использовать
BWT для сортировки строк и
построения оптимального дерева.
> Мне бы хотелось узнать мнение
> специалистов об этом алгоритме.
> Достаточно ли он эффективен,
> чтобы его применять на практике? Вообще-то непохоже. ;) > Regards,
> Никита Лесников
> (mailto:nlo_one@mail.ru) Счастливо!
- Шелвин
|