Progmeistars - новости

Цикл лекций«Обработка текста»

13.02.2004 14:20

     (“Lexical scanning”)Лектор С.И. Мельник
     В этом цикле лекций планируется рассмотреть два основных сюжета: сжатие текста и поиск строк.
     Компьютер применяется для поиска и редактирования текста уже очень давно. Развитие сети резко расширило как потребность в такого рода обработке, так и, особенно резко, объемы обрабатываемых текстов. Поиск, пересылка и добавление информации в Сети является одним из наиболее востребованных применений компьютера. Значительная доля работы с документами состоит в обработке символьных строк и использовании строковых шаблонов. Например, документы в форматах HTML или XML – это, в первом приближении, просто текстовые документы, дополненные специальными символами разметки (тэгами).
     Не менее существенным является поиск информации в различных базах, часто именно текстовой информации. Большие размеры баз приводят к тому, что операции поиска зачастую требуют больших временных ресурсов.
     Важными потребителями эффективных алгоритмов поиска и сравнения строк являются химия, биохимия, клеточная биология.
     Все это привело к появлению алгоритмически эффективных способов поиска строк. В цикле лекций планируется рассмотреть и проанализировать эффективность и реализацию алгоритма Кнута-Морриса-Пратта и алгоритма Бойера-Мура, метода “отпечатков”. Если хватит времени, то хотелось бы рассмотреть методы приближенного сравнения строк, иначе говоря, поиска схожих строк и определения меры их сходства, а также алгоритмы поиска, основанные на применении суффиксных деревьев.
     Быстрый рост объемов обрабатываемой и передаваемой информации, связанный с совершенствованием «железа» и развитием Сети, с выполнением все более сложных прикладных процессов, появлением новых сетевых сервисов, требует все более эффективных методов сжатия данных для их хранения и передачи. Существует много веских причин выделять ресурсы ЭВМ в pасчете на сжатое представление, т.к. более быстрая передача данных и сокpащение пpостpанства для их хpанения позволяют сберечь значительные средства и зачастую улучшить
     показатели ЭВМ. Сжатие, кроме того, можно использовать для преодоления некотоpых физических ограничений, таких, напpимеp, как низкая шиpина пpопускания канала.
     Для сжатия текстов необходимо применять обратимое сжатие (сжатие без потери информации). Сжатие текстов связано с более компактным расположением байтов, кодирующих символы. Определенные результаты дает статистическое кодирование, в котором наиболее часто встречающиеся символы имеют коды наименьшей длины.
     Мы рассмотрим кодирование Хаффмана, алгоритм Лемпеля-Зифа, сжатие методом сортировки блока, возможно, арифметическое сжатие.
     Никаких специфических предварительных знаний не требуется, однако слушателям было бы неплохо иметь навык программирования. Это, во-первых, даст возможность более точно оценить возникающие трудности и способы их разрешения, во-вторых, реализация программ для изучаемых алгоритмов, несомненно, позволит глубже и прочнее усвоить теоретический материал.
     Записываться на этот лекторий можнодо 25-го февраля по телефону 7336035 или у администрации курсов
     Cм. также "Лекторий"