Результат интеллектуальной деятельности: СПОСОБ КОДИРОВАНИЯ И ВЫЧИСЛЕНИЯ ДАТЫ С ИСПОЛЬЗОВАНИЕМ УПРОЩЕННОГО ФОРМАТА В ЦИФРОВЫХ УСТРОЙСТВАХ

Область техники, к которой относится изобретение

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

Уровень техники

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

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

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

Так, известен способ кодирования и преобразования даты в программном обеспечении (ПО) SQL Server 2005 и SQL Server 2012 компании Microsoft [1, 2].

Для хранения даты и времени отводится два 4-байтовых целых числа (всего используется 8 байт). Первые 4 байта используются для хранения собственно даты и содержат количество дней до или после даты отсчета, в качестве которой выбрано 1 января 1900 года (для типа данных datetime; вторые 4 байта содержат текущее значение времени, представленного в виде трехсотых долей секунды, прошедших после полуночи).

Используется также хранение даты и времени с меньшей точностью. В этом варианте даты хранятся в виде 2-байтового целого числа, представляющего количество дней, прошедших с 1 января 1900 года (для типа данных smalldatetime; в двух следующих байтах хранится количество минут, прошедших после полуночи).

Таким образом, дата может храниться в виде целого числа и минимально занимать 2 байта (16 бит).

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

a(M-14)div 12,

y=Y+4800-a,

m=M+12*a-3,

J=D+(153*m+2) div 5+365*y+y div 4 - y div 100+y div 400-32075,

где a, y, m - промежуточные переменные целого типа;

M - месяц года, от 1 (январь) до 12 (декабрь);

D - день месяца, от 1 до 31;

Y - год григорианского календаря.

После этого для получения N из полученного значения J (номер юлианского дня для исходной даты) вычитают константу J0, которая зависит от стартовой даты и является номером юлианского дня для стартовой даты.

Однако для обратного преобразования целого числа N в дату используется еще большее количество преобразований и вычислений, сначала получают номер юлианского дня J, прибавляя константу J0, далее вычисляют

j=J+32044,

g=j div 146097,

dg=j mod 146097,

c=(dg div 36524+1)×3 div 4,

dc=dg-с×36524,

b=dc div 1461,

db=dc mod 1461,

a=(db div 365+1)×3 div 4,

da=db-a×365,

y=g×400+c×100+b×4+a,

m=(da×5+308)div 153-2,

d=da-(m+4)×153 div 5+122,

Y=y-4800+(m+2)div 12,

M=(m+2)mod 12+1,

D-d+1,

где b, с, d, j, g, da, db, dc, dg - промежуточные переменные целого типа.

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

Известен также способ кодирования и преобразования даты в ПО системы управления базами данных (СУБД) Oracle 7 компании Oracle [4].

Данные даты хранятся в фиксированных полях длиной 4 байта, соответствующих веку, году, месяцу, дню (еще 3 байта отведены для часа, минут и секунд). Соответственно, используемый способ позволяет хранить даты в диапазоне от 1 января 4712 года до н.э. до 31 декабря 4712 года нашей эры.

Номер юлианского дня позволяет датировать события от общей точки (эта точка принимается за 1 января 4712 г. до н.э. по юлианскому календарю). Для представления номера юлианского календаря используются целые числа. Метод, используемый в СУБД Oracle, представляет дату в виде семизначного числа (для наиболее часто используемых дат), так, например, 8 апреля 1991 года будет представлено в виде 2448355. Для преобразования даты во внутренний формат и наоборот используются специально созданные внутренние системные функции.

Такой метод позволяет упростить вычисления даты. Если значения байт принять N1, N2, N3, N4, тогда

D=N4,

M=N3,

Y=N1*100+N2.

Прямое преобразование даты в целое число N из 4 байт также несложно:

N1=Y div 100,

N2=Y mod 100,

N3=M,

N4=D.

Описанный способ принят за прототип.

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

Раскрытие изобретения

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

Для этого предлагается способ, заключающийся в том, что

- выделяют для хранения данных о дате, включающей год, месяц и день, целое число длиной К бит;

- устанавливают для отсчета фиксированную дату как первое января определенного года Y0;

- вводят значения текущего года Y, месяца М, дня D;

- вычисляют целое число N для хранения данных о дате по формуле

N=D+(М-1)*32+(Y-Y0)*384.

Вычисление N по приведенной формуле означает, что:

- первые 5 бит двоичного представления числа N выделяют для дня месяца хранимой даты;

