Алгоритмы, структуры данных




ДАЛЬHЕЙШИЕ ИССЛЕДОВАHИЯ. - часть 2


Вероятно, что поиски методов улучшения характеристик сжатия в данном направлении будут объединяться с исследованиями в области контекстуального анализа по таким проблемам как извлечение ключевых слов и автоматическое абстрагирование.

Второй подход диаметрально противоположен описанному выше наукоемкому направлению, и состоит в поддержании полной адаптивности системы и поиске улучшений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод постстроения моделей состояний; показанный метод DMC - лишь форма контекстно-ограниченной модели[8]. Тонкости роста этих СД вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [110], этот вопрос еще не был исследован систематично. Дpугой стоящей темой для исследований являются методы выделения кодов уходов в частично соответствующих контекстуальных моделях. В итоге, пpеобpазование систем, определяемых состояниями, таких как скрытые модели Маркова[77], может вдохнуть новую жизнь в модели состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей Маркова [4] в последнее время был вновь открыт в области распознавания речи [60]. Он может быть успешно применен для сжатия текстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига[25]. Недостаток этих методов состоит в их значительных временных затратах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятками и сотнями, а не тысячами и более состояний.

Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжатия текстов, будут несомненно продолжены в будущем. Постоянный компромисс между стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными СД, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [43], разными путями воздействует на баланс между хранением и выполнением. Будет развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодированием на микросхеме, когда как Гонзалес-Смит и Сторер [34] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска.


Содержание  Назад  Вперед