Раздел 4 Тексты

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

Вначале было слово.

Так говорит история человечества. В истории компьютеров вначале было число. Долгое время вместо термина «компьютер» использовались аббревиатуры «ЭВМ» (Электронная Вычислительная Машина) и «ЦВМ» (Цифровая Вычислительная Машина), что подчеркивало цифровую сущность первых компьютеров. И использовались они тогда в отраслях, связанных с военными применениями, в зарождающейся космической отрасли, в физике, - в тех областях, где господствовала цифра. Тогда в почете были физики, а не лирики с их, казалось бы, ненужными текстами.

Ситуация начала меняться в 60-х годах. И в немалой степени способствовали переменам сами компьютеры, развитие которых потребовало создания языков программирования. Нотацию для записи программ на уровне более высоком, чем система команд компьютера, стали называть «языком». Если первый язык программирования Fortran (Formula Translator) сохранил в своем названии приверженность к формулам, то последующий языки – AlgoL, CoboL, SnoboL, PL/I несли в своем имени букву L от слова «язык» (Language). Программы для компьютеров, написанные на языках программирования, стали восприниматься как тексты. И одной из главных задач, порожденных внутренними потребностями самого программирования, стала задача трансляции. К тому времени языкотворчество стало модным, число языков исчислялось сотнями. Для каждого языка нужен был транслятор - программа, осуществляющая перевод текста с одного (формального) языка в другой формальный язык (язык системы команд компьютера).

В первых языках программирования – Фортране и Алголе по-прежнему практически отсутствовали средства представления текстовой информации и работы с ней. В сборнике упражнений по Алголу [9], подготовленном на факультете ВМК МГУ и вышедшем в 1975 году, нет ни одного упражнения по работе с текстовой информацией, все упражнения предназначены для работы с числами. Приведу еще цитату из книги [8], вышедшей у нас в 1980 году и посвященной обзору расплодившихся тогда языков программирования: «Можно сказать, что для «научных» языков программирования характерно полное или почти полное отсутствие средств для работы со строками литер».

Однако время господства цифры уже прошло и ей пришлось уступить символу, занявшему законное первое место в компьютерных программах. Этому во многом способствовали успехи математической лингвистики, теории и практики разработки трансляторов, теории формальных грамматик и теории автоматов. Появились языки логического программирования. В японском проекте машин пятого поколения делалась ставка на эти языки в надежде на существенное повышение «интеллекта» программ, немыслимое без работы с текстами. Возникающие здесь задачи оказались ничуть не проще, а во многом сложнее задач вычислительной математики. Надежды решить их с помощью компьютера оправдались лишь в малой степени. Например, задача перевода с одного естественного языка на другой до сих пор решена лишь частично. До сих пор приемлемый перевод технических текстов требует вмешательства человека. Для художественных текстов компьютерный перевод может быть полезен лишь как подстрочник. Но не все так плохо, и несомненные успехи в этой области достигнуты. Интеллектуальные роботы, автомобили, дома - становятся частью нашего мира. Мой хороший друг, прекрасный математик и шахматист Леонид Дмитриевич Иванов полагал, что компьютеры никогда не смогут одолеть шахматного мастера. Он ошибался. Сегодня чемпион мира еще может соревноваться с компьютером, но завтра справиться с компьютером в этой игре человеку будет невозможно. Компьютеры считают лучше. Они быстрее просчитывают варианты, они могут обработать в короткое время огромные массивы разнородной информации – числа, тексты, картинки и звуки. Что же остается человеку? Многое. Действительно новую информацию создает человек. Он создает «настоящие» тексты. Компьютеры могут лишь их обрабатывать.

Появление персональных компьютеров в каждом доме, а затем и появление компьютерных сетей, создало новую реальность – информационный мир. Ежедневно миллионы людей создают новые тексты, размещая их в Интернете – этом громадном хранилище текстов. Денно и нощно поисковые машины перелопачивают эту груду, индексируя их, наводя хоть какой-то порядок, позволяющий по запросу найти нужный текст. Без людей, создающих тексты, и без компьютеров, обрабатывающих эти тексты, Интернет, как хранилище информации, был бы бесполезным.

