ПРЕДСТАВЛЕНИЕ ЧИСЛОВОЙ ИНФОРМАЦИИ - 4

REPRESENTATION OF NUMERICAL INFORMATION — 4

Valery Fedotov

Candidate of Physical and Mathematical Sciences, Head of the Department of Machine Learning, International Academy of Information Technology,

Russia, Saint-Petersburg

АННОТАЦИЯ

Четвёртая часть серии публикаций автора по заявленной теме посвящена метрическим пространствам символьных термов. Рассмотрены три метрики, их топологические свойства и аспекты практического использования.

ABSTRACT

The fourth part of the author's series of publications on the stated topic is devoted to metric spaces of symbolic terms. Three metrics, their topological properties and aspects of practical use are considered.

Ключевые слова: метрика, символ, терм, файл, система счисления.

Keywords: metric, symbol, term, file, number system.

Первые две части ([1] и [2]) этой серии были посвящены представлению чисел в различных (традиционных и информационных, включая башенные) системах счисления. Теперь перейдём к их связи с символьными термами.

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

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

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

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

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

Прежде всего, каждая кодовая страница подразумевает нумерацию используемых в ней символов. Терм в памяти компьютера содержит не сами символы, а только их номера (плюс нужную информацию о конкретной кодовой странице). Сколь бы огромна ни была кодовая страница, она конечна. Поэтому номера символов можно рассматривать в качестве цифр в системе счисления, основание которой равно мощности кодовой страницы. Тогда терм превращается в натуральное число, записанное в этой системе счисления, а файл терма — в запись этого натурального числа в двойной системе счисления, меньшее основание которой равно числу цифр, используемых для записи номеров (в практике программирования это могли быть 2, 3, 8, 10 или 16).

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

Совершенно иные способы представления используются при ручном вводе термов в различные устройства (набор текста, подача команд ЧПУ и т. д.). Здесь в роли символов выступают нажатия на клавиши, кнопки и прочие средства подачи сигналов.

Закончив предварительные определения и минимально необходимое погружение в контексты, перейдём к названной в заголовке теме. Рассмотрим два терма А и В. Через К обозначим число соответственно одинаковых символов в их начале (не исключён случай К=0). Если А и В различны, то расстоянием от А до В назовём

М(А,В) = 1/(К+1) .

Но если А=В, то считаем М(А,В) = 0 .

Проверим, что это расстояние обладает всеми свойствами метрики.

Рефлексивность М(А,А) = 0 специально была заложена в определении.

Симметричность М(А,В) = М(В,А) очевидна.

Остаётся проверить транзитивность. Пусть А, В и С — три терма, а К сохраняет прежний смысл. Через Р обозначим число соответственно одинаковых символов в начале В и С. Не теряя общности, считаем К≤Р  (в противном случае придётся поменять местами обозначения А и С). Прежде всего, если К=Р, то все три расстояния равны, значит, сумма любых двух из этих трёх (неотрицательных) слагаемых (вдвое) больше третьего.

Перейдём теперь к общему случаю К<Р . Рассмотрим символы, стоящие в разряде с номером К+1. Согласно выбору обозначения К, у А и В они различны. Но так как К<Р , то у В и С они одинаковы. Значит, у А и С они различны. Следовательно, М(А,В) = М(А,С).

Итак, получился «равнобедренный» треугольник с двумя «длинными» сторонами М(А,В) = М(А,С) = 1/(К+1) и третьей «короткой»

М(В,С) = 1/(Р+1) < 1/(К+1). Легко видеть, что все нужные неравенства треугольника в нём выполнены, что завершает доказательство транзитивности и свойств метрики.

Рассмотрим топологию, индуцированную этой метрикой. Здесь возникает несколько случаев в зависимости от ограничений на длину термов.

Если разрешены только конечные термы, длина которых не превосходит заданного порога Т, то все ненулевые расстояния превышают 1/(Т+2) . Значит, пространство строго дискретно (все его точки изолированы).

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

Многие свойства введённой метрики радикально отличаются от числовой прямой или евклидовой плоскости. Например, все расстояния не превышают 1.

