Lucarev_5 (Лекции по ЭВМ)

Компьютерный текстТекст – это словесная запись мыслей, сообщений, речи.Компьютерный текст – это цепочка символов.Несмотря на простоту и краткость, определение требует подробного разбора. Подсловом цепочка понимается линейная одномерная конструкция конечной длины,состоящая из некоторых элементов а1 , а 2 ,..., а п . Элементом цепочки компьютерноготекста является символ. Буквы, цифры, знаки препинания, служебные символы-этоотдельные символы. Множество всех символов, из которых строится текст, называетсяалфавитом.

При работе в текстовых редакторах мы имеем дело не с самимкомпьютерным текстом, а с его изображением; при смене шрифта (способа изображениятекста) сам компьютерный текст не меняется.НА□ДВОРЕ□ТРАВА¶НА□ТРАВЕ□ДРОВАКодирование текстаКодирование текста-это установление таблицы соответствия между кодируемымсимволом и комбинацией состояния битов, то есть процесс кодирования заключается втом, что каждому символу ставится в соответствие уникальный код. В настоящее времясуществуют различные системы кодирования, основное различие между нимизаключается в количестве бит, необходимых для кодирования одного символа.Системы кодирования•ASCII (American Standard Code for Information Interchange): для кодированияодного символа используется количество информации=7 бит.

Если рассматриватьсимволы как возможные события (см. лекцию 1), то можно вычислить количествосимволов, которые можно закодировать:27=1282*26-латинские буквы10-цифры32-различные знаки34-служебные символы128-символовТаким образом, количество кодируемых символов ограничено, поэтому всемибитной системе кодировки невозможно закодировать буквы русского алфавита.Возникла задача одновременно изображать и русские, и латинские символы.

Способамирешения этой задачи являются транслитерация и расширение кодировки.• Восьмибитные системы кодировки:28=256Если старший бит кода-0, то система кодировки совпадает с ASCII, если старшийбит –1, то вводятся дополнительные кодов-ые страницы.1кодANSIКОИ-8CP125Е1 1110 0001áАбЕЕ 1110 1110ÎНоF4 1111 0100ÔРфF2 1111 0010òТтC0 1100 0000ÀюАCD 1100 1101ÍмНD0 1101 0000ÐрРD2 1101 0010ÒпТВ России была создана одна из таких систем КОИ-8, ее недостаток в том, чторусские буквы расположены не по алфавиту.Кроме того существуют СР-866, СР-1251,ANSI, использующиеся в операционной системе Windows.• Большие кодовые страницы:− UNICODEНа кодирование одного символа необходимо 16 бит216=65535естественно с такой системой кодирования не возникает проблемы невозможностикодировки того или иного символа, так как 65535 с избытком покрывает многообразиеиспользуемых символов, но UNICODE имеет другой недостаток: при переводе текстов изASCII в UNICODE существенно увеличивается размер компьютерного текста.

В связи сэтим разработан еще один класс систем кодировки, использующих переменное число битдля кодирования символов.− UTF-8Если старший бит кода равен нулю (бит8=0), то система кодировки совпадает сASCII, причем каждый из первых 128 символов кодируется одним байтом.Если старший равен единице (бит8=1, бит7=0), то следующие 16384 символа кодируютсяаналогично UNICODE, то есть для кодировки каждого символа используется два байта.Оставшиеся символы (65535-128-16384=49023) кодируются тремя байтами.Пример: рассмотрим, сколько информации несет цепочка символов"Information⋅−⋅Информация"в различных системах кодировки.

В случае СР1251 каждый символ кодируется однимбайтом ⇒ количество информации: 24*1=24 байт. В UNICODE каждый символкодируется двумя байтами ⇒ количество информации: 24*2=48 байт. В UTF-8 накодировку латинских букв, знаков пробела и тире необходимо один байт на каждыйсимвол, а каждый символ слова "Информация" кодируется двумя байтами ⇒ количествоинформации: 14*1+10*2=34 байт.С одной стороны, компьютерный текст – это алфавитный, по которому текстпредставляется как цепочка символов (алфавитный подход). Другой подход заключается втом, что компьютерный текст рассматривается уже как сложная структура, состоящая измножества всех цепочек символов.t:{1, 2, 3...k} - одна из таких цепочек длиной k.Такой подход дает возможность понять алгоритм преобразования текста, которыйосуществляется по принципу функционального отображения, то есть одной текстовойцепочке, входящей в область определения этого алгоритма, ставится в соответствиедругая цепочка, являющаяся результатом преобразования: t1→t2.

В таком случае областьюопределения функции (алгоритма) будет являться язык.Грамматика языка – это правила, порождающие все входящие в язык цепочки.Отдельный символ алфавита – это регулярное выражение. Грамматики, построенные нарегулярных выражениях, записываются в виде программы, которая порождает цепочку2символов. Назначение регулярных выражений – задать множество цепочек, составляющихязык.Регулярные выраженияМеханизм построения регулярных выражений осуществляется по принципу "отпростого к сложному". Для любого алфавита существует простое выражение - одинсимвол алфавита.

Мощность регулярного выражения – это мощность порождаемогомножества или количество элементов. В простейшем случае для простого регулярноговыражения S – 1 символ алфавита: M(S)=1.Если a и b регулярные выражения, то регулярными выражениями будут:• a|b- "или", объединение множеств.M(a|b)=M(a)+M(b)Например, пусть а=(один; два), b= (три; четыре; пять), тогда M(a|b)=M(a)+M(b)=(один,два, три, четыре, пять).• ab – "конкатенация", прямое произведение множеств (получается множество пар,где каждому элементу из а сопоставляется элемент из b).M(ab)=M(a)×M(b)Например, пусть а=(один; два), b= (три; четыре; пять), тогда a×b=М(а)×М(b)=(один_три;два_три; один_четыре; два_четыре; один_пять; два_пять).• а*- "повторение"М(а*)=0+М(а)+М(а)×М(а)+...=∞М(а)=М﴾(а)﴿Примеры:(a/b)(a/b)={aa; ab; ba; bb}﴾(a/b)a﴿*={aa; ba; aaaa; baaa; aaba; baba; aaaaaa}Как видно, запись регулярных выражений часто занимает много времени, поэтомубыли созданы сокращенные записи для некоторых элементов регулярных выражений.1.Б=а/б/в/г/д/.../ю/я в сокращенном виде [а-я]2.С=Б/ББ/БББ/ББББ/ конкретное число повторений -[а-я] {1,4}3.