Око, рок и рококо

Показывать лекцию целиком

Если у нас есть числа, то оперируя с числами можно решать разнообразные задачи,- находить корни квадратного уравнения, вычислять траектории полета к луне или другим планетам, определять оптимальные характеристики проектируемых самолетов, многие, многие задачи. Как правило, все современные сложные задачи решаются на компьютере. Изначально, компьютер умеет не много. Его система команд включает такие операции, как сложение, умножение, деление, сравнение двоичных чисел. На основе этих элементарных операций можно написать программы, вычисляющие стандартные функции, например, sin(x) и другие. Идя по этому пути, благодаря программированию, можно решать самые сложные задачи.

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

Еще одна важная для программистов задача - задача трансляции текста программы, написанного на алгоритмическом языке, в программу, написанную в командах компьютера. Это сложная задача, но успешно решаемая. Разработаны компиляторы для многочисленных алгоритмических языков.

Другая не менее важная задача – это задача перевода текста, написанного на одном естественном языке, в текст на другом естественном языке с сохранением смысла текста, например, перевод текстов с русского на английский, или с английского на китайский. Эту задачу удалось пока решить лишь частично. Хороших программ, позволяющих переводить художественные тексты, не существует, но есть множество программ, позволяющих выполнить подстрочный перевод, переводя слова и отдельные фразы.

Над числами определены элементарные операции и функции, используя которые можно решать более сложные задачи.

Какие же элементарные функции и операции используются при работе с текстами – словами в некотором алфавите?

Первая операция (функция), которую мы рассмотрим называется операцией конкатенации, или сцепления. Обычно для ее обозначения используется символ сложения "+".

Если s₁ и s₂ – слова, то конкатенацией слов s₁ и s₂ называется слово s₃, полученное приписыванием слова s₂ в конец слова s₁. Операцию конкатенации двух слов будем записывать в виде:

s₃ = s₁ + s₂

Далее наряду с термином "слово в алфавите Т" будем использовать его синоним – "строка в алфавите Т", или короче "слово" и "строка", упоминая алфавит, только тогда, когда требуется уточнить, о каком именно алфавите идет речь.

Константные строки, составленные из символов алфавита, будем записывать, заключая строку в кавычки. Пусть например s₁ = "ведь", s₂ = "мед", тогда s₃ = s₁ + s₂ будет иметь значение "ведьмед", но s₃ = s₂ + s₁ будет иметь значение "медведь".

Пусть например s₁ = "рок", s₂ = "око", тогда s₃ = s₁ + s₂ будет иметь значение "рококо", но s₃ = s₂ + s₁ будет иметь значение "окорок".

Пусть s – слово длины m, представимое в виде s = c₁ c₂… c_m, где c_k – символы алфавита. Подстрокой строки s будем называть строку s₁ = c_j c_j+1… c_j+n, где

j >= 1, j + n <= m

Для работы с текстами полезно иметь следующий набор функций над строками:

Length(s) – в качестве результата эта функция возвращает длину строки s. Вот примеры применения этой функции. Пусть s = "рококо", n = Length(s). В результате значение n равно 6. Если s = "рок, кок и око", то n = Length(s) = 14, учитывая символы пробелов и запятых.

Substring(s, k, n) – в качестве результата эта функция возвращает подстроку строки s длины n, начинающуюся в позиции k. Будем полагать, что нумерация символов строки начинается с 1. Будем также полагать, что в качестве результата возвращается пустая строка, если k и n заданы некорректно, не позволяя задать подстроку строки s. Вот примеры применения этой функции. Пусть s = "рококо". s₁ = Substring(s, 2, 3). В результате значение s₁ равно "око". Если s₁ = Substring(s, 4, 3), то значением s₁ также равно "око", но, если s₁ = Substring(s, 5, 3), то s₁ получит значением пустой строки "", - значение пустого слова ε, - строки, не содержащей символов.

Insert(s, s₁, k) – в качестве результата эта функция возвращает строку s, в которую, начиная с позиции k вставлена подстрока s₁. Вот примеры применения этой функции.

Пусть s = "поход". s₁ = Insert(s, "ар", 2). В результате значение s₁ равно "пароход".

Если s = "монна", s₁ равно "ад", s₂ = Insert(s, s₁, 2), то s₂ получит значение "мадонна".

Remove(s, k, n) – в качестве результата эта функция возвращает строку s, в которой, начиная с позиции k удалена подстрока длины n.