Матрёшка: символы и строки

Много лет назад автору пришлось столкнуться с необходимостью обработки русскоязычных текстов, представленных в самых различных кодировках — ДКОИ, КОИ-8, ISO-8859-5, CP866 и Windows-1251. Стандартные средства Ada совершенно не подходили для решения подобной задачи. После многочисленных проб и ошибок зародилась идея создать специализированную библиотеку для обработки текстовых данных в удобном программисту виде. Спустя более 10 лет она сформировалась и обрела физическое воплощение в виде компонента проекта Матрёшка.

В основе лежит использование набора символов Unicode для представления текстовой информации. Набор символов Unicode не зависит от используемой кодировки текстовых данных и позволяет манипулировать более чем одним миллионом символов. Считается, что он включает все используемые и ранее использовавшиеся человечеством символы. Для представления символов и строк символов Матрёшка предлагает два типа данных: League.Characters.Universal_Character и League.Strings.Universal_String.

Тип Universal_Character предназначен в первую очередь для доступа к так называемой базе данных символов Unicode (Unicode Character Database), содержащей значения огромного количества свойств для каждого символа. У прикладного программиста очень редко возникает необходимость использовать этот тип.

Тип Universal_String предназначен для хранения и обработки последовательности символов Unicode. Длина строки не ограничена и может изменяться в процессе исполнения (по своему использованию этот тип напоминает стандартный тип Ada.Strings.Unbounded.Unbounded_String).

Создание и инициализация объектов Universal_String

Для создания и инициализации объектов‐строк из строковых литералов в программе может использоваться функция To_Universal_String, принимающая строку Wide_Wide_String и преобразующая её в объект Universal_String.

declare
   S : constant League.Strings.Universal_String
     := League.Strings.To_Universal_String ("Здравствуй, мир!");

begin

Как видно из примера, строка может содержать символы русского алфавита, однако необходимо корректно настроить компилятор на обработку кодировки в которой представлен текст программы. В случае использования GNAT наиболее простой путь заключается в использовании кодировки UTF-8 для хранения текста программы и ключа -gnatW8 для корректного преобразования кодировок строковых литералов.

«Обратное» преобразование из Universal_String в Wide_Wide_String осуществляется так же просто:

declare
   W : constant Wide_Wide_String := S.To_Wide_Wide_String;

begin

Для выполнения ввода‐вывода текстовых данных в настоящее время отсутствуют какие‐либо предопределённые пакеты, однако имеется возможность выполнять преобразования Universal_String в/из внешней кодировки с использованием текстового кодека. Более подробно использование текстового кодека для ввода/вывода текстовых данных рассмотрено в статье Матрёшка: обмен текстовыми данными.

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

Доступ к элементам строки

Строка Universal_String состоит из последовательности символов Universal_Character. Позиция каждого символа пронумерована, первый символ имеет индекс 1. Длину строки можно получить с использованием функции Length, а для проверки строки на отсутствие значения (нулевую длину) предназначена функция Is_Empty. Таким образом, простейший цикл для обхода всех символов строки будет иметь вид:

   for J in 1 .. S.Length loop
      Ada.Wide_Wide_Text_IO.Put (S.Element (J).To_Wide_Wide_Character);
   end loop;

Конкатенация символов и строк

Матрешка предоставляет полный набор операций конкатенации символов и строк, возвращающих результат в виде Universal_String. При этом возможно использование не только Universal_Character и Universal_String, но и Wide_Wide_Character и Wide_Wide_String.

declare
   use type League.Strings.Universal_String;

   S1 : constant Wide_Wide_String := "Привiт, ";
   S2 : constant League.Strings.Universal_String
     := League.Strings.To_Universal_String ("свiт");
   S3 : League.Strings.Universal_String;

begin
   S3 := S1 & S2 & '1';

Помимо операторов конкатенации для имеются две подпрограммы добавления строки к началу и в конец другой строки — Append и Prepend:

declare
   S1 : constant League.Strings.Universal_String
     := League.Strings.To_Universal_String ("Здравствуй");
   S2 : constant League.Strings.Universal_String
     := League.Strings.To_Universal_String (", ");
   S3 : constant League.Strings.Universal_String
     := League.Strings.To_Universal_String ("мир!");
   S  : League.Strings.Universal_String;

begin
   S := S2;
   S.Append (S3);
   S.Prepend (S1);

Значимым преимуществом использования подпрограммы Append вместо конкатенации является её более высокая прозводительность за счёт особенностей внутреннего управления динамической памятью.

Получение и замена подстроки

Для получения подстроки (или среза) предоставляется подпрограмма Slice:

