Регулярное выражение

Преобразование текста

Количество информации

Битные кодовые страницы

Битные кодовые страницы

ASCII

Кодирование текста

Компьютерный текст и его изображение

Компьютерный текст

Операционные систмемы

Компьютерный текст

Шрифт

Векторная графика

Кодирование цвета - палитра

Кодирование цвета – RGB

n24-битный цвет

–8 бит интенсивность красного

–8 бит интенсивность зеленого

–8 бит интенсивность синего

nДисплей

–800 x 600 пикселей

–3 байта на пиксель

–1 440 000 байт > 1Мбайт

nИзображение составляется из графических элементов: прямых, ломаных, прямоугольников, овалов и т.п.

nДля каждого элемента кодируются координаты контура, цвет и толщина линии, цвет заполнения.

nПример – язык SVG (Scalable Vector Graphics)
http://www.w3.org/TR/2003/REC-SVG11

n… - таблица, в которой коду символа соответствует рисунок символа

nРастровый, векторный, контурный

Следующая лекция – базы данных

Вопросы?

#3

nТекст – буквы, слова, предложения

nКомпьютерный текст – цепочка символов

nСимволы – элементы конечного множества, включающего буквы, цифры, знаки, служебные символы

–Пробел

–НС

nЧисло бит на символ

–7 бит/символ – ASCII

–8 бит/символ – ANSI, КОИ-8, CP866, CP1251

–16 бит/символ – UNICODE

–8-24 бит/символ – UTF-8

nСоответствие между кодами и символами

nAmerican Standard Code for Information Interchange

n7 бит на символ – 128 символов

–26*2 латинских буквы

–10 цифр

–32 знака

–34 служебных символа

nСтарший бит 0 – ASCII

nСтарший бит 1 – кодовые страницы

Большие кодовые таблицы

nUNICODE: 16 бит/символ – 65535 символов

nUTF-8: переменное число байт

–Бит8=0: один байт (ASCII)

–Бит8=1&Бит7=0: два байта (16384 символа UNICODE)

–Бит8=1&Бит7=1: три байта (оставшиеся символы)

nCP1251: 24 байта

nUTF-8: 37 байт

nUNICODE: 50 байт

nАлгоритмы компрессии (WinZip, …)

–Переменная длина кода

–В множество «символов» помещают часто встречающиеся подцепочки (слова)

nS: {s₁,s₂,…s_n} – множество символов

nt: {1,2.. k }®S – цепочка символов длиной k

nT – множество всех цепочек (длины 0, 1, 2, …)

–{ а, б, в, … я, аа, аб, ав, … мамамылараму …}

nT®T – алгоритм преобразования текста

nОбласть определения = язык

nГрамматика языка – правила, порождающие все входящие в язык цепочки

nПример

–Грамматика: все цепочки, содержащие последовательность МАМА

–Функция преобразования: замена всех вхождений МАМА на ПАПА

n… - правило, порождающее множество текстов

nЛюбой символ алфавита – регулярное выражение (порождает множество из одного текста длиной в один символ)

nЕсли a и b – регулярные выражения, то регулярными выражениями являются

– a | b («или», объединение множеств)

– ab («конкатенация», прямое произведение множеств)

–(a)

– a* («повторение»)

nПримеры

– (a | b) (a | b) порождает { aa, ab, ba, bb}

– ((a | b) a)* порождает { aa, ba, aaaa, baaa, aaba, baba, aaaaaa, … }

Порождаемые языки?

n Б = a | б | в | г | … | ю | я

–Другая запись [а-я]

n С = Б | ББ | БББ | ББББ

–Другая запись: [а-я]{1,4}

n(С (¶ | □))*

–Другая запись: ([а-я]{1,4}[ ])*

Литература

nРегулярные выражения

–Т.Пратт, М.Зелковиц. Языки программирования. Разработка и реализация. М.: Питер, 2002 (ISBN 5-318-00189-0) Раздел 3.3.2

–А.В.Ахо, Р.Сети, Д.Д.Ульман. Компиляторы: принципы, технологии и инструменты. М.: Вильямс, 2003 (ISBN 5-8459-0189-8) Раздел 3.3

#2

Дата добавления: 2014-01-20