Счетчик символов - это целое число, и для него отводится доста-
точное количество битов, чтобы их с избытком хватало для предс-
тавления длины самой длинной строки,какую только можно предста-
вить в данной машине. Обычно для счетчика отводят от 8 до 16
битов. Тогда при таком представлении издержки памяти в расчете на
одну строку составляют 1-2 символа. При использовании счетчика
символов возможен произвольный доступ к символам в пределах стро-
ки, поскольку можно легко проверить, что обращение не выходит за
пределы строки. Счетчик размещается в таком месте, где он может
быть легко доступен - начале строки или в дескрипторе строки.
Максимально возможная длина строки, таким образом, ограничена
разрядностью счетчика. В PASCAL, например, строка представляется
в виде массива символов, индексация в котором начинается с 0; од-
нобайтный счетчик числа символов в строке является нулевым эле-
ментом этого массива. Такое представление строк показано на
рис.4.5. И счетчик символов, и признак конца в предыдущем случае
могут быть доступны для программиста как элементы вектора.
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 3 │ A │ B │ D │ │ 8 │ P │ Q │ R │ S │ T │ U │ V │ W │
└───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┴───┘
Рис.4.5. Представление строк переменной длины
со счетчиком
В двух предыдущих вариантах обеспечивалось максимально эф-
фективное расходование памяти (1-2 "лишних" символа на строку),
но изменчивость строки обеспечивалась крайне неэффективно. Пос-
кольку вектор - статическая структура, каждое изменение длины
строки требует создания нового вектора, пересылки в него неизме-
няемой части строки и уничтожения старого вектора. Это сводит на
нет все преимущества работы со статической памятью. Поэтому наи-
более популярным способом представления строк в памяти являются
вектора с управляемой длиной.
ВЕКТОР С УПРАВЛЯЕМОЙ ДЛИНОЙ. Память под вектор с управляемой
длиной отводится при создании строки и ее размер и размещение ос-
таются неизменными все время существования строки. В дескрипторе
такого вектора-строки может отсутствовать начальный индекс, так
как он может быть зафиксирован раз навсегда установленными согла-
шениями, но появляется поле текущей длины строки. Размер строки,
таким образом, может изменяться от 0 до значения максимального
индекса вектора. "Лишняя" часть отводимой памяти может быть за-
полнена любыми кодами - она не принимается во внимание при опери-
ровании со строкой. Поле конечного индекса может быть использова-
но для контроля превышения длиной строки объема отведенной памя-
ти. Представление строк в виде вектора с управляемой длиной (при
максимальной длине 10) показано на рис.4.6.
Хотя такое представление строк не обеспечивает экономии па-
мяти, проектировщики систем программирования, как видно, считают
это приемлемой платой за возможность работать с изменчивыми стро-
ками в статической памяти. Дескрипторы строк
┌───┐ ┌───┐
Максимальная длина │10 │ │10 │
Текущая длина │ 3 │ │ 8 │
Указатель на данные │ * │ │ * │
└─┼─┘ └─┼─┘
┌──────────────────────┘ │
│ Области данных строк │
│ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
└>│A│B│D│?│?│?│?│?│?│?│ └──>│P│Q│R│S│T│U│V│W│?│?│
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
Рис.4.6. Представление строк вектором с управляемой длиной
В программном примере 4.4 приведен модуль, реализующий
представление строк вектором с управляемой длиной и некоторые опе-
рации над такими строками. Для уменьшения объема в примере в сек-
ции Implementation определены не все процедуры/функции. Предос-
тавляем читателю самостоятельно разработать прочие объявленные в
секции Interface подпрограммы. Дескриптор строки описывается ти-
пом _strdescr, который в точности повторяет структуру, показанную
на рис.4.6. Функция NewStr выделяет две области памяти: для деск-
риптора строки и для области данных строки. Адрес дескриптора
строки, возвращаемый функцией NewStr - тип varstr - является той
переменной, значение которой указывается пользователем модуля для
идентификации конкретной строки при всех последующих операциях с
нею. Область данных, указатель на которую заносится в дескрипторе
строки - тип _dat_area - описана как массив символов максимально-
го возможного объема - 64 Кбайт. Однако, объем памяти, выделяемый
под область данных функцией NewStr, как правило, меньший - он за-
дается параметром функции. Хотя индексы в массиве символов строки
теоретически могут изменяться от 1 до 65535, значение индекса в
каждой конкретной строке при ее обработке ограничивается полем
maxlen дескриптора данной строки. Все процедуры/функции обработки
строк работают с символами строки как с элементами вектора, обра-
щаясь к ним по индексу. Адрес вектора процедуры получают из деск-
риптора строки. Обратите внимание на то, что в процедуре CopyStr
длина результата ограничивается максимальной длиной целевой стро-
ки.
{==== Программный пример 4.4 ====}
{ Представление строк вектором с управляемой длиной }
Unit Vstr;
Interface
type _dat_area = array[1..65535] of char;
type _strdescr = record { дескриптор строки }
maxlen, curlen : word; { максимальная и текущая длины }
strdata : ^_dat_area; { указатель на данные строки }
end;
type varstr = ^_strdescr; { тип - СТРОКА ПЕРЕМЕННОЙ ДЛИНЫ }
Function NewStr(len : word) : varstr;
Procedure DispStr(s : varstr);
Function LenStr(s : varstr) : word;
Procedure CopyStr(s1, s2 : varstr);
Function CompStr(s1, s2 : varstr) : integer;
Function PosStr(s1, s2 : varstr) : word;
Procedure ConcatStr(var s1: varstr; s2 : varstr);
Procedure SubStr(var s1 : varstr; n, l : word);
Implementation
{** Создание строки; len - максимальная длина строки;
ф-ция возвращает указатель на дескриптор строки }
Function NewStr(len : word) : varstr;
var addr : varstr;
daddr : pointer;
begin
New(addr); { выделение памяти для дескриптора }
Getmem(daddr,len); { выделение памяти для данных }
{ занесение в дескриптор начальных значений }
addr^.strdata:=daddr; addr^.maxlen:=len; addr^.curlen:=0;
Newstr:=addr;
end; { Function NewStr }
Procedure DispStr(s : varstr); {** Уничтожение строки }
begin
FreeMem(s^.strdata,s^.maxlen); { уничтожение данных }
Dispose(s); { уничтожение дескриптора }
end; { Procedure DispStr }
{** Определение длины строки, длина выбирается из дескриптора }
Function LenStr(s : varstr) : word;
begin
LenStr:=s^.curlen;
end; { Function LenStr }
Procedure CopyStr(s1, s2 : varstr); { Присваивание строк s1:=s2}
var i, len : word;
begin
{ длина строки-результата м.б. ограничена ее макс. длиной }
if s1^.maxlen<s2^.curlen then len:=s1^.maxlen
else n:=s2^.curlen;
{ перезапись данных и установка длины результата }
for i:=1 to n do s1^.strdata^[i]:=s2^.strdata^[i];
s1^.curlen:=len;
end; { Procedure CopyStr }
{** Сравнение строк - возвращает:
0, если s1=s2; 1 - если s1>s2; -1 - если s1<s2 }
Function CompStr(s1, s2 : varstr) : integer;
var i : integer;
begin i:=1; { индекс текущего символа }
{ цикл, пока не будет достигнут конец одной из строк }
while (i<=s1^.curlen) and (i<=s2^.curlen) do
{ если i-ые символы не равны, функция заканчивается }
begin if s1^.strdata^[i]>s2^.strdata^[i] then
begin CompStr:=1; Exit; end;
if s1^.strdata^[i]<s2^.strdata^[i] then
begin CompStr:=-1; Exit; end;
i:=i+1; { переход к следующему символу }
end;
{ если выполнение дошло до этой точки, то найден конец одной из
строк, и все сравненные до сих пор символы были равны;
строка меньшей длины считается меньшей }
if s1^.curlen<s2^.curlen then CompStr:=-1
else if s1^.curlen>s2^.curlen then CompStr:=1
else CompStr:=0;
end; { Function CompStr }
.
.
END.
СИМВОЛЬНО-СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ СТРОК. Списковое представле-
ние строк в памяти обеспечивает гибкость в выполнении разнообраз-
ных операций над строками (в частности, операций включения и иск-
лючения отдельных символов и целых цепочек) и использование сис-
темных средств управления памятью при выделении необходимого объ-
ема памяти для строки. Однако, при этом возникают дополнительные
расходы памяти. Другим недостатком спискового представления стро-
ки является то, что логически соседние элементы строки не являют-
ся физически соседними в памяти. Это усложняет доступ к группам
элементов строки по сравнению с доступом в векторном представле-
нии строки.
ОДНОНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК. Каждый символ строки
представляется в виде элемента связного списка; элемент содержит
код символа и указатель на следующий элемент, как показано на
рис.4.7. Одностороннее сцепление представляет доступ только в од-
ном направлении вдоль строки. На каждый символ строки необходим
один указатель, который обычно занимает 2-4 байта.
┌───┬───┐ ┌───┬───┐ ┌───┬───┐
──>│ A │ ─┼──>│ B │ ─┼──>│ D │nil│
└───┴───┘ └───┴───┘ └───┴───┘
Рис.4.7. Представление строки
однонаправленным связным списком
ДВУНАПРАВЛЕННЫЙ ЛИНЕЙНЫЙ СПИСОК. В каждый элемент списка до-
бавляется также указатель на предыдущий элемент, как показано на
рис.4.8. Двустороннее сцепление допускает двустороннее движение
вдоль списка, что может значительно повысить эффективность выпол-
нения некоторых строковых операция. При этом на каждый символ
строки необходимо два указателя , т.е. 4-8 байт.
┌───┬───┬───┐ ┌───┬───┬───┐ ┌───┬───┬───┐
───>│ │ │ ─┼────>│ │ │ ─┼────>│ │ │nil│
│ │ A │ │ │ │ B │ │ │ │ D │ │
│nil│ │ │<────┼─ │ │ │<────┼─ │ │ │
└───┴───┴───┘ └───┴───┴───┘ └───┴───┴───┘
Рис.4.8. Представление строки двунаправленным
связным списком
БЛОЧНО-СВЯЗНОЕ ПРЕДСТАВЛЕНИЕ СТРОК. Это представление позво-
ляет в болшинстве операций избежать затрат, связанных с управле-
нием динамической памятью, но в то же время обеспечивает доста-
точно эффективное использование памяти при работе со строками пе-
ременной длины.
МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ ФИКСИРОВАННОЙ ДЛИНЫ. Многосимвольные
группы (звенья) организуются в список, так что каждый элемент
списка, кроме последнего, содержит группу элементов строки и ука-
затель следующего элемента списка. Поле указателя последнего эле-
мента списка хранит признак конца - пустой указатель. В процессе
обработки строки из любой ее позиции могут быть исключены или в
любом месте вставлены элементы, в результате чего звенья могут
содержать меньшее число элементов, чем было первоначально. По
этой причине необходим специальный символ, который означал бы от-
сутствие элемента в соответствующей позиции строки. Обозначим та-
кой символ 'emp', он не должен входить в множество символов,из
которых организуется строка. Пример многосимвольных звеньев фик-
сированной длинны по 4 символа в звене показан на рис.4.9.
┌───┬───┬───┬───┬───┐
───>│ A │ B │ D │emp│nil│
└───┴───┴───┴───┴───┘
┌───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┐
───>│ P │ Q │ R │ S │ ─┼──>│ T │ U │ V │ W │nil│
└───┴───┴───┴───┴───┘ └───┴───┴───┴───┴───┘
Рис. 4.9. Представление строки многосимвольными
звеньями постоянной длины
Такое представление обеспечивает более эффективное использо-
вание памяти, чем символьно-связное. Операции вставки/удаления в
ряде случаев могут сводиться к вставке/удалению целых блоков. Од-
нако, при удалении одиночных символов в блоках могут накапливать-
ся пустые символы emp, что может привести даже к худшему исполь-
зованию памяти, чем в символьно-связном представлении.
МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ ПЕРЕМЕННОЙ ДЛИНЫ. Переменная длинна
блока дает возможность избавиться от пустых символов и тем самым
экономить память для строки. Однако появляется потребность в спе-
циальном символе - признаке указателя, на рис.4.10 он обозначен
символом 'ptr'.
С увеличением длины групп символом, хранящихся в блоках, эф-
фективность использования памяти повышается. Однако негативной
характеристикой рассматриваемого метода является усложнение опе-
раций по резервированию памяти для элементов списка и возврату
освободившихся элементов в общий список доступной памяти.
┌───┬───┬───┬───┐ ┌───┬───┬───┐
─>│ A │ B │ptr│ ─┼───>│ D │ptr│nil│
└───┴───┴───┴───┘ └───┴───┴───┘
┌───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┐
─>│ P │ptr│ ─┼─>│ Q │ R │ S │ T │ U │ptr│ ─┼─>│ V │ W │ptr│nil│
└───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┴───┘
Рис.4.10. Представление строки многосимвольными звеньями
переменной длины
Такой метод спискового представления строк особенно удобен в
задачах редактирования текста, когда большая часть операций при-
ходится на изменение, вставку и удаление целых слов. Поэтому в
этих задачах целесообразно список организовать так, чтобы каждый
его элемент содержал одно слово текста. Символы пробела между
словами в памяти могут не представляются.
МНОГОСИМВОЛЬНЫЕ ЗВЕНЬЯ С УПРАВЛЯЕМОЙ ДЛИНОЙ. Память выделя-
ется блоками фиксированной длины. В каждом блоке помимо символов
строки и указателя на следующий блок содержится номера первого и
последнего символов в блоке. При обработке строки в каждом блоке
обрабатываются только символы, расположенные между этими номера-
ми. Признак пустого символа не используется: при удалении символа
из строки оставшиеся в блоке символы уплотняются и корректируются
граничные номера. Вставка символа может быть выполнена за счет
имеющегося в блоке свободного места, а при отсутствии такового -
выделением нового блока. Хотя операции вставки/удаления требуют
пересылки символов, диапазон пересылок ограничивается одним бло-
ком. При каждой операции изменения может быть проанализирована
заполненность соседних блоков и два полупустых соседних блока мо-
гут быть переформированы в один блок. Для определения конца стро-
ки может использоваться как пустой указатель в последнем блоке,
так и указатель на последний блок в дескрипторе строки. Последнее
может быть весьма полезным при выполнении некоторых операций,
например, сцепления. В дескрипторе может храниться также и длина
строки: считывать ее из дескриптора удобнее, чем подсчитывать ее
перебором всех блоков строки.
Пример представления строки в виде звеньев с управляемой
длиной 8 показан на рис.4.10.
В программном примере 4.5 приведен модуль, реализующий
представление строк звеньями с управляемой длиной. Даже с первого
Дескриптор
┌────┐ ╓─╥─╥─┬─┬─┬─┬─┬─┬─┬─╥───╖ ╓─╥─╥─┬─┬─┬─┬─┬─┬─┬─╥───╖
│ 50 │ ┌─>║1║8║П│р│е│д│с│т│а│в║ ─╫─>║2║7║?│л│е│н│и│е│ │?║ ─╫┐
│ ──┼─┘ ╙─╨─╨─┴─┴─┴─┴─┴─┴─┴─╨───╜ ╙─╨─╨─┴─┴─┴─┴─┴─┴─┴─╨───╜│
│ ──┼┐ ┌─────────────────────────────────────────────────────┘
└────┘│ │ ╓─╥─╥─┬─┬─┬─┬─┬─┬─┬─╥───╖ ╓─╥─╥─┬─┬─┬─┬─┬─┬─┬─╥───╖
│ └>║1║8║с│т│р│о│к│и│ │з║ ─╫─>║1║8║в│е│н│ь│я│м│и│ ║ ─╫┐
│ ╙─╨─╨─┴─┴─┴─┴─┴─┴─┴─╨───╜ ╙─╨─╨─┴─┴─┴─┴─┴─┴─┴─╨───╜│
│ ┌─────────────────────────────────────────────────────┘
│ │ ╓─╥─╥─┬─┬─┬─┬─┬─┬─┬─╥───╖ ╓─╥─╥─┬─┬─┬─┬─┬─┬─┬─╥───╖
│ └>║1║8║с│ │у│п│р│а│в│л║ ─╫─>║1║8║я│е│м│о│й│ │д│л║ ─╫┐
│ ╙─╨─╨─┴─┴─┴─┴─┴─┴─┴─╨───╜ ╙─╨─╨─┴─┴─┴─┴─┴─┴─┴─╨───╜│
│ ┌─────────────────────────────────────────────────────┘
│ │ ╓─╥─╥─┬─┬─┬─┬─┬─┬─┬─╥───╖
└>└>║1║4║и│н│о│й│?│?│?│?║nil║
╙─╨─╨─┴─┴─┴─┴─┴─┴─┴─╨───╜
Рис.4.10. Представление строки звеньями управляемой длины
взгляда видно, что он значительно сложнее, чем пример 4.4. Это
объясняется тем, что здесь вынуждены обрабатывать как связные
(списки блоков), так и векторные (массив символов в каждом блоке)
структуры. Поэтому при последовательной обработке символов строки
процедура должна сохранять как адрес текущего блока, так и номер
текущего символа в блоке. Для этих целей во всех процедурах/функ-
циях используются переменные cp и bi соответственно. (Процедуры и
функции, обрабатывающие две строки - cp1, bi1, cp2, bi2.) Деск-
риптор строки - тип _strdescr - и блок - тип _block - в точности
повторяют структуру, показанную на рис.4.10. Функция NewStr выде-
ляет память только для дескриптора строки и возвращает адрес
дескриптора - тип varstr - он служит идентификатором строки при
последующих операциях с нею. Память для хранения данных строки
выделяется только по мере необходимости. Во всех процедурах/функ-
циях приняты такие правила работы с памятью:
- если выходной строке уже выделены блоки, используются эти
уже выделенные блоки;
- если блоки, выделенные выходной строке исчерпаны, выделя-
ются новые блоки - по мере необходимости;
- если результирующее значение выходной строки не использует
все выделенные строке блоки, лишние блоки освобождаются.
Для освобождения блоков определена специальная внутренняя
функция FreeBlock, освобождающая весь список блоков, голова кото-
рого задается ее параметром.
Обратите внимание на то, что ни в каких процедурах не конт-
ролируется максимальный объем строки результата - он может быть
сколь угодно большим, а поле длины в дескрипторе строки имеет тип
longint.
{==== Программный пример 4.5 ====}
{ Представление строки звеньями управляемой длины }
Unit Vstr;
Interface
const BLKSIZE = 8; { число символов в блоке }
type _bptr = ^_block; { указатель на блок }
_block = record { блок }
i1, i2 : byte; { номера 1-го и последнего символов }
strdata : array [1..BLKSIZE] of char; { символы }
next : _bptr; { указатель на следующий блок }
end;
type _strdescr = record { дескриптор строки }
len : longint; { длина строки }
first, last : _bptr; { указ.на 1-й и последний блоки }
end;
type varstr = ^_strdescr; { тип - СТРОКА ПЕРЕМЕННОЙ ДЛИНЫ }
Function NewStr : varstr;
Procedure DispStr(s : varstr);
Function LenStr(s : varstr) : longint;
Procedure CopyStr(s1, s2 : varstr);
Function CompStr(s1, s2 : varstr) : integer;
Function PosStr(s1, s2 : varstr) : word;
Procedure ConcatStr(var s1: varstr; s2 : varstr);
Procedure SubStr(var s : varstr; n, l : word);
Implementation
Function NewBlock :_bptr; {Внутр.функция-выделение нового блока}
var n : _bptr;
i : integer;
begin
New(n); { выделение памяти }
n^.next:=nil; n^.i1:=0; n^.i2:=0; { начальные значения }
NewBlock:=n;
end; { NewBlock }
{*** Внутр.функция - освобождение цепочки блока, начиная с c }
Function FreeBlock(c : _bptr) : _bptr;
var x : _bptr;
begin { движение по цепочке с освобождением памяти }
while c<>nil do begin x:=c; c:=c^.next; Dispose(x); end;
FreeBlock:=nil; { всегда возвращает nil }
end; { FreeBlock }
Function NewStr : varstr; {** Создание строки }
var addr : varstr;
begin
New(addr); { выделение памяти для дескриптора }
{ занесение в дескриптор начальных значений }
addr^.len:=0; addr^.first:=nil; addr^.last:=nil;
Newstr:=addr;
end; { Function NewStr }
Procedure DispStr(s : varstr); {** Уничтожение строки }
begin
s^.first:=FreeBlock(s^.first); { уничтожение блоков }
Dispose(s); { уничтожение дескриптора }
end; { Procedure DispStr }
{** Определение длины строки, длина выбирается из дескриптора }
Function LenStr(s : varstr) : longint;
begin
LenStr:=s^.len;
end; { Function LenStr }
{** Присваивание строк s1:=s2 }
Procedure CopyStr(s1, s2 : varstr);
var bi1, bi2 : word; { индексы символов в блоках для s1 и s2 }
cp1, cp2 : _bptr; { адреса текущих блоков для s1 и s2 }
pp : _bptr; { адрес предыдущего блока для s1 }
begin
cp1:=s1^.first; pp:=nil; cp2:=s2^.first;
if s2^.len=0 then begin
{ если s2 пустая, освобождается вся s1 }
s1^.first:=FreeBlock(s1^.first); s1^.last:=nil;
end
else begin
while cp2<>nil do begin { перебор блоков s2 }
if cp1=nil then begin { если в s1 больше нет блоков }
{ выделяется новый блок для s1 }
cp1:=NewBlock;
if s1^.first=nil then s1^.first:=cp1
else if pp<>nil then pp^.next:=cp1;
end;
cp1^:=cp2^; { копирование блока }
{ к следующему блоку }
pp:=cp1; cp1:=cp1^.next; cp2:=cp2^.next;
end; { while }
s1^.last:=pp; { последний блок }
{ если в s1 остались лишние блоки - освободить их }
pp^.next:=FreeBlock(pp^.next);
end; { else }
s1^.len:=s2^.len;
end; { Procedure CopyStr }
{** Сравнение строк - возвращает:
0, если s1=s2; 1 - если s1>s2; -1 - если s1<s2 }
Function CompStr(s1, s2 : varstr) : integer;
var bi1, bi2 : word;
cp1, cp2 : _bptr;
begin
cp1:=s1^.first; cp2:=s2^.first;
bi1:=cp1^.i1; bi2:=cp2^.i1;
{ цикл, пока не будет достигнут конец одной из строк }
while (cp1<>nil) and (cp2<>nil) do begin
{ если соответств.символы не равны, ф-ция заканчивается }
if cp1^.strdata[bi1]>cp2^.strdata[bi2] then begin
CompStr:=1; Exit;
end;
if cp1^.strdata[bi1]<cp2^.strdata[bi2] then begin
CompStr:=-1; Exit;
end;
bi1:=bi1+1; { к следующему символу в s1 }
if bi1>cp1^.i2 then begin cp1:=cp1^.next; bi1:=cp1^.i1; end;
bi2:=bi2+1; { к следующему символу в s2 }
if bi2>cp2^.i2 then begin cp2:=cp2^.next; bi2:=cp2^.i1; end;
end;
{ мы дошли до конца одной из строк,
строка меньшей длины считается меньшей }
if s1^.len<s2^.len then CompStr:=-1
else if s1^.len>s2^.len then CompStr:=1
else CompStr:=0;
end; { Function CompStr }
.
END.
Чтобы не перегружать программный пример, в него не включены
средства повышения эффективности работы с памятью. Такие средства
включаются в операции по выбору программиста. Обратите внимание,
например, что в процедуре, связанной с копированием данных (Co-
pyStr) у нас копируются сразу целые блоки. Если в блоке исходной
строки были неиспользуемые места, то они будут и в блоке резуль-
тирующей строки. Посимвольное копирование позволило бы устранить
избыток памяти в строке-результате. Оптимизация памяти, занимае-
мой данными строки может производится как слиянием соседних полу-
пустых блоков, так и полным уплотнением данных. В дескриптор
строки может быть введено поле - количество блоков в строке. Зная
общее количество блоков и длину строки можно при выполнении неко-
торых операций оценивать потери памяти и выполнять уплотнение,
если эти потери превосходят какой-то установленный процент.