Здесь есть еще одна невидимая сторона дела – алгоритмическая сложность задач, решаемых в процессе поиска. Пользователям Интернета, далеким от понимания алгоритмов, может казаться совершенно естественным, что на их запрос уже через секунды выдается большое число ссылок на тексты с запрашиваемой информацией. Пользователи могут жаловаться, что ссылок слишком много, не все из них действительно соответствуют запросу, но в целом система работает удовлетворительно. У специалиста, представляющего, какие объемы текстов следует просмотреть для получения ответов, работоспособность системы должна вызывать изумление и уважение. Примитивные алгоритмы работы с текстами не смогли бы привести к успеху поиска.

Интернет далеко не единственная область, где подобные алгоритмы играют важнейшую роль. Молекулярная биология (и ее раздел - биоинформатика) является сегодня бурно развивающейся научной областью. Как ни странно, а может быть вполне естественно, что при анализе структур ДНК и РНК, при расшифровке генома человека работа с текстами играет определяющую роль. В книге Дэна Гансфилда [Строки], подробно рассматриваются алгоритмы работы с текстами, как необходимый инструментарий решения задач вычислительной биологии. Приведу из нее некоторые цитаты, поясняющие, как биологическая информация представляется в виде текста: «Можно получить биологически осмысленные результаты, рассматривая ДНК как одномерную строку символов… Аналогичное, но более сильное предположение делается и о белках… Информация, которая лежит за биохимией, клеточной биологией и развитием, может быть представлена обычной строкой, составленной из 4-х символов G, А, Т и С. Для биологии организмов эта строка является исходной структурой данных».

(В одной из задач, приводимых ниже, поясняется смысл используемых символов).

Символьные данные

Дадим формальное определение строки символов и других важных понятий.

Пусть T = {t₁, t₂, …t_n} – конечное множество, которое будем называть алфавитом, а его элементы – символами алфавита. Строкой s (словом, цепочкой) в алфавите T будем называть последовательность подряд записанных символов из T – (s = c₁c₂...c_m). Число символов в слове – m будем называть длиной слова. Пустое слово длины 0 будем обозначать символом ε или константой вида "". Если s – строка длины m (s = c₁c₂...c_m), то подстрокой s[i, j], где 1 <= i <= j <= m, ,будем называть часть строки из s, начиная с i-го символа и заканчивая символом j - (c_ic_i+1…c_j). Подстрока s[1, j] называется префиксом слова, а подстрока s[i, m] – суффиксом слова.

Алфавит T можно рассматривать как множество слов длины 1. Рассмотрим операцию конкатенации над множествами, так, что конкатенация алфавита T с самим собой дает множество всех слов длины 2. Обозначается конкатенация ТТ как Т². Обозначим через

• T^k – множество слов в алфавите T длины k, - его можно рассматривать как k-кратную конкатенацию алфавита T;

• T⁺ - множество всех непустых слов в алфавите T произвольной длины. Это множество получается, как результат объединения множеств T^k по всем возможным значениям k;

• T^* - множество всех возможных слов в алфавите T. Это множество называется итерацией алфавита и его можно рассматривать как объединение пустого слова с множеством T⁺.

Рассмотрим примеры некоторых алфавитов. Алфавит T₂ = {0, 1} – любые данные, хранимые в памяти компьютера, можно рассматривать, как слова в этом алфавите. Алфавит T₁₀ = {0, 1, …9} – целые числа без знака в десятичной системе счисления являются словами в этом алфавите. Четырехбуквенные алфавиты T_DNK = {A, T, G, C} и T_DNK = {A, U, G, C} используются для строк, задающих структуру молекул ДНК и РНК. Каждая молекула ДНК и РНК представляет комбинацию 4-х нуклеотидов: Аденин (А), тимин (Т), цитозин (С) или гуанин (G) в ДНК; аденин (А), урацил (U), цитозин (С) или гуанин (G) в РНК.