- оставшиеся К - 5 бит двоичного представления числа N выделяют для числа месяцев, прошедших после фиксированной даты. Затем сохраняют число N в двоичном формате. При необходимости обратного преобразования вычисляют дату по формулам

D=N mod 32,

M=(N div 32)mod 12+1,

Y=Y0+(N div 384),

где div - операция целочисленного деления (деления с отбрасыванием дробной части);

mod - операция взятия остатка от целочисленного деления.

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

В предложенном способе оба этих подхода комбинируются: день месяца хранится в своем наборе бит, а оставшаяся часть данных хранится в виде числа месяцев - не минимальных квантов изменения даты, прошедших со стартовой даты. Очевидным эффектом предложенного способа является компактность представления - максимальное число дней в месяце (31 день) весьма близко к степени числа два (2⁵=32), поэтому информационная избыточность предложенного способа хранения всего около 0,3 бита (log₂(12*32/365)). Поскольку информационная избыточность меньше одного бита, то для существенной части требуемых диапазонов дат требуемое число бит будет минимально возможным.

Сложность преобразований при этом оказывается такой же, как и для раздельного хранения компонент даты, т.е. минимальной.

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

Можно показать преимущество предложенного способа на следующем примере.

Пусть требуется представление даты, покрывающее диапазон в 150 лет. Такой диапазон часто требуется в практических приложениях, где требуется представлять год рождения человека и обеспечить работоспособность выбранного представления минимум на 30 лет. Поэтому выберем начальную дату 01 января 1900 года (как в способе компании Microsoft) - требуем пригодность способа минимум до 2050 года.

Для предложенного способа потребуется 16 бит: 5 бит на представление дня месяца, остается 11 бит, что соответствует максимальному хранимому значению месяцев 2048(=2¹¹), что соответствует чуть более 169 годам. Таким образом, пригодность способа при стартовой дате 1 января 1900 года - до 2069 года.

В известном способе компании Oracle, принятом за прототип, для кодирования даты потребуется 4 байта (32 бита) - по байту на день месяца, месяц года, год столетия и столетие, что в 2 раза больше, чем в предложенном способе.

Даже если модифицировать этот способ, но все компоненты даты хранить в своих наборах бит - 5 на день месяца, 4 - месяц года и оставшиеся биты для хранения года, для хранения года (не менее 150) потребуется не менее 8 бит:

2⁷⁼128<150<2⁸=256.

Итого в сумме получаем 17 бит, что на один бит хуже, чем в предлагаемом способе.

В известном способе компании Microsoft, в котором используется число дней, прошедших с фиксированной даты, потребуется представить не менее 150*365=54750 дней, на что потребуется не менее 16 бит:

2¹⁵=32768<54750<2¹⁶=65536.

Однако сложность и объем вычислений в способе компании Microsoft, как указано выше, значительно выше.

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

Осуществление изобретения

Реализация предложенного способа может быть осуществлена в вычислительной системе, способной производить операции целочисленного деления, т.е. практически в любой, включая системы, работающие, например, под управлением операционной системы MS Windows.

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

Например, на языке C++ при использовании boost типов реализация может выглядеть следующим образом.

#include<boost/cstdint.hpp>

const int StartYear=1900; // В качестве стартовой даты берем 1 января 1900 г.

// Внутреннее представление даты

typedef boost::uint16_t InternalDate;

// Внешнее представление даты - отдельно год, месяц и день.

typedef struct {int year; int month; int day;} ExternalDate;

// Получаем внутреннее представления по внешнему

InternalDate PackDate (const ExternalDate & date)

{return date.day+(date.year-StartYear)·384+(date.month -1)*32;

}

// Получаем внешнее представление по внутреннему

void UnpackDate (InternalDate n, ExternalDate & date)

{date.year=StartYear+n/384;

date.month=(n/32)% 12+1;

date.day=n% 32;

}

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

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

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

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

Источники информации

1. Дата и время (Transact-SQL), статья по адресу

http://msdn.microsoft.com/ru-ru/library/ms187819(v=sql.90)aspx.

2. Datetime (Transact-SQL), статья по адресу

http://msdn.microsoft.com/ru-ru/library/ms187819(у=sql.110). Aspx.

3. Julian day, статья по адресу

http://en.wikipedia.org/wiki/Julian_day.

4. Руководство разработчика приложений (Server Application Developer's Guide), 1992, перевод по адресу

http://www.interface.ru/fset.asp?Url=/oracle/ora7/ora7a03a.htm.