Laboratory of Mathematical Logic at PDMI

Пятница, 27 января, комната 106. Начало в 17:30.

Докладчик: Ю. Лифшиц.

Тема: Новые алгоритмы обработки сжатых текстов.

Abstract

В теории алгоритмов активно развивается новое направление: обработка сжатых объектов без распаковки. В ряде случаев удается придумать более эффективный алгоритм, чем "распакуй-и-запусти-обычный-алгоритм". В докладе я расскажу общий обзор достижений в этой области обработки сжатых текстов и ряд алгоритмов придуманных мной за последний месяц.

Во-первых, будет представлен алгоритм поиска подстрок, работающий за куб от размера сжатого текста и шаблона. Прежний алгоритм (1997) работал за n^4. Далее будет представлен алгоритм поиска всех периодов и накрытий для данного сжатого текста. Последний алгоритм строит таблицу отпечатков (fingerprint table) для сжатого текста.

В конце доклада будет сформулирован ряд открытых вопросов.