В основе каждого языка лежит некоторый алфавит T. Если под языком G(T) понимать множество всех слов данного языка в алфавите T, то G(T) является подмножеством T*. Задать конкретный язык можно разными способами. Для языков программирования широко применяется аппарат формальных грамматик, позволяющий описать синтаксически корректные программы.

Определим класс языков, задаваемых регулярными множествами. Регулярное множество определяется рекурсивно следующими правилами:

• пустое множество, а также множество, содержащее пустое слово, и одноэлементные множества, содержащие символы алфавита, являются регулярными базисными множествами;

• если множества P и Q являются регулярными, то множества, построенные применением операций объединения, конкатенации и итерации – , PQ, P^*, Q^* – тоже являются регулярными.

Регулярные выражения представляют удобный способ задания регулярных множеств. Аналогично множествам, они определяются рекурсивно:

• регулярные базисные выражения задаются символами и определяют соответствующие регулярные базисные множества, например, выражение f задает одноэлементное множество {f} при условии, что f — символ алфавита T;

• если p и q – регулярные выражения, то операции объединения, конкатенации и итерации – p + q, pq, p*, q* — являются регулярными выражениями, определяющими соответствующие регулярные множества.

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

С точки зрения практика регулярное выражение задает образец поиска. После чего можно проверить, удовлетворяет ли заданная строка или ее подстрока данному образцу. В языках программирования синтаксис регулярного выражения существенно обогащается, что дает возможность более просто задавать сложные образцы поиска. Такие синтаксические надстройки, хотя и не меняют сути регулярных выражений, крайне полезны для практиков, избавляя их от ненужных сложностей.

Какие операции над строками лежат в основе преобразований текста? Как и для арифметического типа, это операции отношения, позволяющие сравнивать строки, и некоторый набор операций, позволяющих из заданных строк получать новые строки.

Строковый тип, также как и арифметический тип, считается упорядоченным. Вначале задается порядок на символах алфавита, например как в кириллице от «А» до «Я». Порядок на алфавите порождает порядок на словах, называемый лексикографическим порядком. Не определяя его формально, скажу, что этот порядок задает расположение слов в словарях. Поэтому на строках определены операции сравнения не только на равенство, но и на «больше» и «меньше».

Пока не выработаны устоявшиеся обозначения для базисных операций над строками, подобные «+» или «-» для арифметического типа. Тем не менее, любой язык программирования, позволяющий работать с текстами, включает такие операции над строками как: конкатенация, поиск, вставка, удаление и замена подстрок. Эти операции можно считать базисными. С их помощью один текст можно преобразовать в другой текст, например сделать из «мухи» «слона», или осуществить перевод текста с одного языка на другой язык.

Представление символьных данных в C#

Для работы с текстами на языке C# библиотека классов FCL предлагает целый набор разнообразных классов, сосредоточенных в разных пространствах имен этой библиотеки. Классы для работы с текстами находятся как в основном пространстве имен System, так и в пространствах System.Text и System.Text.RegularExpression. Основные, но далеко не все из этих классов, подробно рассмотрены в учебнике [1]. Они же будут встречаться в задачах этого раздела.

Классы C# для работы с текстами

Рассмотрим несколько основных классов, позволяющих работать с текстовой информацией, - char, char[], string, StringBuilder. Класс System.Char (синоним класса char) определяет множество символов – алфавит языка. Объекты этого класса задают символы, используемые при работе с текстами в программах C#. Класс относится к значимым типам и реализуется в виде структуры Char. Для символов класса Char используется двухбайтная кодировка Unicode, определяющая как мощность алфавита, включающего 2¹⁶ =65536 различных символов, так и порядок на алфавите. Если код символа s₁ меньше кода символа s₂, то символ s₁ предшествует в алфавите символу s₂ и справедливо неравенство s₁ < s₂. По символу нетрудно получить его код, поскольку существует неявное преобразование из типа Char в целочисленный тип int. Обратное преобразование также существует, но должно быть явным. Вот простой пример взаимных преобразований:

//преобразования int <-> char

Char s1 = 'Я', s2, s3;