Более интересное отличие обнаруживается, если определить середину отрезка ВС как такую точку А, для которой расстояния М(А,В) и М(А,С) равны между собой и равны половине расстояния М(В,С) . Если сохранить прежние обозначения, то из равенства расстояний М(А,В) = М(А,С) = 1/(К+1) получаем тот же «равнобедренный» треугольник с «короткой» третьей стороной ВС, что вступает в противоречие с требованием М(А,В) = М(А,С) = М(В,С) /2 . Значит, (ненулевые) отрезки в этом пространстве не имеют середин.

Более того, можно продолжить это рассуждение и показать, что ненулевые отрезки в этом пространстве не имеют не только середин, но даже никаких внутренних точек, если под внутренней точкой А на отрезке ВС понимать такую точку А, для которой расстояния М(А,В), М(А,С) и М(В,С) удовлетворяют равенству М(А,В) + М(А,С) = М(В,С) . Как следствие, получаем отсутствие у этого пространства линейной связности. Другими словами, в него невозможно непрерывно отображать обычные отрезки числовой прямой.

Однако, если ввести эту метрику на числовой прямой, точки которой представлены записью вещественных чисел в какой-либо основной системе счисления, то обе метрики индуцируют одну и ту же операцию предельного перехода. Действительно, рассмотрим какую-либо последовательность точек и её предел. При движении вдоль последовательности к её пределу расстояние от точки последовательности до предела рано или поздно становится меньше любого наперёд заданного 1/(К+1). Это значит, что в записи точки и предела в выбранной системе счисления рано или поздно совпадут не менее К первых цифр, что и доказывает равносильность обоих способов перехода к пределу.

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

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

М₁(А,В) = Σ (А_i — В_i) Хⁱ ,

где i — номера разрядов, а суммирование ведётся по всем разрядам, содержащим символ хотя бы в одном из двух термов. Но нужно кое-что уточнить.

Обычно разряды в записи натуральных чисел принято нумеровать справа налево (от конца записи к её началу), причём крайний правый разряд имеет номер 0. Чтобы получить в точности ту же самую метрику, сохраним это правило для алфавита, все символы которого являются цифрами некоторой системы счисления. Но если символы не имеют такого смысла, то удобнее нумеровать разряды слева направо. Кроме того, в этом случае 0 в нумерации символов нужно зарезервировать за «пустыми» разрядами, следующими после конца терма. Возможно, (по аналогии с цифрой 0) символ «пустого» разряда был заблаговременно предусмотрен в алфавите. Во избежание путаницы и иных нестыковок важно, чтобы его номер был именно нулём (как у незначащих нулей в цифровых алфавитах).

Если А и В — натуральные числа (а метрика построена корректно), то М₁(А,В) вне зависимости от выбора основания системы счисления совпадёт с абсолютной величиной разности между А и В. Ясно, что М₁(А,В) всегда окажется натуральным числом, в том числе, и в случае нечисловых термов. Следовательно, пространство строго дискретно.

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

М₂(А,В) = Σ (А_i — В_i) Х^—i .

Хотя термы А и В при этом как бы не изменились, формула подсказывает совершенно другую их интерпретацию. Отрицательные номера обычно относят к разрядам дробной части числа. Значит, терм нужно трактовать как дробь, значение которой заключено между 0 и 1.

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

Наконец, аналогом смешанных чисел (имеющих непустые целую и дробную часть) служат сдвоенные термы. Первая часть сдвоенного терма обязательно должна быть конечной, а вторая может быть бесконечной. Формула для расстояния внешне ничем не отличается от записанной выше для М₁ , но контекст совсем иной. Индексы i принимают теперь значения обоих знаков. При этом неотрицательные значения индексов относятся к первой части сдвоенного терма, а отрицательные — ко второй. Важно заметить, что разделителем частей сдвоенного терма в этом случае должен быть символ, формально не входящий в состав алфавита (даже если в состав алфавита есть свой символ, внешне ничем не отличающийся от разделителя частей сдвоенного терма), а его позиция в терме не должна иметь никакого разрядного номера.

А ещё вспомним про разряд для знака. Если знаки А и В противоположны, то минус в скобках в формуле для М₁ нужно заменить плюсом, тогда как минус в начале записи числа подставлять в эту формулу не следует (более того, как и в случае разделителя его следует считать внеалфавитным символом).

Список литературы:

1. Федотов В. П. Представление числовой информации — 1 //Sciences of Europe . – 2022. – №. 100. – С. 63-72.
2. Федотов В. П. Представление числовой информации — 2 //Sciences of Europe. – 2022. – №. 100. – С. 73-81.