declare
   S1 : constant League.Strings.Universal_String
     := League.Strings.To_Universal_String ("Здравствуй, мир!");
   S2 : League.Strings.Universal_String;

begin
   S2 := S1.Slice (S1.Length - 3, S1.Length - 1);

Подпрограмма Replace позволяет заменить подстроку другой подстрокой.

declare
   S1 : League.Strings.Universal_String
     := League.Strings.To_Universal_String ("Здравствуй, свiт!");
   S2 : constant League.Strings.Universal_String
     := League.Strings.To_Universal_String ("мир");

begin
   S1.Replace (13, 16, S2);

Поиск символа, подчсёт количества вхождений

Подпрограмма Index позволяет найти позицию первого вхождения символа в строку. Если указанный символ в строке не встречается, то она возвращает 0.

Подпрограмма Count возвращает количество вхождений указанного символа в строку. Разбиение строки

Подпрограмма Split позволяет разбить строку на вектор строк с использованием указанного символа‐разделителя. Опционально, она может удалить все вхождения пустых строк.

В качестве примера рассмотрим преобразования списка путей поиска исполняемых файлов в операционных сисемах POSIX в вектор строк, каждая из которых есть отдельно взятый путь:

declare
   Path  : constant League.Strings.Universal_String
     := League.Application.Environment.Value
         (League.Strings.To_Universal_String ("PATH"));
   Paths : constant League.String_Vectors.Universal_String_Vector
     := Path.Split (':');

begin

Сравнение

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

Матрёшка предлагает все основные операторы сравнения — „<“, „<=“, „=“, „>“, „>=“ — перегруженные для возможности использования типов Universal_String и Wide_Wide_String в качестве параметров сравнения. Но кроме этого предоставляется две дополнительные подпрограммы — Starts_With и Ends_With — позволяющие определить, что строка начинается с или заканчитвается второй указанной строкой:

declare
   S1 : constant League.Strings.Universal_String
     := League.Strings.To_Universal_String ("Здравствуй, мир!");
   S2 : constant League.Strings.Universal_String
     := League.Strings.To_Universal_String ("мир!");

begin
   if S1.Starts_With ("Здравствуй") then
      Ada.Wide_Wide_Text_IO.Put_Line ("Здравствуй");
   end if;

   if S1.Ends_With (S2) then
      Ada.Wide_Wide_Text_IO.Put_Line ("мир!");
   end if;

Использование строк со стандартными контейнерами

Часто строки используются совместно со стандартными контейнерами Ada2005/Ada2012. Для упрощения использования строк с хэшированными наборами и отображениями предоставляется специальная подпрограмма League.Strings.Hash, поэтому настройка стандартного контейнера, например набора, выглядит следующим образом:

with Ada.Containers.Hashed_Sets;

with League.Strings.Hash;

package String_Sets is
  new Ada.Containers.Hashed_Sets
       (League.Strings.Universal_String,
        League.Strings.Hash,
        League.Strings."=");

Нужно отметить, что подпрограмма League.Strings.Hash, совместимая с контейнерами выполнена как отдельная единица компиляции; а сам тип Universal_String имеет собственную операцию Hash, не совместимую со стандартными контейнерами, но удобную в использовании с префиксной нотацией.

Немного об эффективности

Для наиболее скептически настроенных или просто любопытных читателей несколько замечаний по внутреннему устройству и эффективности обработки строк.

Для внуреннего хранения сторовых данных используется кодировка UTF-16, что позволяет найти компромис между объёмом занимаемой данными памяти и эффективностью обработки.

Universal_String использует технику «копирование‐при‐модификации», т.е. время выполнения операции копирования объекта не зависит от длины данных.

Для обеспечения приемлемой надёжности при использовании в многопоточных приложениях без значительного снижения производительности или введения ограничений на использование объектов активно используются атомарные операции.

На процессорах Intel/AMD, поддерживающих набор команд SSE2, обработка данных осуществляется с привлечением инструкций этого набора, позволяющих выполнить за одну операцию обработку от четырёх до восьми символов. На остальных процессорах используется техника псевдовекторизации на регистрах общего назначения, позволяющая обработать за операцию один или два символа на 32‐битных систмеах и от двух до четырёх — на 64‐битных.

Для снижения количества операций распределений/освобождения памяти активно используется предвыделение и выравнивание размера выделяемого сегмента памяти по границам используемого системой алгоритма выделения памяти. В частности, на большинстве систем на восемь операций добавления символа в конец строки будет выполнено только одно выделение памяти.

Автор: Вадим Годунко
Дата: 11.08.2011