Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2009
Hauptverfasser:	Шинкаренко, В.И., Кроль, Г.Г., Васецкий, Е.Г., Мажара, Т.Н.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2009
Schlagworte:	Интеллектуальный анализ данных
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/8164
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе / В.И. Шинкаренко, Г.Г. Кроль, Е.Г. Васецкий, Т.Н. Мажара // Штучний інтелект. — 2009. — № 4. — С. 104-111. — Бібліогр.: 11 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-8164
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-81642025-02-09T13:38:44Z Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе Структурна адаптація алгоритмів стискання даних на метаалгоритмічній основі Шинкаренко, В.И. Кроль, Г.Г. Васецкий, Е.Г. Мажара, Т.Н. Интеллектуальный анализ данных Предложен модифицированный метод структурной адаптации алгоритмов на метаалгоритмической основе. Особенность метода заключается в том, что в процессе адаптации одновременно синтезируется два взаимообратные алгоритма. Методика апробирована на алгоритмах архивации и разархивации данных. Решена задача эффективной архивации распознанных линий скоростемерных лент локомотивов. Выполнена оценка функциональной эффективности структурно-адаптированного алгоритма сжатия данных. Запропоновано модифікований метод структурної адаптації алгоритмів на метаалгоритмічній основі. Особливість методу полягає у тому, що під час адаптації одночасно синтезується два взаємообернених алгоритми. Вирішена задача ефективної архівації розпізнаних ліній швидкостемірних стрічок локомотивів. Виконана оцінка функціональної ефективності структурно-адаптованих алгоритмів стиснення даних. 2009 Article Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе / В.И. Шинкаренко, Г.Г. Кроль, Е.Г. Васецкий, Т.Н. Мажара // Штучний інтелект. — 2009. — № 4. — С. 104-111. — Бібліогр.: 11 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8164 004.051:004.89:519.712.2 ru application/pdf Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Интеллектуальный анализ данных Интеллектуальный анализ данных
spellingShingle	Интеллектуальный анализ данных Интеллектуальный анализ данных Шинкаренко, В.И. Кроль, Г.Г. Васецкий, Е.Г. Мажара, Т.Н. Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе
description	Предложен модифицированный метод структурной адаптации алгоритмов на метаалгоритмической основе. Особенность метода заключается в том, что в процессе адаптации одновременно синтезируется два взаимообратные алгоритма. Методика апробирована на алгоритмах архивации и разархивации данных. Решена задача эффективной архивации распознанных линий скоростемерных лент локомотивов. Выполнена оценка функциональной эффективности структурно-адаптированного алгоритма сжатия данных.
format	Article
author	Шинкаренко, В.И. Кроль, Г.Г. Васецкий, Е.Г. Мажара, Т.Н.
author_facet	Шинкаренко, В.И. Кроль, Г.Г. Васецкий, Е.Г. Мажара, Т.Н.
author_sort	Шинкаренко, В.И.
title	Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе
title_short	Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе
title_full	Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе
title_fullStr	Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе
title_full_unstemmed	Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе
title_sort	структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2009
topic_facet	Интеллектуальный анализ данных
url	https://nasplib.isofts.kiev.ua/handle/123456789/8164
citation_txt	Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе / В.И. Шинкаренко, Г.Г. Кроль, Е.Г. Васецкий, Т.Н. Мажара // Штучний інтелект. — 2009. — № 4. — С. 104-111. — Бібліогр.: 11 назв. — рос.
work_keys_str_mv	AT šinkarenkovi strukturnaâadaptaciâalgoritmovsžatiâdannyhnametaalgoritmičeskojosnove AT krolʹgg strukturnaâadaptaciâalgoritmovsžatiâdannyhnametaalgoritmičeskojosnove AT vaseckijeg strukturnaâadaptaciâalgoritmovsžatiâdannyhnametaalgoritmičeskojosnove AT mažaratn strukturnaâadaptaciâalgoritmovsžatiâdannyhnametaalgoritmičeskojosnove AT šinkarenkovi strukturnaadaptacíâalgoritmívstiskannâdanihnametaalgoritmíčníjosnoví AT krolʹgg strukturnaadaptacíâalgoritmívstiskannâdanihnametaalgoritmíčníjosnoví AT vaseckijeg strukturnaadaptacíâalgoritmívstiskannâdanihnametaalgoritmíčníjosnoví AT mažaratn strukturnaadaptacíâalgoritmívstiskannâdanihnametaalgoritmíčníjosnoví
first_indexed	2025-11-26T09:34:57Z
last_indexed	2025-11-26T09:34:57Z
_version_	1849845046824665088
fulltext	«Искусственный интеллект» 4’2009 104 2Ш УДК 004.051:004.89:519.712.2 В.И. Шинкаренко, Г.Г. Кроль, Е.Г. Васецкий, Т.Н. Мажара Днепропетровский национальный университет железнодорожного транспорта имени академика В. Лазаряна, г. Днепропетровск, Украина ccp@diit-70.dp.ua Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе Предложен модифицированный метод структурной адаптации алгоритмов на метаалгоритмической основе. Особенность метода заключается в том, что в процессе адаптации одновременно синтезируется два взаимообратные алгоритма. Методика апробирована на алгоритмах архивации и разархивации данных. Решена задача эффективной архивации распознанных линий скоростемерных лент локомотивов. Выполнена оценка функциональной эффективности структурно-адаптированного алгоритма сжатия данных. Введение Несмотря на то, что адаптации алгоритмов уделяется достаточно большое внима- ние [1], [2], структурная адаптация из-за сложности реализации изучена достаточно слабо. Данную работу можно рассматривать как развитие работ [3], [4], в которых предложены достаточно универсальные методы и средства структурной адаптации алгоритмов. Несмотря на универсальность этих методов, специфика алгоритмов сжа- тия требует их уточнения и модернизации. Это еще раз подтверждает, что алгоритмы сжатия данных относятся к одному из классических классов алгоритмов, изучение и совершенствование которых обогащает методологию и средства поддержки алгорит- мизации. Предложенный метод основывается на понятии метаалгоритма и поддерживает- ся разработанными программными средствами [4]. Метаалгоритм – это специальным образом заданный алгоритм, на основе кото- рого могут быть построены конкретные алгоритмы, обобщенный алгоритм решения некоторой задачи. Метаалгоритм строится на основе модифицированного метода пошаговой дета- лизации: на первом шаге программа записывается с помощью абстрактных операто- ров (АО) или предикатов первого уровня и инструкций языка программирования; на втором шаге АО первого уровня записываются (реализуются) с помощью АО второго уровня и инструкций языка программирования и т.д., пока вся программа не будет за- писана с помощью инструкций языка программирования. Модификация метода заклю- чается в том, что абстрактные операторы могут иметь несколько реализаций. Адаптация алгоритмов осуществляется путем направленного синтеза конкретных алгоритмов. Синтез конкретных алгоритмов заключается в его пошаговом формировании. На- чиная с корневого, АО заменяются их реализациями. Выбор конкретных реализаций из числа альтернативных осуществляется на основе рекомендаций подсистемы анализа. Для каждого синтезированного алгоритма хранится его структура, а измерительная Структурная адаптация алгоритмов сжатия данных... «Штучний інтелект» 4’2009 105 2Ш система в процессе выполнения алгоритма запоминает в базу знаний значения целе- вого показателя эффективности алгоритма такой структуры. В результате анализа накопленной информации формируются рекомендации син- тезатору алгоритмов: какие реализации АО предпочтительнее, что представляется в виде рекомендуемых вероятностей применения конкретных реализаций АО. Целью данной работы является разработка модификации метода структурной адаптации алгоритмов с учетом специфических особенностей алгоритмов сжатия. Особенности структурной адаптации алгоритмов сжатия Будем обозначать Y XA \| – алгоритм с областью определения X и областью зна- чения Y . Определим операцию композиции алгоритмов " " как их последовательное выполнение [5]. Результатом выполнения алгоритма 2 2 \|2 Y XA непосредственно после 1 1 \|1 Y XA есть алгоритм 2 2 1 1 \|\|\| 21 Y X Y X Y X AAA  (краткая форма записи   N i Y Xi i i A 1 \| ). Для алгоритмов сжа- тия обязательно наличие обратного алгоритма, такого, что: X X X Y Y X EAA \|\|\| 1   , (1) где X XE \| – единичный алгоритм, реализующий функцию .y x Алгоритмы сжатия могут состоять из последовательности преобразований, сочетая один или несколько предварительных проходов или повторно применяя алгоритм к уже сжатым данным: ....2,,,\|\| 11 1 NiYXXXAA ii N i Y Xi Y X i i     (2) Разархивация должна выполняться в обратном порядке: ....2,,,\|\| 1 1 1 1 1 1 1 NiXYYYAA iiN N i X YiN X Y iN iN          (3) Исходя из (2) и (3) предложена методика формирования двух взаимообратных метаалгоритмов. Любой абстрактный оператор (алгоритм) метаалгоритма сжатия дан- ных должен иметь обратный. При синтезе конкретных алгоритмов архивации одновременно должен синтези- роваться алгоритм разархивации как обратная последовательность обратных алгоритмов. Для многих алгоритмов, в частности для рассматриваемых ранее алгоритмов сортировки [3], степень эффективности АО практически не зависела от места и спо- соба его применения. Для алгоритмов сжатия данных это положение существенно другое. Эффективность алгоритма j i i i Y Yj Y Xi AA \|\|  может существенно отличаться от эф- фективности алгоритма i j j j Y Yi Y Xj AA \|\|  . Это предусматривает модификацию и методов, и средств анализа, а также измери- тельной системы. Функциональность измерительной системы расширена таким образом, что раз- мер сжатого файла измеряется и заносится в базу данных после каждого выполнения реализации АО, способной изменить текущий размер сжатого файла. Назовем такую реализацию сжимающей реализацией АО (СР АО). Шинкаренко В.И., Кроль Г.Г., Васецкий Е.Г., Мажара Т.Н. «Искусственный интеллект» 4’2009 106 2Ш База данных расширена следующим образом. Для каждой СР АО строится век- тор, в котором для каждой СР АО, следующей после данной СР АО, определяется значение текущей степени сжатия архивируемого файла. Система анализа, согласно методике [4], определяет рекомендуемую вероятность использования. Для каждой СР АО аналогичным образом определяется рекомендуе- мая вероятность его использования после других СР АО. Система синтеза первую СР АО выбирает на общих основаниях (как в [4]), а последующие – на основании рекомендуемой вероятности следования после преды- дущей СР АО. Метаалгоритм сжатия данных С использованием модифицированного метода пошаговой детализации [3] на ос- нове известных алгоритмов [6] разработан метаалгоритм сжатия данных. Порядок дета- лизации приведен на рис. 1. Рисунок 1 – Порядок формирования метаалгоритма сжатия данных Каждой детализации в представленном дереве соответствует абстрактный опе- ратор – iS или реализация абстрактного оператора y xiB . 0 уровень 1 уровень 2 уровень 3 уровень 4 уровень <<1,1,1>> <<1,1,2>> <<2,8,1>> <3,13,0> <3,14,0> <<2,7,1>> <<2,6,1>> <3,9,0> <3,10,0> <3,11,0> <3,12,0> <<3,9,1>> <<3,10,1>> <<3,11,1>> <<3,13,1>> <<3,14,1>> <<4,12,1>> <0,1,0> <<3,12,1>> <4,12,0> <1,3,0> <1,4,0> <<1,2,2>> <<1,2,1>> <<1,1,2>> <<0,1,1>> <1,1,0> <1,2,0> <1,3,0> <1,4,0> <<1,4,2>> <<1,4,1>> <2,5,0> <<1,3,5>> <<1,3,4>> <<1,3,3>> <<1,3,2>> <<1,3,1>> <2,6,0> <2,7,0> <2,8,0> <<2,5,1>> <<2,4,1>> <2,4,0> Структурная адаптация алгоритмов сжатия данных... «Штучний інтелект» 4’2009 107 2Ш На нулевом уровне имеем один АО Ms M S1 (<0,1,0>) – <сжатие>, где M – массив до сжатия, Ms – массив после сжатия, который имеет одну реализацию Ms M B1 (<<0,1,1>>). Реализация включает четыре АО (4) Mo M S2 (<1,1,0>) – <предварительная обработка>, Mo M S3 (<1,2,0>) – <универсальная обработка>, Ms M S4 (<1,3,0>) – <конкретный метод сжатия>, Ms M S5 (<1,4,0>) – <сжать данные>. Ms Ms Ms Mo Mo Mo Mo M Ms M Ms M SSSSBS 1 1 1 1 54321 * 1  , (4) где Ms M S * 1 (<<0,1,>>) – выбранная синтезатором реализация Ms M S1 , iMs и iMo – обра- ботанные массивы соответствующими алгоритмами. АО Mo M S2 имеет две реализации (5): Mo M B2 (<<1,1,1>>) – предварительная обработка arcDelta2 [6] и M M B3 (<<1,1,2>>), а Mo M S3 имеет три альтернативных реализации (6), Mo M B4 (<<1,2,1>>) – предваритель- ная обработка arcBase64 [7], Mo M B5 (<<1,2,2>>) – предварительная обработка RLE [8, c. 289] и M M B3 (<<1,2,3>>). Реализация M M M M EB 3 .        .)1( ,1~ если , ,~0 если , 3223 22 2 pppp B ppB S M M Mo MMo M (5)            )1( 1~ если , ,~ если , ,~0 если , 543435 434 33 * 3 .ppp, pppB pppB ppB S Mo M Mo M Mo M Mo M (6) где p~ – случайное число, ip – рекомендуемая вероятность выбора i -й альтернативы. АО Ms M S4 имеет пять реализаций (7): Ms M B6 (<<1,3,1>>), Ms M B7 (<<1,3,2>>), Ms M B8 (<<1,3,3>>), Ms M B9 (<<1,3,4>>), Ms M B10 (<<1,2,5>>) (9), которые выполняют сжатие вход- ного массива следующими методами сжатия данных соответственно: сжатие методом arcDeflate [8, c. 94], сжатие методом arcBZip, сжатие методом arcLZMA, [8, c. 90], сжатие методом GZip, сжатие методом «Арифметическое кодирование» [8, с. 35] (7). АО Ms M S5 имеет две реализации (8): Ms M B11 (<<1,4,1>>) – сжать любым методом, и Ms M B12 (<<1,4,2>>) – сохранение данных.                   ).1(1~ если , ~ если , ... ,~0 если , 10 6 9 6 10,,,9 ,, 8 9 6 8 6 9 66 * 4 i i i i Ms Mc Mc sMfMdM sMfMd M i i i i Ms M Ms M Ms M p,ppSSS ,pppB pp B S (7) Шинкаренко В.И., Кроль Г.Г., Васецкий Е.Г., Мажара Т.Н. «Искусственный интеллект» 4’2009 108 2Ш        ).1(1~ если , ,~0 если , 12111112 1111* 5 pp,ppB ppB S Ms M Ms MMs M (8) В свою очередь реализация «сохранение данных» состоит из абстрактного опе- ратора АО fn fnMS ,6 (<2,4,0>) – сохранение данных, который реализован fn fnMB ,13 (<<2, 4,1>>), где M – это массив для сохранения в файл с именем fn . АО I MsS \|7 (<2,5,0>) – запись в базу данных информации для анализа ( I ): Ms M Ms M I Ms SSSS 574 * 7 \|  . (9) АО sMfMd M S ,, 8 (<2,6,0>) имеет реализацию sMfMd M B ,, 15 (<<2,6,1>>), которая на ос- нове входного массива M формирует массив символов A , которые встречаются во входном массиве, и массив накапливаемых частот символов B размером s . MfMd MfMd MfMdMb M Md M MfMd MfMd sMfMd M SSSSS , ,14 ,, 1312 , ,11 ,,* 8  . (10) Реализация АО <кодирование> C sBAM S ,,,9 (<2,7,0>) – Mc sMfMdM B ,,,16 (<<2,7,1>>) Md – массив символов, которые встречаются в данных для кодирования, Mf – массив накапливаемых частот символов, s – количество разных символов в массиве для коди- рования, и на выходе дает массив кодов Mc . АО Mb Mc S10 (<2,8,0>), Mb Mc S15 (<2,13,0>) реа- лизуют алгоритмы Mb Mc B17 (<<2,8,1>>) и Mb Mc B22 (<<2,13,1>>) соответственно, которые из символьного массива кодов Mc формируют массив байтов Mb . .\| 1615,,,16 * 10 Ms Ma Ma Mc Mc sMfMdM Ms Mc SSBS  (11) АО MbMa MbMaS , ,11 (<3,9,0>) имеет реализацию MbMa MbMaB , ,18 (<<3,9,1>>), которая обнуляет все элементы входных массивов Ma и Mb ; АО Ma M S12 (<3,10,0>) и его реализация Ma M B19 (<<3,10,1>>) подсчитывает частоту символов во входном массиве M и записывает ее в массив Ma . АО MfMdMb Ma S ,, 13 (<3,11,0>) имеет реализацию MfMdMb MaB ,, 20 (<<3,11,1>>), которая выполняет подсчет накапливаемых частот символов входного массива и сохраняет их в массив Mb ; Ma – массив частот всех символов, Md – массив симво- лов, встреченных во входном массиве, Mf – массив накапливаемых частот символов из входного массива. АО MbMa MbMaS , ,14 (<3,12,0>) – <сортировка двух массивов>, MbMa MbMaS , ,17 (<4,12,0>) – <метод сортировки> имеют реализации MbMa MbMaB , ,21 (<<3,12,1>>) – сорти- ровка массива, MbMa MbMaB , ,24 (<<4,12,1>>) – «быстрая» сортировка массивов соответст- венно. Указанные реализации на вход принимают два массива Ma и Mb и сортируют их. В АО Mb Ma S16 (<3,14,0>) – <копирование элементов массива>, и алгоритме Mb Ma B23 (<<3,14,1>>), который его реализует, элементы входного массива Ma копируются в новый массив Mb . Структурная адаптация алгоритмов сжатия данных... «Штучний інтелект» 4’2009 109 2Ш Апробация метода структурной адаптации алгоритмов Апробация метода структурной адаптации алгоритмов выполнена при решении практической задачи организации хранения значительных объемов информации со скоростемерных лент локомотивов. При движении поезда на скоростемерную ленту записывается информация об уп- равлении локомотивом: время, скорость движения, состояние семафоров и др. Разработанный программно-аппаратный комплекс расшифровки скоростемерных лент [9] выполняет сканирование ленты, предварительную обработку изображения, распознавание и идентификацию кривых, а также выявляет нарушения управления поездом. Выделенные кривые (рис. 2) носят достаточно специфический характер. Для от- дельных кривых характерны определенная регулярность, или скачкообразный характер, или значительные случайные возмущения. Рисунок 2 – Фрагмент записей на скоростемерной ленте Необходимо было разработать форматы данных, позволяющие за приемлемое время отображать и масштабировать кривые с возможностью совместного отображения со сканированным изображением. Также требовалось найти эффективные методы сжа- тия для хранения в базах данных информации для дальнейшего анализа. Специфический характер кривых позволяет предположить, что специализирован- ные или адаптированные алгоритмы будут более эффективными, чем универсальные. Оценка функциональной эффективности адаптированного алгоритма Выполнена оценка функциональной эффективности [10] адаптированного алго- ритма к модельным данным распознанных линий скоростемерных лент. Функциональная эффективность определялась средствами исследовательского комплекса программ ResComp [10]. Адаптированный алгоритм с доступными архиваторами. Они перечислены ни- же с указанием разработчиков, версии, года выпуска и параметров командной строки для запуска архиваторов:  Rar 3.71, Alexander Roshal, 2007, “a -m5 bbb all”  Ha 0999с, Harry Hirvola, 1995, “a2 bbb all\.”;  Arj 3.14a, ARJ Software, 2006, “a -jm '+ ' bbb all”; Шинкаренко В.И., Кроль Г.Г., Васецкий Е.Г., Мажара Т.Н. «Искусственный интеллект» 4’2009 110 2Ш  7_zip 4.58 beta, Igor Pavlov, 2008, “a -t7z bbb all -mx9”;  Bzip2 1.0.4, Julian Seward, 2006, “--best -k all\.”;  AlZip 7.0 beta1, ESTSoft corp, 2007, ”-a -m0 all bbb.alz”;  Rk 1.04.1 alpha, Malcolm Taylor, 2000, “-c bbb.rk @ccc2.txt”;  Tar 1.12, “-c -k -z --files-from=ccc1.txt --file=bbb.tar”;  Imp 1.12, Technelysium Pty ltd., 2000, “a -m3 bbb.imp all\.”;  Jar 1.02, ARJ Software, 1997, “a -m4 bbb.jar all\.”;  PKZIPC(R)_4.00, PKWARE inc., 2000, “-add bbb.zip all\.”. Здесь “bbb” – имя архива, “ccc” – имя файла со списком файлов, подлежащих архи- вации, “all” – имя папки с исходными файлами. Параметры архиваторов фиксированы и выбраны согласно рекомендациям раз- работчиков такими, что предполагают наилучшую степень сжатия. Функциональная эффективность алгоритмов определялась при сжатии файлов из банка данных из 840 файлов с минимальным и максимальным размером 40/1000 Кбайт и общим объемом 367,2 Мб. Определялась Xji AAS \|),( – степень превосходства одного (i-го) алгоритма над дру- гим (j-м) на ограниченном множестве X [11]: %100 ))\|(),\|(max( )\|()\|(1\|),(      Xx xixj xixj Xx Xji i ii ii i AA AA N AAS   . (10) Вычисленные значения показателей и доверительные интервалы (уровень доверия 0,05) приведены в табл. 1. В табл. 1 111 AA – алгоритмы архиваторов, перечисленных выше, 12A – адаптированный алгоритм. Отметим, что из существующих архиваторов наиболее эффективно выполняют сжатие специфичных данных записи скоростемерных лент Rar 3.71 и 7_zip 4.58 beta, причем первый из них незначительно лучше. Структурно-адаптированный алгоритм показал существенно более высокую эф- фективность по сравнению с универсальными архиваторами. Таблица 1 – Степень превосходства i-го алгоритма над j-м i j 1A 2A 3A 4A 5A 6A 7A 8A 9A 10A 11A 12A 1A 0.0 45,1 45,14,50   48,1 48,11,49   42,5 42,59,4   69,1 69,15,47   55,1 55,13,47   51,1 51,16,50   52,1 52,19,47   55,1 55,19,46   53,1 53,16,45   52,1 52,18,47   97, 97,0 08,71   2A 45,1 45,14,50   0.0 13,6 13,66,1   99,1 99,10,49-   53,0 53,00,11   09,0 09,06,5   26,0 26,04,0   17,7 17,70,5-   33,7 33,572,8   17,0 17,07,11-   17,8 17,85,5   41,0 41,04,85-   3A 48,1 48,11,49   13,6 13,66,1   0.0 98,1 98,18,47-   57,0 57,05,9-   81,5 81,51,4   3, 3,0 00,2   77, 77,1 14,3   1,2 1,26,6   12,0 12,01,10-   75, 75, 2 29,3   42,0 42,00,85-   4A 42,5 42,59,4   99,1 99,10,49   98,1 98,18,47   0.0 55,2 55,26,45   06,2 06,20,46   95, 95,1 13,49   06,2 06,25,46   17,2 17,24,45   23, 23,2 20,44   07,2 07,24,46   07,1 07,11,73-   5A 69,1 69,15,47   53,0 53,00,11   57,0 57,05,9   55,2 55,26,45-   0.0 57,0 57,00,6   36, 36,0 04,11   58,0 58,07,6   6,0 6,08,3   71,0 71,02,0   59,0 59,02,6   37,0 37,084,7-   6A 55,1 55,13,47   09,0 09,06,5   81,5 81,51,4   06,2 06,20,46-   57,0 57,00,6   0.0 26,0 26,06,0-   38,4 38,47,0   74,3 74,32,7-   09,0 09,06,4-   72,3 72,30,1-   41,0 41,084,5-   7A 51,1 51,16,50   26,0 26,04,0   3, 3,0 00,2   95, 95,1 13,49   36, 36,0 04,11   26,0 26,06,0  0.0 27,0 27,05,4-   26,0 26,08,5-   29,0 29,012,1-   27,0 27,05,9-   4,0 4,085,4-   8A 52,1 52,19,47   17,7 17,70,5   77, 77,1 14,3   06,2 06,25,46-   58,0 58,07,6   38,4 38,47,0   27,0 27,05,4  0.0 9,4 9,43,3   11,0 11,00,7   11,1 11,15,0   41,0 41,084,6-   9A 55,1 55,19,46   33,7 33,572,8   1,2 1,26,6   17,2 17,24,45-   6,0 6,08,3   74,3 74,32,7  26,0 26,08,5  9,4 9,43,3   0.0 11,0 11,00,4   4,5 4,58,2   41,0 41,084,4-   10A 53,1 53,16,45   17,0 17,07,11   12,0 12,01,10   23, 23,2 20,44   71,0 71,02,0   09,0 09,06,4  29,0 29,012,1  11,0 11,00,7   11,0 11,00,4   0.0 1,0 1,06,6   41,0 41,084,0-   11A 52,1 52,18,47   17,8 17,85,5   75, 75, 2 29,3   07,2 07,24,46-   59,0 59,02,6   72,3 72,30,1  27,0 27,05,9  11,1 11,15,0   4,5 4,58,2   1,0 1,06,6   0.0 41,0 41,084,6-   12A 97, 97,0 08,71   41,0 41,04,85   42,0 42,00,85   07,1 07,11,73   37,0 37,084,7   41,0 41,084,5  4,0 4,085,4  41,0 41,084,6  41,0 41,084,4  41,0 41,084,0  41,0 41,084,6  0.0 Структурная адаптация алгоритмов сжатия данных... «Штучний інтелект» 4’2009 111 2Ш Выводы В работе представлен модифицированный метод структурной адаптации алго- ритмов на метаалгоритмической основе. Его основная особенность заключается в одновременной адаптации прямого и обратного алгоритма. Это свойственно алгорит- мам сжатия данных (архивация/разархивация), кодирования и некоторым другим. Вторая особенность заключается в том, что при адаптации учитывается не только эффективность синтезированных алгоритмов, но и промежуточных преобра- зований. Таким образом расширяется база знаний о синтезированных алгоритмах, что обеспечивает большие возможности анализа алгоритмов и в конечном итоге ускоряет процесс адаптации и улучшает результаты. Выполненная апробация при решении задачи организации хранения значитель- ных объемов информации со скоростемерных лент локомотивов показала хорошую результативность метода и соответствующих программных средств. Согласно методике [7] выполнена оценка функциональной эффективности адап- тированного алгоритма к модельным данным распознанных линий скоростемерных лент. Отмечается высокая степень превосходства адаптированного алгоритма по от- ношению к известным архиваторам. Это объясняется повышенной эффективностью специализированного алгоритма, полученного в результате адаптации над универсаль- ными. Исследования могут быть продолжены для алгоритмов сжатия данных с потерями. Литература 1. Растригин Л.А. Адаптация сложных систем / Растригин Л.А. – Рига : Зинатне, 1981. – 375 с. 2. Цейтлин Г.Е. Введение в алгоритмику / Цейтлин Г.Е. – К. : Сфера, 1998. – 310 с. 3. Шинкаренко В.И. Структурная адаптация алгоритмов на основе полиморфизма / В.И. Шинкаренко // Математические машины и системы. – 2009. – № 2. – С. 28-44. 4. Шинкаренко В.И. Методы и средства структурной адаптации алгоритмов на метаалгоритмичес- кой основе / В.И. Шинкаренко, Г.Г. Кроль, И.В. Литвин, Е.Г. Васецкий // Искусственный интел- лект. – 2009. – № 3. – С.105-113. 5. Шинкаренко В.И. Структурные модели алгоритмов в задачах прикладного программирования. Часть I. Формальные алгоритмические структуры / В.И. Шинкаренко, В.М. Ильман, В.В. Скалозуб // Кибернетика и системный анализ. – 2009. – № 3. – С. 3-14. 6. Mogul J., Krishnamurthy B., Douglis F., Feldmann A., Goland Y., Hoff A. van, Hellerstein D. RFC 3229 – 2002 – 49 c. – [Электронный ресурс]. – Режим доступа : http://tools.ietf.org/html/rfc3229. 7. Josefsson S., RFC 3548 The Base16, Base32, and Base64 Data Encodings [Электронный ресурс] / S. Josefsson – 2003. – 13 c. – Режим доступа : http://tools.ietf.org/html/rfc3548. 8. Ватолин Д. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео / Д. Ва- толин, А. Ратушняк, М. Смирнов, В. Юкин. – М. : Диалог-МИФИ, 2003. – 384с. 9. Шинкаренко В.І. Програмно-апаратний комплекс розшифровки швидкостемірних стрічок / В.І. Шинкаренко, Є.Г. Васецький, Т.М. Мажара, О.М. Швець // Современные информационные техно- логии на транспорте, в промышленности и образовании : тезисы Международной научно-практической конференции. – Днепропетровск : ДНУЖТ, 2008. – С. 80-81. 10. Шинкаренко В.И. Знание-ориентированный подход к адаптации алгоритмов / В.И. Шинкаренко // Искусственный интеллект. – 2008. – № 3. – С. 388-397. 11. Шинкаренко В.И. Функциональная эффективность нечетко специфицированных алгоритмов / В.И. Шинкаренко // Проблемы программирования. – 2006. – № 1. – С. 24-33. В.І. Шинкаренко, Г.Г. Кроль, Є.Г. Васецький, Т.М. Мажара Структурна адаптація алгоритмів стискання даних на метаалгоритмічній основі Запропоновано модифікований метод структурної адаптації алгоритмів на метаалгоритмічній основі. Особливість методу полягає у тому, що під час адаптації одночасно синтезується два взаємообернених алгоритми. Вирішена задача ефективної архівації розпізнаних ліній швидкостемірних стрічок локомотивів. Виконана оцінка функціональної ефективності структурно-адаптованих алгоритмів стиснення даних. Статья поступила в редакцию 22.06.2009.

Структурная адаптация алгоритмов сжатия данных на метаалгоритмической основе

Institution

Ähnliche Einträge