Алгоритмы, структуры данных
Алгоритмы триангуляции
Романюк Александр, Сторчак Александр,Системы синтеза реалистических изображений должны обеспечивать передачу всех свойств моделируемого объекта: объемность, расположение, передачу полутонов, тени, освещение, текстуры поверхности. Чем выше степень реалистичности изображения, тем больше требуется вычислений для его формирования.
Генерация объемных изображений представляет сложную вычислительную задачу, в связи этим на практике выполняют ее декомпозицию. Сложные изображения формируют из фрагментов объектов, для чего их разбивают на составные части. Процесс разбиения поверхности объектов на полигоны получил название тесселяции. Эта стадия на данном этапе развития машинной графики проводится полностью программно вне зависимости от технического уровня 3D-аппаратуры.
В настоящее время появилось большое разнообразие графических акселераторов, которые имеют различные аппаратные графические функции для закраски трехмерных объектов, удаления невидимых частей, наложения текстур и т.п. Для использования преимуществ 3D-ускорителей необходимо сначала программно произвести тесселяцию исходных объектов, а затем передать полученные полигональные области для дальнейшей обработки акселератору.
На практике наиболее часто производится разбиение изображений на треугольники.
Это объясняется следующими причинами:
треугольник является простейшим полигоном, вершины которого однозначно задают грань;
любую область можно гарантировано разбить на треугольники;
вычислительная сложность алгоритмов разбиения на треугольники существенно меньше, чем при использовании других полигонов;
реализация процедур рендеринга наиболее проста для области, ограниченной треугольником;
для треугольника легко определить три его ближайших соседа, имеющих с ним общие грани.
Процесс разбиения полигональной области со сложной конфигурацией в набор треугольников называется триангуляцией. При анализе или синтезе сложных поверхностей их аппроксимируют сеткой треугольников, и впоследствии оперируют с простейшими полигональными областями, т.е.
с каждым из треугольников.
Особый интерес к алгоритмам триангуляции определяется тем, что они используются во многих процедурах машинной графики, таких как формирование поверхностей, закраска, удаление невидимых частей, отсечение.
Приведем пример создания полусферы, проиллюстрировав этапы рендеринга. Полигональная область представляется совокупностью треугольников. При этом важно достаточно точно аппроксимировать внешний контур.
Любая поверхность может быть аппроксимирована с необходимой точностью сеткой треугольников. Точность аппроксимации определяется количеством треугольников и способом их выбора. Для качественной визуализации объекта, находящегося вблизи точки наблюдения, требуется учесть во много раз больше треугольников, чем в ситуации, когда тот же объект расположен на удалении. Даже достаточно грубая сетка полезна на практике, так как методы сглаживания, применяемые в процессе отображения, могут значительно улучшить представление о кривизне поверхности.
Следующий этап – закрашивание граней, ограниченных треугольниками.
Последним этапом является применение алгоритмов сглаживания, которые устраняется ребристость поверхности, эффект Маха.
Поверхности, заданные набором точек
В машинной графике задачу триангуляции можно рассматривать в двух направлениях – это триангуляция полигональных областей и триангуляции набора точек. Последняя имеет место при описании поверхности набором точек и интенсивностями их цветов. Поточечное описание поверхностей применяют в тех случаях, когда поверхность очень сложна и не обладает гладкостью, а детальное представление многочисленных геометрических особенностей важно для практики. К поверхностям такого рода можно отнести участки грунта, формы малых небесных тел, микрообъекты, снятые с помощью электронного микроскопа и другие образования со сложной формой.Среди методов триангуляции для конечного набора точек, которые задают поверхность, широко используют метод Делоне. Метод предполагает соединение между собой набора точек непересекающимися отрезками прямых линий таким образом, чтобы сформированные треугольники стремились к равноугольности. Триангулированное изображение не может быть отнесено к триангуляции Делоне.
Триангуляция набора точек будет триангуляцией Делоне, если описанная окружность для каждого треугольника будет свободна от точек, то есть внутри ее не будет больше ни одной точки из набора. Две окружности, которые не содержат внутри себя других точек (можно провести окружности и для других треугольников, чтобы убедиться, что они также свободны от точек набора). Внутри области, ограниченной окружностью, попала одна точка другого треугольника. Следовательно, эта триангуляция не относится к типу Делоне.
Алгоритм работает путем постоянного наращивания к текущей триангуляции по одному треугольнику за шаг. Вначале триангуляция состоит из одного ребра, по окончании работы триангуляция является триангуляцией Делоне. На каждой итерации алгоритм ищет новый треугольник, который подключается к границе текущей триангуляции. Поиск и подключение треугольника образно можно представить, как надувание двумерного пузыря, привязанного к одному из ребер границы. Если такой пузырь достигает некоторой, еще не включенной в триангуляцию точки из набора, то образуется треугольник. В случае, когда точка не встречена, обрабатывается следующее ребро границы.
Сколько треугольников нужно?
При моделировании объекта возникает задача, какое количество треугольников нужно использовать? С одной стороны нужно достичь максимального качества при окончательной визуализации, а с другой снизить нагрузку на процессор и 3D-акселератор. Для снижения нагрузки можно использовать менее детализированную триангуляционную сеть, но при этом качество будет далеко не самым лучшим.При формировании динамических изображений точность представления объектов в кадре из-за его перемещения не воспринимается человеком, в связи с чем нецелесообразно использовать детальную триангуляцию.
При выборе подходов и алгоритмов триангуляции следует руководствоваться целью, которая ставится конкретной задачей. Например, при моделировании объекта, находящегося вдалеке, совершенно нет смысла применять очень детальную сеть для его описания и, наоборот, для близких объектов это очень важно, например, для построения модели головы человека требуется около 60 тыс. треугольников.
Триангуляция полигонов
Рассмотрим наиболее распространенные алгоритмы триангуляции полигонов. Простейшее решение задачи триангуляции состоит в расщеплении полигона вдоль некоторой хорды на два полигона и в дальнейшем рекурсивном разбиении их до ситуации, когда подлежащий триангуляции полигон является треугольником.Данный способ применим лишь для триангуляции выпуклых полигонов. Выпуклым считается полигон, если отрезок прямой, соединяющий любые его две точки, полностью лежит во внутренней области.
Триангуляция невыпуклых полигонов не так проста, поэтому предварительная разбивка невыпуклых многоугольников на выпуклые существенно упрощает алгоритмы их последующей обработки. Проще всего это можно сделать последовательным переносом и поворотом многоугольника так, чтобы одна из его вершин совпадала с началом координат, а исходящая из нее сторона — с осью ОХ. При расположении каких-либо сторон ниже оси, происходит их отсечение, и алгоритм рекурсивно повторяют для полученных полигонов, пока они не станут выпуклыми.
Приведем универсальный алгоритм. Триангуляцию любого полигона можно осуществить по следующему универсальному алгоритму.
Выбирается крайняя левая вершина и между двумя ее смежными сторонами проводится диагональ. При этом могут иметь место следующие два случая:
диагональ является хордой;
диагональ — не хорда, так как внутрь треугольникапопадает вершина полигона (в общем случае их может быть несколько).
Из всех вершин внутри треугольника вершина d наиболее удалена от стороны ас. Эту вершину будем называть вторгающейся. В случае, когда вторгающейся вершины нет, то полученный треугольник заносят в сетку треугольников, и алгоритм рекурсивно обрабатывает оставшийся полигон до тех пор, пока он не выродится в треугольник. При обнаружении вторгающейся вершины проводится диагональ из текущей до вторгающейся вершины. Полученные полигоны рекурсивно обрабатываются до получения треугольников.
Один из подходов к триангуляции состоит в нахождении внутренней точки области, ограниченной полигоном, и соединении с ней всех вершин.
Учитывая, что триангуляция является подготовительным этапом рендеринга, к выбору внутренней точки могут предъявляться определенные требования. Так, например, при многопроцессорной обработке целесообразно внутреннюю точку выбрать таким образом, чтобы площадь составляющих треугольников была примерно одинаковой. В этом случае будет обеспечена одинаковая степень вычислительной загрузки аппаратуры.
При триангуляции в качестве исходных данных наиболее часто задаются вершины полигона. Задача состоит в том, чтобы представить этот полигон совокупностью составных непересекающихся треугольников. В одном из самых распространенных программных интерфейсов (API) для разработки приложений в области двумерной и трехмерной графики стандарте OpenGL для формирования триангуляционной сетки используются следующие команды:
GL_TRIANGLES. Треугольники. Команда рисует серию треугольников, используя тройки вершин v0, v1 и v2, затем v3, v4 и v5 и т.д. Если количество вершин не кратно 3, оставшиеся точки игнорируются. Команду удобно использовать при описании поверхности, которая в результате тесселяции представляется кроме треугольников и другими геометрическими фигурами, например, прямоугольниками. В этом случае треугольники могут быть не соприкасаться между собой. Команда может использоваться для описания всех треугольников полигона, независимо от того, связаны они или нет между собой, однако из-за дублирования информации о координатах общих вершин память используется нерационально.
GL_TRIANGLE_STRIP. Полоса треугольников. Команда рисует серию треугольников, используя вершины в следующем порядке: v0, v1, v2, затем v2, v0, v3, затем v2, v3, v4, и т. д. При таком подходе каждая следующая вершина вместе с двумя предыдущими задает треугольник. Порядок вершин должен гарантировать, что треугольники имеют правильную ориентацию. Полоса может использоваться для формирования части поверхности.
GL_TRIANGLE_FAN. Команда похожа на GL_TRIANGLE_STRIP, но при формировании треугольников используют вершины в таком порядке: v0, v1, v2, затем v0, v2, v3, затем v0, v3, v4, и т.д. Все треугольники имеют общую вершину v0. Команда позволяет разбить n-угольник на n-2 треугольника. Для этого нужно выбрать одну из n вершин полигона и соединить ее с каждой из n-3 несоседних вершин
Использование инструментов среды ParJava.
Рассмотрим некоторые инструментальные средства среды ParJava, применявшиеся при разработке программ компьютерной алгебры. Средства использовались для анализа динамических характеристик программы и для выявления фрагментов кода, оптимизация которых дает максимальный эффект.Разрабатывая прикладную параллельную программу в рамках среды ParJava, прикладной программист взаимодействует с графическим интерфейсом среды. Он вводит исходный код программы в окне редактора и помещает введенные файлы в проект, в рамках которого хранятся исходный код параллельной программы, ее байт-код, ее внутреннее представление (статические модели классов), ее модель, ее трассы и профили.
Инструментальные средства среды становятся доступными после того, как пользователь выполнит трансляцию исходного кода во внутреннее представление (строятся статические модели классов): с помощью мыши отмечает транслируемые файлы в диалоговом окне управления проектом и вызывает транслятор. В результате трансляции во внутреннее представление для каждого указанного файла исходного кода (содержащего один или несколько классов) строится абстрактное синтаксическое дерево, которое затем передается преобразователю, строящему набор статических моделей классов – объектов класса FileInfo. Трансляция каждого класса выполняется независимо. Это позволяет в случае изменения исходного кода отдельного класса Java-программы повторно транслировать только файл, содержащий данный класс. После трансляции исходного кода в окне управления проектом начинает отображаться информация о структуре класса: каждый файл исходного кода отображается как корень дерева, потомок которого – класс, описанный в данном файле, для каждого класса в виде потомков выводятся методы и поля данного класса.
Выявление критических фрагментов кода выполняется при доводке параллельной программы, когда прикладной программист ищет код, работа которого сильнее всего влияет на характеристики всей программы. Влияние возникает за счет того, что код выполняется достаточно много раз (тела циклов) или занимает большую часть времени работы программы (например, из-за использования библиотек).
Ручная оптимизация такого кода позволяет ощутимо улучшить всю программу в целом. Поскольку относительно всей программы объем критического кода достаточно мал (как правило, он составляет 10-20%), оптимизировать только его проще и эффективней по времени, чем всю программу. Для выявления критического кода необходим профиль параллельной программы. Для облегчения работы пользователя с профилем, среда ParJava предоставляет возможность визуализации – числовые значения профиля отображаются на набор цветов (оттенки серого: от белого до черного), а исходный код программы подсвечивается определенным цветом, согласно полученному для него числовому значению характеристики. Если программа достаточно большая, такая методика уже не дает требуемой простоты и комфортности в работе. По этому в большинстве систем [6, 7], применяемых для доводки параллельных программ, используется иерархическая навигация по профилю. В среде ParJava также были разработаны и реализованы средства, позволяющие изучать профиль поэтапно, переходя от крупных фрагментов программы к более мелким. Рассмотрим порядок поиска критических фрагментов на примере анализа частотного профиля.
Сбор и анализ частотного профиля программы заключается в последовательном использовании инструментов среды: применение инструментатора к файлам исходного кода, отладочном выполнении программы, работа со средствами визуализации. Вопросы, связанные с техникой сбора профилей параллельной программы освещены в работе [8]. Собранный частотный профиль визуализируется с помощью инструментов среды ParJava в основном окне, содержащем исходный код программы, и окне визуализатора профиля. Окно визуализатора разделено на четыре части, три из которых используются для отображения данных, а четвертое содержит элементы управления (см. рис 1).
Рис. 1. Окно визуализатора с загруженным профилем.
Верхнее левое поле, поле программы, отображает частный профиль методов параллельной программы. Значения показываются в виде трехмерной гистограммы, столбцы которой расположены в виде матрицы.
Краткое описание среды ParJava.
Среда ParJava обеспечивает возможность разработки Java-программ, параллельных по данным, расширяя среду Java стандартным интерфейсом MPI, реализующим симметричные коммуникации. От реализации MPI в среде Java требуется, чтобы она минимизировала латентность и другие накладные расходы на организацию коммуникаций. Этим требованиям удовлетворяет реализация функций MPI в среде Java в виде «привязки» к соответствующим функциям реализации MPI в среде С. Такой подход позволяет использовать высокоэффективные реализации MPI, учитывающие специфику аппаратуры используемого коммуникационного оборудования. Реализации MPI в среде Java удовлетворяет этим условиям.Среда ParJava предоставляет прикладному программисту набор инструментов, позволяющих во время разработки Java-программы на инструментальном компьютере исследовать динамические характеристики как программы в целом, так и ее частей, и использовать эту информацию для улучшения своей программы. В среде ParJava имеется три группы инструментов: анализаторы (меню Analyze), преобразователи (меню
Transform) и интерпретаторы (меню
Run). В текущей версии среды ParJava доступны следующие инструменты: (а) анализаторы:
Sequential – выделение последовательной части параллельной программы; AmdahlRatio – вычисление отношения Амдаля [1]; ForLoop – анализ возможности распараллеливания заданного цикла for с помощью Омега-теста или теста расстояний [2]; Slice – построение обратного динамического слайса для заданного набора переменных в заданной точке программы; (б) преобразователи:
Transform to IC – построение внутреннего представления параллельной программы; Compile – компиляция внутреннего представления отдельного файла параллельной программы в байт-код;
Build Project – сборка параллельной программы;
Instrumentate – инструментирование параллельной программы с компенсацией обращений к инструментальным функциям; (в) интерпретаторы: Exec – выполнение параллельной программы; Simulate – интерпретация модели параллельной программы.
Во время интерпретация модели параллельной программы активизируется диалоговое окно, в котором пользователь может задавать параметры интерпретации: описание узлов целевого кластера, описание его коммуникационной сети, количество вычислительных узлов кластера.
В результате интерпретации получается оценка времени работы программы, определяются границы области масштабируемости (по Амдалю [1], или по Густафсону [3]).
В настоящее время в среду ParJava интегрируется механизм создания контрольных точек параллельных программ [4]. Поскольку существующие реализации JVM не обеспечивают возможности сохранения своего состояния, была разработана и реализована методика сохранения локальных (стековых) переменных и содержимого кучи JVM. С рядом ограничений (одна нить в каждом процессе, отсутствие пользовательских native-методов), такая методика позволяет восстанавливать состояние JVM по данным, сохраненным на диске. Целостность восстановленного состояния обеспечивается за счет использования коммуникационно-управляемого протокола [5] создания контрольных точек. Реализован механизм, позволяющий оптимизировать расположение контрольных точек в программе за счет использования профиля используемой памяти: если короткоживущие переменные занимают достаточно много места, создание контрольной точки откладывается.
Матричные операции.
Самыми распространенными формами хранения матриц являются стандартная построчечная форма хранения всех коэффициентов матрицы (DM), которая применяется для хранения плотных матриц, а также построчечная форма хранения ненулевых коэффициентов матрицы и их индексов (SM), которая применяется для хранения разреженных матриц.Для организации эффективных рекурсивных параллельных матричных операций необходимо иметь соответствующий формат для хранения матриц.
Таким естественным форматом может служить формат кватернарного дерева (QT). Дерево строится следующим образом. Если порядок матрицы 2n, то она может быть разбита на четыре квадратных блока порядка 2n-1, которые также могут быть разбиты на четыре равных блока, и так – вплоть до элементов. Если блокам поставить в соответствие вершины, а ребрами соединить вершины, соответствующие блокам, с вершинами, соответствующими его подблокам, то в результате получим кватернарное дерево. Если некоторый блок нулевой, то соответствующее ему ребро в дереве отсутствует. Это обеспечивает эффективный способ хранения разреженных матриц (см. также [10 и [11]). Отметим, что при необходимости всякая матрица может быть дополнена до матрицы размера 2n, введением дополнительных нулевых или единичных элементов. Заметим, что обозначения QT, DM и SM происходят от названий: quaternary tree, density matrix и sparse matrix.
Если время вычисления суммы и произведения элементов матриц примерно одинаковые, то применение схемы умножения Штрассена не приводит к ускорению вычислений, если порядок матрицы менее 1287 (см. оценки в [12]). Поэтому в первую очередь были разработаны параллельные программы для стандартного алгоритма умножения матриц. При этом использовались две схемы – простая параллельная схема умножения и рекурсивная блочная схема умножения.
Параллельные алгоритмы компьютерной алгебры
Г.И. Малашонок, А.И. Аветисян, Ю.Д. Валеев, М.С. Зуев.Труды Института Системного Программирования РАН, 2004 г.
В работе рассматривается разрабатываемая в рамках среды ParJava система компьютерной алгебры. Цель разрабатываемой системы – предоставить возможность эффективного использования параллельных вычислительных систем для проведения аналитических расчетов. В силу разреженности данных система включила в себя несколько версий каждой решаемой задачи за счет различных методов распределения данных между процессами параллельной программы. Статья состоит из 5 разделов. В разделе 2 содержится краткое описание среды ParJava. Перечисляются входящие в нее инструментальные средства. В разделе 3 рассматривается применение инструментов среды для решения задач оптимизации программы, возникающих во время ее разработки. Подробно описывается применение нового метода анализа профилей параллельной программы, позволяющего работать с иерархическим представлением численных характеристик. В разделе 4 описываются разработанные программы компьютерной алгебры, приводятся результаты модельных расчетов, проводимых на кластере ИСП РАН. Раздел 5 подводит итоги проведенной работы.
Параллельные программы компьютерной алгебры.
Можно выделить три типа параллельных программ компьютерной алгебры: статический, динамический и комбинированный.Пусть вычислительный граф задачи разбит на узловые подграфы, т.е. подграфы, вычисление которых происходит на одном процессорном узле. Если закрепление узлового подграфы за конкретным узлом происходит до начала вычислений, то такую параллельную программу называем статической. Если закрепление узлового подграфа за конкретным узлом происходит непосредственно перед вычислением по этому подграфу, в зависимости от состояния загруженности узлов, то такую программу называем динамической. Программа комбинированного типа – это программа, в которой предусмотрено переключение статического режима в динамический.
Задачи компьютерной алгебры имеют дело, как правило, с существенно разреженными данными. Заранее неизвестно, как будут загружены отдельные узлы. Поэтому статические программы могут оказаться неэффективными. Если же данные однородные и загрузку узлов можно рассчитать заранее, то, очевидно, статические программы предпочтительнее любых других типов.
Простая параллельная схема умножения матриц.
Вычисление произведения двух матриц можно осуществить с помощью представления первого матричного сомножителя в виде вектора матричных блоков. В результате умножения каждого такого блока на второй сомножитель, получаем соответствующий блок матрицы, являющейся произведением. Здесь использован естественный параллелизм задачи умножения матриц.Был реализован статический вариант такой параллельной программы, в которой число блоков, на которые разбивается первый сомножитель, просто выбирается равным числу процессоров участвующих в вычислении, а размеры всех блоков равны между собой или отличаются не более, чем на одну строку. В каждом из процессоров вычисляется умножает одного блоков первой матрицы на вторую матрицу.
Эксперименты с этой программой показали, что при умножении матриц порядка 1024 в конечном поле коэффициент ускорения равен 77% при использовании 12 процессоров. На рис. 4 показана зависимость скорости вычислений этой параллельной программы от количества процессоров, участвующих в вычислении.

Рис. 4. Вычисление произведения матриц в конечном поле с помощью простой параллельной схемы умножения.
Коэффициент ускорения равен 77%.
Рекурсивная блочная схема умножения матриц.
Когда порядки квадратных матриц сомножителей равны 2n, то матрицы разбиваются на четыре одинаковых квадратных блока и вычисление произведения матриц сводится к вычислению 8 умножений таких блоков, с последующим парным суммированием. Для вычисления произведения блоков снова используется эта же схема. Так можно продолжать вплоть до элементов.Был реализован динамический вариант такой программы. Одно умножение матриц, которые разбиты на четыре блока, сводится к восьми блочным умножениям и может выполняться параллельно на 8 процессорах. Если при этом еще не все процессоры участвуют в вычислениях, то каждое такое блочное умножение может, в свою очередь, быть реализовано с помощью 8 умножений подблоков. Для управления свободными процессорами и организации блочных операции умножения на конкретных процессорах используется программа диспетчера.
Эксперименты для матриц 512 порядка с небольшими целыми коэффициентами (~228) показали, что при умножении в кольце целых чисел коэффициент ускорения равен 85%, а при умножении в конечном поле коэффициент ускорения равный 86.4%. Использовались 2 и 14 процессоров.
На рис. 5 и 6 показаны результаты двух экспериментов, проведенных для динамических параллельных программ умножения матриц. В этих программах использовался QT-формат хранения коэффициентов. В каждом эксперименте выполнялось умножение матриц 512 порядка. В первом случае коэффициенты матриц – это целые числа в пределах 228. Коэффициент ускорения при переходе с двух на 14 процессоров был равен 85%. Во втором случае коэффициенты матриц берутся из конечного поля, характеристика которого не превосходит 2·108. Коэффициент ускорения при переходе с двух на 14 процессоров составляет 85%.

Рис. 5. Вычисление произведения целочисленных матриц в QT формате с помощью рекурсивной схемы умножения.
Коэффициент ускорения равен 85%.

Рис. 6. Вычисление произведения матриц в конечном поле в QT формате с помощью рекурсивной схемы умножения.
Коэффициент ускорения равен 86%.
Рекурсивная блочная схема вычисления присоединенной и обратной матриц.
Для QT-формата был реализован рекурсивный алгоритм вычисления присоединенной и обратной матриц, а также решения систем линейных уравнений (см. [13] и [14]).Вычисления производились с плотной случайной целочисленной матрицей 128 порядка, с 28-битовыми целыми коэффициентами. Была составлена программа с помощью рекурсивного алгоритма [14] для QT-формата.
Этот алгоритм вычисления присоединенной матрицы в коммутативной области имеет такую же сложность, что и алгоритма матричного умножения, который в нем используется. Для построения параллельного алгоритма был применен последовательный алгоритм вычисления присоединенной матрицы, в котором все процедуры умножения выполнялись параллельно. Результаты экспериментов приведены на рис 7. Коэффициент ускорения при переходе с двух на 14 процессоров равен 60%.

Рис. 7. Вычисление присоединенной (обратной) матрицы в случае целых коэффициентов в QT формате с помощью рекурсивного алгоритма. Коэффициент ускорения равен 60%.
Умножение полиномов.
Были разработаны программы комбинированного типа для умножения полиномов многих переменных. Вычислительный граф параллельной программы имеет вид бинарного дерева: каждый из полиномов сомножителей представляется суммой двух полиномов, а произведение представляется суммой четырех произведений, в которых участвуют эти слагаемые. Ниже, на рис. 2 и 3, показаны результаты двух вычислительных экспериментов с параллельными программами умножения полиномов. На рисунках представлены графики роста скорости вычислений при увеличении числа процессоров, участвующих в вычислениях.
Рис. 2. Вычисление произведения полиномов в конечном поле. Коэффициент ускорения равен 76%.
На этих графиках и на всех графиках дальше по горизонтальной шкале откладывается количество процессоров, участвующих в вычислениях, а по вертикальной шкале – величина, обратная времени вычислений. За единицу времени принято 100 сек. Верхний луч соответствует 100% роста скорости (теоретический предел), нижний луч соответствует росту скорости, равному 50%. В первом эксперименте вычислялось произведение двух полиномов от трех переменных, содержащих по 17 тысяч мономов. Коэффициенты брались из конечного поля, характеристика которого не превосходила 2·108. Коэффициент ускорения при переходе от двух к шестнадцати процессорам составил 76%.

Рис. 3. Вычисление произведения полиномов с целыми коэффициентами. Коэффициент ускорения равен 85%.
Во втором эксперименте вычислялось произведение таких же по размеру полиномов, коэффициентами которых были случайные целые числа, не превосходящие по модулю числа 228. Коэффициент ускорения при переходе от двух к шестнадцати процессорам составил 85%.
Продолжение
Используемые сегодня системы компьютерной алгебры,
Используемые сегодня системы компьютерной алгебры, такие как MAPLE, Mathematica, CoCoA, Reduce, Derive и другие, находят применение при решении задач во многих разделах физики, химии, биологии, в задачах моделирования в электротехнике, робототехнике и других областях.Эти системы предназначены для работы на персональных рабочих станциях и поэтому ограничены задачами небольшой вычислительной сложности. Они опираются на парадигмы программирования 80х-90х годов, когда закладывались основы для этих систем и ориентированы на последовательную организацию вычислений – их базовые структуры данных являются последовательными структурами.
Аналитические расчеты носят характер задач высокой вычислительной сложности, у которых происходит быстрый рост сложности вычислений при росте объемов входных данных. По этой причине для проведения аналитических вычислений требуется разработка параллельных алгоритмов и проведение расчетов на многопроцессорных вычислительных комплексах, требуется создание системы параллельной компьютерной алгебры. Создание такой параллельной системы представляется перспективным в связи с развитием вычислительных сетей и технологий GRID.
Цель этой статьи – обсудить результаты экспериментов с параллельными алгоритмами компьютерной алгебры, реализованными в среде ParJava и проведенными на вычислительном кластере ИСП РАН.
Каждая параллельная программа выполнялась на высокопроизводительном кластере ИСП РАН, состоящем из восьми узлов, связанных сетями Myrinet и Fast Ethernet. Вычислительный узел кластера работает под управлением операционной системы Linux с ядром версии 2.4.20-8, содержит два процессора Athlon с тактовой частотой 1533 MHz и один гигабайт оперативной памяти. Для передачи данных во время работы параллельной программы используется сеть Myrinet, обеспечивающая полнодуплексный канал с пропускной способностью 2 Gbit/sec; топология сети Myrinet представляет собой сеть Клоза (Clos network). Сеть Fast Ethernet используется только для управления работой кластера: монтирование файловых систем, запуск процессов параллельных программ, сбор данных системного мониторинга вычислительных узлов.
Используемые сегодня системы компьютерной алгебры, такие как MAPLE, Mathematica, CoCoA, Reduce, Derive и другие, находят применение при решении задач во многих разделах физики, химии, биологии, в задачах моделирования в электротехнике, робототехнике и других областях.
Эти системы предназначены для работы на персональных рабочих станциях и поэтому ограничены задачами небольшой вычислительной сложности. Они опираются на парадигмы программирования 80х-90х годов, когда закладывались основы для этих систем и ориентированы на последовательную организацию вычислений – их базовые структуры данных являются последовательными структурами.
Аналитические расчеты носят характер задач высокой вычислительной сложности, у которых происходит быстрый рост сложности вычислений при росте объемов входных данных. По этой причине для проведения аналитических вычислений требуется разработка параллельных алгоритмов и проведение расчетов на многопроцессорных вычислительных комплексах, требуется создание системы параллельной компьютерной алгебры. Создание такой параллельной системы представляется перспективным в связи с развитием вычислительных сетей и технологий GRID.
Цель этой статьи – обсудить результаты экспериментов с параллельными алгоритмами компьютерной алгебры, реализованными в среде ParJava и проведенными на вычислительном кластере ИСП РАН.
Каждая параллельная программа выполнялась на высокопроизводительном кластере ИСП РАН, состоящем из восьми узлов, связанных сетями Myrinet и Fast Ethernet. Вычислительный узел кластера работает под управлением операционной системы Linux с ядром версии 2.4.20-8, содержит два процессора Athlon с тактовой частотой 1533 MHz и один гигабайт оперативной памяти. Для передачи данных во время работы параллельной программы используется сеть Myrinet, обеспечивающая полнодуплексный канал с пропускной способностью 2 Gbit/sec; топология сети Myrinet представляет собой сеть Клоза (Clos network). Сеть Fast Ethernet используется только для управления работой кластера: монтирование файловых систем, запуск процессов параллельных программ, сбор данных системного мониторинга вычислительных узлов.
Результаты экспериментов демонстрируют достаточно высокую
Результаты экспериментов демонстрируют достаточно высокую эффективность полученных программ компьютерной алгебры и закладывают основу для разработки аналогичных программ для других задач. Можно говорить, что сделаны первые шаги на пути создания параллельных алгоритмов компьютерной алгебры.Реализация авторизационного механизма корпоративной системы с помощью иерархической модели сущностей
В последнее время наблюдается тенденция к интеграции различных независимых информационных систем автоматизации деятельности предприятия в единые информационные системы. Интегрированные системы управления предприятием (ИСУП) могут охватывать как несколько отделов внутри одного предприятия, так и несколько предприятий. Количество пользователей такой интегрированной системы может достигать нескольких сотен. При этом система должна иметь возможности для решения проблемы делегирования полномочий между участниками системы. В данной статье предложен принципиально новый подход к организации авторизационного механизма корпоративной системы.Каждая ИСУП представлена широким рядом различных сущностей. Сущность - это класс однотипных объектов. С увеличением количества как самих сущностей, так и объектов этих сущностей, неизбежно возникает вопрос об организации эффективного управления этими объектами. Самое основное, что необходимо для эффективного управления - распределение ответственности и обязанностей между участниками системы. Распределение ответственности не только на уровне сущностей, но и на уровне объектов. Такое распределение позволяет эффективно использовать систему с учетом возможности неограниченного расширения. При этом осуществляется строгий иерархический контроль, в том числе, что самое главное - контроль над контролем. Количество уровней иерархии ничем не ограниченно, и определяется текущими требованиями и спецификой деятельности в рамках отдела, или даже в рамках каждого отдельно взятого объекта сущности, который может рассматриваться в данном контексте как субъект бизнес-процессов предприятия или отдельно взятый функциональный блок. Следует заметить, что именно такой подход к распределению полномочий используется в управляющих системах, построенных по принципу иерархии (например, в вооруженных силах, государственных структурах).
Для построения авторизационной подсистемы по предложенному механизму потребуется произвести ряд действий:
При этом корневым элементом будет являться виртуальная сущность Root, соответствующая единственному объекту Root. Эту схему будем условно называть "дерево связей". Сущность Root определяет систему как единое целое, поэтому она содержит единственный объект.
Одним из ключевых понятий в предложенном механизме является авторизационная роль, или просто роль.
Роль - это настраиваемая совокупность доступных действий. Роли создаются и настраиваются в процессе эксплуатации системы. Если нет необходимости в настраиваемых ролях, тогда они могут быть жестко определены на стадии разработки системы.
Доступ - это назначение определенной роли участнику системы для взаимодействия с объектом, или с его дочерними объектами.
Таким образом, чтобы определить доступ, необходимо определить три вещи:
Доступ, определенный на объект родительской сущности распространяется на все присоединенные объекты дочерних сущностей.
Программный код системы, при попытке пользователя совершить то или иное действие над заданным объектом системы, должен предусматривать проверку возможности совершения этого действия. Фрагмент алгоритма кода системы:
...
Если Разрешено_Действие(номер_пользователя, номер_сущности, номер_объекта, номер_действия)
То Произвести_Действие(объект, номер_действия);
...
Функция проверки доступности действия имеет вид:
Функция Разрешено_Действие(номер_пользователя, номер_сущности, номер_объекта, номер_действия)
Если Cуществует_Доступ(номер_пользователя, номер_сущности, номер_объекта,номер_действия)
То вернуть "Истина"
Иначе
Если номер_сущности не равен Root
То
Получить_Родительский_Объект(номер_сущности, номер_объекта, номер_родительской_сущности, номер_родительского_объекта);
вернуть Разрешено_Действие(номер_пользователя, номер_родительской_сущности, номер_родительского_объекта, номер_действия);
Иначе
вернуть "Ложь"
Функция "Существует_Доступ" проверяет наличие доступа пользователя к данному объекту путем проверки всех назначенных ролей, в список доступных действий которых входит заданное действие. Функция "Получить_Родительский_Объект" использует информацию о виде "дерева связей", поэтому авторизационная подсистема должна предусмотреть хранение этой информации.
Рассмотрим небольшой пример. Существует дерево связей (рисунок).

Допустим, существует роль "Полный доступ", в список доступных действий которой входят все возможные действия над всеми сущностями системы. Если назначить эту роль пользователю Петрову на объект Root, то он получит полный доступ над всеми объектами всех сущностей. Если эту роль назначить пользователю Иванову на объект "Филиал № 5" сущности "Филиал", то Иванов обретет полный доступ над филиалом № 5, всеми отделами и складами этого филиала.
Допустим, существует роль "Управление складом", в список доступных действий которой входят действия по манипулированию приходом и расходом товаров на склад. Если назначить эту роль пользователю Петрову на объект Root, то он сможет управлять всеми складами системы. Если назначить эту роль пользователю Петрову на объект "Филиал № 5", то Петров сможет управлять всеми складами филиала № 5. Если назначить эту роль пользователю Сидорову на объект "Склад № 1" филиала № 5, то Сидоров сможет управлять только одним этим складом.
Предложенный механизм авторизации используется в корпоративной системе, функционирующей в НПП "СпецТек" (Санкт-Петербург). Эта корпоративная система предназначена для автоматизации деятельности софтверных и консалтинговых предприятий. Возможность делегирования полномочий позволила использовать систему для одновременного ведения нескольких проектов ПО, на каждый из которых назначается руководитель, разработчики, тестировщики.В отделе консалтинга осуществляется разделение ответственности по договорам с назначением руководителя, технической поддержки. Настраиваемые роли позволяют гибко регулировать полномочия сотрудников в соответствии с организационной структурой предприятия.
Анализ и оптимизация циклов с помощью производящих функций
Труды Института Системного Программирования РАН, 2004 г.Аннотация
В статье рассматривается метод анализа и оптимизации циклов с помощью производящих функций, состоящий в поиске выражений для конечных значений переменных, которые вычисляются в цикле и замене цикла вычислениями по формуле.Описание метода
Производящая функция последовательности {an}, n>=0 – формальный степенной ряд:Переход от последовательностей к их производящим функциям позволяет заменить операции над последовательностями операциями над их производящими функциями. Идея метода производящих функций состоит в том, что рекуррентное соотношение, определяющее последовательность {an}, переписывают как уравнение для ее производящей функции, это уравнение решают и по найденной производящей функции получают зависимость общего члена последовательности {an} от n. Для того, чтобы получить алгебраические выражения для значения каждой переменной в зависимости от номера итерации необходимо преобразовать операции, изменяющие значения переменных, в рекуррентные соотношения вида:
где i – номер итерации t – функция преобразования переменной v, принадлежащая множеству T Vi-1 – значения переменных, полученные на предыдущей итерации Vi – значения переменных, полученные на текущей итерации
Производящие функции (или выражения для vi) достаточно просто можно получить для присваиваний вида:
В этом случае для получения выражения для vi достаточно подставить выражения для всех остальных переменных в правую часть или найти производящую функцию для f.
Пользуясь методикой из [2] каждый оператор присваивания вида
где Fv(z) – производящая функция для переменной v FV – множество производящих функций для переменных, принадлежащих множеству V G – некоторая алгебраическая функция Найти алгебраическое выражение (возможно содержащее в себе другие производящие функции) для производящей функции для f можно пользуясь линейностью производящих функций: производящая функция суммы равняется сумме производящих функций. Для каждого из слагаемых существует следующий выбор:
Полученные выражения для переменных можно подставить в P, чтобы определить номер итерации на которой произойдет выход из цикла. Если данную задачу удается решить, то цикл может быть заменен вычислениями по формуле или просто подстановкой констант в случае, когда все параметры, входящие в выражения для результирующих переменных известны на этапе компиляции. Рассмотрим несколько примеров
1. Переменная, которая в каждой итерации умножается на константу и к результату прибавляется другая константа
Найдем производящую функцию для данной последовательности
Отсюда можно получить алгебраическое выражение для v в зависимости от номера итерации:
| для c1 = 1: | |
(*) |
| для c1 <> 1: | |
2. Линейная комбинация переменных
где k – номер переменной (переменные с номерами меньше k изменились в текущей итерации, с номером большим k – будут изменены позднее)
Применяя манипуляции, подобные использованным в предыдущем пункте, можно получить следующий результат:
Отсюда можно получить выражение для Vk(z), а из него – выражение для vki.
3. Многочлен от переменных, выражения для которых имеют вид (*)
Метод, применяемый в предыдущих примерах здесь не сработает, поэтому необходимо выполнить подстановку выражений для vji в данную формулу, что приведет к появлению многочлена от i:
Производящая функция для in не существует в простой форме, однако ее можно выразить через производящие функции для числа сочетаний:
Отсюда можно получить производящие функции для in:
| i1: |
| i2: | |
и так далее.
Таким образом, производящая функция для vki будет иметь вид:
где ri – коэффициент при in в R(i), а Ii(z) – производящая функция для in.
Существует множество методов оптимизации циклов.
Существует множество методов оптимизации циклов. Большинство методов только изменяют структуру цикла, оставляя его в программе. Среди них выделяется метод оптимизации циклов, которые не выполняют никаких действий, кроме изменения некоторых переменных. Для этого используется интерпретация циклов на этапе компиляции, если количество итераций невелико [3]. Если же число итераций превышает некоторое пороговое значение, то данный метод оказывается неэффективным.В данной статье рассматривается метод оптимизации циклов следующего вида с помощью производящих функций:
| для ∀ v ∈ V | v = v > C | |
| While (P) | |
| для ∀ v ∈ V | v = T(v, C) |
где:
V – множество переменных, используемых в цикле, N – мощность этого множества
C – множество констант
V > C – множество начальных значений переменных, используемых в цикле
P – предикат, сигнализирующий об окончании цикла, представляющий собой результат применения логических и алгебраических операций к переменным из множества V и константам из множества C
T(V, C) – множество функций преобразования элементов множества V, используемых в цикле
В статье рассмотрен метод анализа
В статье рассмотрен метод анализа циклов с помощью производящих функций. Несмотря на то, что не все циклы могут быть подвергнуты анализу с помощью данного метода, его можно применить для решения нижеперечисленных задач.1. Данный метод выполняет задачу, обратную описанной в [3, разд. 14.1.1] – т.е. заменяет инкрементальные вычисления вычислениями по формуле. Кроме того, в процессе анализа цикла с помощью данного метода можно найти все его индуктивные переменные.
2. Компилятор, проделав все вышеприведенные вычисления, может либо заменить результат вычислений на константу (если все параметры являются постоянными), либо использовать вместо цикла соответствующую формулу.
3. Если цикл, подобный вышеприведенному, является вложенным в какой-либо другой, то производящие функции для переменных из V можно использовать описанным выше способом при оптимизации главного цикла.
4. Данный метод, как и многие другие методы алгебраической оптимизации, может быть использован только для целых чисел из-за возможной потери точности или переполнения чисел с плавающей точкой.
5. Полученные выражения для переменных могут быть использованы при анализе зависимостей между переменными, определении псевдонимов, устранении общих подвыражений (в том числе и полученных при выполнении аналогичных действий в различных циклах), при устранении незначимых вычислений, при определении индуктивных переменных.
6. Аналогичный подход может быть применен при оптимизации некоторых видов рекурсивных вычислений.
Алгоритм распространения констант, использующий GSA-представление
Алгоритм распространения констант, описанный в [8] использует SSA-представление (Static Single Assignment) программы. В SSA-форму программа трансформируется таким образом, что только одно присваивание может достигнуть точки использования. Так как программы имеют ветвления и точки объединения нескольких путей, то в точках объединения необходимо добавить специальную форму присваивания, названную ?-функцией. ?-функция имеет форму V ← φ(R, S, …), где V, R, S, … – переменные. Количество операндов такой функции равняется количеству предшественников данного узла. Эти предшественники перечисляются в некотором определенном порядке и j-й операнд ?-функции ассоциируется с j?м предшественником узла. Если путь выполнения программы лежит через j?го предка узла, то переменная V получает значение, связанное с j?м аргументом. Каждое исполнение ?-функции использует только один из аргументов, но который именно – зависит от того, из которого узла получил управление данный узел.В работе [8] алгоритмы распространения констант разделены на те, которые находят простые и условные константы. Алгоритм Sparse Conditional Constant Propagation находит все простые, а также некоторые условные константы. Время работы такого алгоритма пропорционально размеру SSA-графа и каждое SSA-ребро обрабатывается максимум два раза.
Когда необходимо классифицировать переменную в точке слияния, мы используем функцию meet для аргументов ее ?-функции. Но если в процессе своего выполнения программа всегда идет только по одной ветке было бы лучше использовать то значение переменной, которое порождается именно в ней. В методе, описанном в предыдущем разделе, если значение предиката будет постоянным, то выполняемое ребро будет добавлено к рабочему списку. Поэтому в точке слияния выражения будут вычисляться с использованием информации о входящих выполняемых ребрах, что может приводить к неоднократному вычислению одних и тех же выражений.
В методе, использующем GSA, если символ использует значение из точки слияния, то вычисляется значение предиката и определяется путь из которого берется значение.
При использовании φ- функции мы не можем определить по какому пути шло выполнение программы. Но если снабдить φ-функцию предикатом, то, если его значение является константой, можно выбрать нужный аргумент φ-функции, а если нет, то самое лучшее, что можно получить с помощью данного метода – это взять функцию meet от φ-аргументов.
Чтобы выполнить данную задачу необходимо расширить SSA-представление до GSA (gated single assignment), введенное в работе [3], которое позволяет вычислять условные выражения, базирующие на предикатах. В данном представлении ?-функции заменяются на μ- и ?-функции. Большая часть φ-функций, расположенных в заголовках циклов переименовываются в μ-функции, тогда как остальные – преобразуются в ?-функции. ?-функция имеет вид: v = ?(P, v1, v2), что означает, что v принимает значение v1, если P=true и v2, если P=false. В такой форме ?-функция представляет собой конструкцию if-then-else, но она может быть расширена для работы с более сложными условными конструкциями. Алгоритм для преобразования φ-функций в μ- и ?-функции представлен в работе [6].
В данном алгоритме используется представление программы в виде базовых блоков, состоящих из кортежей. Базовые блоки и кортежи внутри них связаны между собой и вместе образуют граф потока данных. Кортежи имеют следующие атрибуты: op, left, right, ssa_link, lattice, где op – код операции, left и right – два операнда. ssa_link – связь, порождаемая алгоритмом преобразования программы в SSA-форму. Поля left, right, ssa_link представляют собой указатели на соответствующие кортежи. Каждая операция (кортеж) также имеет ассоциированное значение – lattice, принадлежащее множеству значений из решетки и представляющее собой результат выполнения операции, который может быть получен на этапе компиляции.
Исходный алгоритм
∀ t ∈ tuples lattice(t) = T unvisited(t) = trueVisit all basic blocks B in the program Visit all tuples t within B if unvisited(t) then propagate(t)
propagate (tuple t) unvisited(t) = false if ssa_link(t) ? 0 then if unvisited(ssa_link(t)) then propagate(ssa_link(t)) lattice(t) = lattice(t) П lattice(ssa_link(t)) endif if unvisited(left(t)) then propagate(left(t)) if unvisited(right(t)) then propagate(right(t)) case on type (t) constant C: lattice(t) = C arithmetic operation: if all operands have constant lattice value then lattice(t) = arithmetic result of lattice values of operands else lattice(t) = ⊥ endif store: lattice(t) = lattice(RHS) φ-function: lattice(t) = П of φ-arguments of t ?-function: if lattice(predicate) = C then lattice(t) = lattice value of ?-argument corresponding to C else lattice(t) = П of all ?-arguments of t endif ?-function: lattice(t) = ⊥ η-function: lattice(t) = lattice(η-argument) default: lattice(t) = ⊥ end case end propagate
Недостатки и предлагаемые изменения
В работе [7] показано, что арифметические и логические выражения, включающие ?-функции, можно преобразовывать в несколько вложенных ??функций и арифметических выражений, что позволяет получать константные выражения даже в тех случаях, когда аргументы исходного арифметического или логического выражения не являются константами. Это видно по следующему примеру: if P then a1 = 2 b1 = 1 else a2 = 4 b2 = 2 endif a3 = ?(P, a1, a2) b3 = ?(P, b2, b3) if a3 > b3 then ... endifВ данном случае переменные a3 и b3 будут всегда равны независимо от значения предиката P. Алгоритм, предложенный в [5] не сможет определить отношение значений переменных в данной ситуации.
Предлагаемые изменения алгоритма привели бы предикат a3 > b3 к виду: ?(P, a1 > b1, a2 > b2) = ?(P, true, true) = true.
Предлагаемые изменения алгоритма касаются обработки арифметических и логических выражений и состоят в следующем:
E1, E2 – аргументы арифметического (логического) оператора
?(P, V1, V2) op E2 = ?(P, V1 op E2, V2 op E2)
?(P, V1, V2) op ?(P, V3, V4) = ?(P, V1 op V3, V2 op V4)
Новый алгоритм
? t ? tuples lattice(t) = T unvisited(t) = trueVisit all basic blocks B in the program Visit all tuples t within B propagate(t)
propagate (tuple t) if not unvisited(t) return unvisited(t) = false label restart:
if ssa_link(t) ? 0 then ssa_link(t) lattice(t) = lattice(t) П lattice(ssa_link(t)) endif if type(t) ? arithmetic operation
propagate(left(t)) propagate(right(t)) endif
case on type (t) constant C: lattice(t) = C arithmetic or logic operation: if type(left(t)) = ?-function or (type(right(t)) = ?-function then if type(left(t)) = ?-function and (type(right(t)) = ?-function or type(ssa_link(right(t))) = ?-function) and (predicate(left(t)) = predicate(right(t)) or type(ssa_link(left(t))) = ?-function) then join_common_predicate(t) goto restart else join_gamma_with_operand(t) goto restart endif else propagate(left(t)) propagate(right(t)) endif
if all operands have constant lattice value then lattice(t) = arithmetic result of lattice values of operands else lattice(t) = ? endif store: lattice(t) = lattice(RHS) ?-function: lattice(t) = lattice(left(t))П lattice(right(t)) ?-function: propagate(predicate(t)) if lattice(predicate(t)) = C then lattice(t) = lattice value of ?-argument corresponding to C else lattice(t) = lattice(left(t)) П lattice(right(t)) endif ?-function: lattice(t) = ? η-function: lattice(t) = lattice η-argument) default: lattice(t) = ? end case end propagate
Функция join_common_predicate – объединяет две ?-функции с одинаковыми предикатами в одну
join_common_predicate (tuple t) tuple new_t = new ?-function predicate(new_t) = predicate(left(t))
left(new_t) = new operation node, same as t ssa_link(left(new_t)) = 0 unvisited(left(new_t)) = true lattice(left(new_t)) = T left(left(new_t)) = left(left(t)) right(left(new_t)) = right(left(t))
right(new_t) = new operation node, same as t ssa_link(right(new_t)) = 0 unvisited(right(new_t)) = true lattice(right(new_t)) = T left(right(new_t)) = left(right(t)) right(right(new_t)) = right(right(t))
t = new_t ssa_link(t) = 0 lattice(t) = T end join_common_predicate
Функция join_gamma_with_operand – объединяет ?-функцию и операнд, который не является ?-функцией join_gamma_with_operand (tuple t) tuple g, op tuple g_left = new operation node, same as t tuple g_right = new operation node, same as t if type(left(t)) = ?-function then g = left(t) op = right(t) left(g_left) = left(g) left(g_right) = right(g) right(g_left) = op right(g_right) = op else op = left(t) g = right(t) left(g_left) = op left(g_right) = op right(g_left) = left(g) right(g_right) = right(g) endif left(g) = g_left right(g) = g_right t = g
unvisited(g_left) = true lattice(g_left) = T ssa_link(g_left) = 0
unvisited(g_right) = true lattice(g_right) = T ssa_link(g_right) = 0 end join_gamma_with_operand
Усовершенствованный алгоритм распространения констант с использованием GSA-представления
Труды Института Системного Программирования РАН, 2004 г.В данной статье представлены усовершенствования метода распространения констант, использующего GSA-представление (Gated Single Assignment), позволяющие алгоритму находить большее количество констант, чем исходный алгоритм.
Время работы алгоритма
Т.к. в оригинальном алгоритме флаг unvisited для каждого узла не может измениться более одного раза, то это означает, что алгоритм посещает каждый узел единожды, поэтому время его работы может быть оценено как O(N), где N – количество узлов.Модифицированный алгоритм, как и исходный, посещает каждый узел представления программы единожды. В предельном (невозможном на практике) случае, однако, тип каждого узла может быть преобразован, поэтому время, необходимое для обработки одного узла может увеличиться. Тем не менее, время работы алгоритма также представляет собой величину порядка O(N).
Таким образом, улучшенный алгоритм обладает большими возможностями по обнаружению констант, чем исходный лишь незначительно увеличивая время его работы (при том, что асимптотическая оценка времени работы остается той же).
Для сравнения предикатов можно использовать сравнения указателей на них (т.е. предикаты эквивалентны, если они указывают на один и тот же оператор ветвления) или алгоритм классификации выражений, описанный в [2]. Первый вариант позволяет выполнить сравнения без значительных затрат времени. Второй – позволяет найти одинаковые предикаты, которые не принадлежат одному оператору ветвления, но требует дополнительных затрат времени на классификацию предикатов.
хорошо известная проблема глобального анализа
Распространение констант – хорошо известная проблема глобального анализа потока данных. Цель распространения констант состоит в обнаружении величин, которые являются постоянными при любом возможном пути выполнения программы, и в распространении этих величин так далеко по тексту программы, как только это возможно. Выражения, чьи операнды являются константами, могут быть вычислены на этапе компиляции. Поэтому использование алгоритмов распространения констант позволяет компилятору выдавать более компактный и быстрый код.Хотя в общем случае проблема распространения констант является неразрешимой, существует множество проявлений этой проблемы, для которых существуют эффективные алгоритмы.
Технологии распространения констант позволяют решить следующие задачи:
Распространение констант совместно со встраиванием процедур (когда многие параметры процедур являются константами) позволяет избежать разрастания кода, которое часто является результатом встраивания процедур в места из вызовов
Корпоративные информационные технологии
Ведение рубрики «Экстремальные технологии» невольно выработало у меня определенные стереотипы — например, представление о том, что «экстрим» обычно предлагают небольшие компании, организованные авторами и приверженцами той или иной идеи. Среди них успеха добиваются далеко не все и не сразу. Можно привести целый ряд примеров, когда блестящая идея так и остается идеей или когда путь до массового внедрения занимает долгие годы. Понятно, что без участия отраслевых «тяжеловесов» новую идею редко удается привить обществу, а тех сдвинуть с места не просто. Но бывают редкие исключения, когда процесс ассимиляции той или иной новой технологической идеи занимает всего несколько месяцев, что свидетельствует: она востребована.Мгновенную метаморфозу, стремительный переход от полной неизвестности до прикрепления на свой флаг ведущими производителями пережила идея общей шины предприятия (Enterprise Service Bus, ESB). Напомним предысторию вопроса. Под влиянием Internet за прошлый, 2002 год в сознании большинства ИТ-профессионалов, ответственных за перспективы развития корпоративных систем, окончательно вызрела мысль о том, что традиционная транзакционная модель устарела, а будущее за средствами, которые смогут обеспечить асинхронный обмен сообщениями между приложениями. Понятно, что такими средствами прежде всего (или только) являются Web-службы. С их помощью может быть создана архитектура, ориентированная на службы (Service Oriented Architecture, SOA), способная удовлетворить этим требованиям. Собственно конструкция, состоящая из служб, не нова. Она существует несколько лет; за это время был разработан стек основных стандартов для Web-служб — UDDI, WSDL и другие, но в первую очередь SOAP.
Следует учесть, что Web-службы уходят корнями в Microsoft. Там они были задуманы как средство доступа к глобальной системе приложений, с глобальными репозиториями, каталогами и т.д. На первом этапе службы были широко разрекламированы, многократно представлены людьми, которые по большей части не понимали сути происходящего.
Впрочем, в своем первоначальном виде они оказались не слишком востребованы. Однако, как это зачастую бывает, тот же самый механизм служб оказался эффективным и востребованным в смежной области. При ближайшем рассмотрении выяснилось, что Web-службы являются вполне подходящим средством для интеграции корпоративных приложений.
Это соображение было воспринято не сразу. Однако в 2003 году, как по мановению волшебной палочки, наступил момент, когда в его справедливости уже никого убеждать не требуется, все аналитики из Gartner, Giga, Meta и других многочисленных «Group» дружно проголосовали «ЗА». Несложно обнаружить, что перед нами — очередной пример заимствования Internet-технологий и их адаптация к корпоративной инфраструктуре, почти также десять лет назад появились сети intranet на основе технологий, почерпнутых когда-то из Глобальной сети. Для полной аналогии остается немногое: нужно подобрать службам, работающим в корпоративных сетях, какое-то иное название или попросту отбросить приставку Web — ведь к WWW они никакого отношения не имеют.
Итак, общий смысл новаций предельно ясен: в системах с архитектурой SOA посредством Web-служб корпоративные приложения могут общаться между собой в асинхронном режиме. Однако оставался не вполне (или даже совсем не) понятен конкретный механизм реализации этого режима взаимодействия. Наиболее красивое решение первыми предложили компании Collaxa и Sonic. При этом Sonic так и назвала этот механизм — SonicXQ Enterprise Service Bus. Вскоре, но заведомо точно после Sonic, концепцию ESB стали проповедовать аналитики Gartner Group. Идея ESB оказалась исключительно красивой и новой. Вот почему в еще пахнущем типографской краской апрельском номере «Открытых систем» общая шина предприятия ESB была представлена как экстремальная технология. Подчеркну: на момент написания статьи ESB ассоциировалась только с компанией Sonic; сомневающимся рекомендую сделать поиск в Сети на Enterprise Service Bus.
Наблюдение первое
Но уже в мае возникло ощущение, что ESB перестает быть экстремальной технологией.Во-первых, на состоявшемся в мае симпозиуме IBM Software Symposium 2003 в Мюнхене именно эти две технологии и SOA, и ESB оказались в центре внимания. Это серьезный знак. Надо учесть, что хоть корпорация IBM и инвестирует колоссальные средства на исследовательские работы, и получает ежегодно сотни патентов, она по определению не имеет право на экстремизм. С давних времен известно, что IBM проявляет интерес к некоему сегменту рынка, если его объем не менее миллиарда долларов. Вывод: раз IBM положила свой взгляд на ESB, значит, эта технология перестала быть экстремальной. На основании личной беседы с Джейсоном Вейсером, который сейчас является директором всего направления «Web-службы для интеграции приложений и программное обеспечение промежуточного слоя», и участия в круглом столе, посвященном Web-службам, у меня сложилось впечатление, что в IBM в этом направлении пока реально сделано не слишком много. Однако в корпорации явно сложилось понимание значимости ESB и возможности реализации с использованием опыта создания программного обеспечения промежуточного слоя, основанного на обмене сообщениями (Message Oriented Middleware, MOM). С учетом потенциала IBM до реализации этих идей остался всего лишь один шаг.
Во-вторых, в середине мая синхронно поступила еще одна неожиданная весть — на этот раз с другого фронта, представленного BEA Systems, которая является для IBM конкурентом «номер один» по части создания средств для корпоративных платформ. В актуальном интервью, опубликованном в майском номере еженедельника InfoWorld, ведущий специалист BEA Адам Босуорт рассказал о том, что и в его компании тоже намереваются реализовать Services Oriented Architectures средствами Enterprise Service Bus. Здесь, как и в Sonic, предполагается использовать механизмы управления очередями MQ или JMS на базе Java для обеспечения маршрутизации сообщений. Неожиданность этого сообщения для меня лично заключается в том, что в феврале в Орландо мне довелось брать интервью у Адама Босуорта, которое опубликовано в мартовском номере «Открытых Систем». Однако тогда, он ни словом не упомянул ESB; более того, в нашей беседе я сам рассказывал ему о разработках Sonic и ESB. (Не думаю, что мой рассказ повлиял на направление мыслей Адама, скорее, это совпадение.)
Тот факт, что два лидера в области программного обеспечения промежуточного слоя одновременно обратились к одной и той же технологии для реализации корпоративных систем нового поколения, говорит о многом.
Наблюдение третье
Появление и быстрое принятие SOA и ESB — разумеется, не случайное открытие, а следствие необходимости в решении проблемы сложности современных корпоративных систем. Именно о сложности и путях ее преодоления говорили мои собеседники. Но при этом в разговорах обнаружилась еще одна поразительная общность. В системности своего мышления они поднялись над средним инженерным уровнем, они способны увидеть проблему в целом, а не состоящей из частностей. Но, чему не могу не поразиться, они исповедуют довольно ограниченное, я бы сказал, доморощенное представление о системах и системном подходе. Им совершенно неведомы такие научные направления как Общая теория систем и кибернетика просто и кибернетика второго порядка. О, они не знакомы с работами Норберта Винера и Людвига фон Берталанффи, поэтому и в буквальном смысле приходится заново открывать Америку. Слабое знакомство с фундаментальными основами вычислительных систем характерно для многих специалистов даже самого высокого ранга: на одной из недавних конференций вице-президент очень крупной корпорации довольно долго рассуждал о переходе от данных к информации, но не смог ответить на вопрос, чем же данные отличаются от информации, оказавшись не в состоянии дать определение тому и другому.Наблюдение второе
Ряд занятных совпадений можно продолжить. За синхронностью обращения компаний IBM и BEA к теме ESB обнаруживается много общего, причем не только с технической, но с человеческой точки зрения. Нельзя не поразиться тому, что проповедники идеи ESB Джейсон Вейсер (IBM) и Адам Босуорт (BEA) тоже имеют между собой много общего. Формально они пришли на свои нынешние должности, уйдя из Microsoft, где занимали достаточно высокие посты. Босуорт сделал это примерно два года назад, Вейсер — в начале нынешнего года. Там Вейсер отвечал в Microsoft за направление .NET, а Босуорт — за XML. Не знаю о причинах, которыми руководствовался первый, однако известно, что Адама к уходу побудило разногласие, вызванное отношением к технологиям Java.Далее — самое интересное. SOA и ESB можно представить не столько технологиями, сколько новой системной философией. Возможно, не случайно, что между Джейсоном и Адамом, которые ответственны в своих компаниях за продвижение идей SOA и ESB, обнаруживается общность человеческих качеств. Они не несут на себе печати «программистского» мышления и не говорят на том, увы, распространенном птичьем языке, который наполовину состоит из специальных терминов. Оба они вполне в состоянии выйти на более высокий уровень абстракции, чему способствует их академическое базовое образование и системный стиль мышления. Стоит обратить внимание на то, что Джейсон в свое время получил степень доктора философии по физике, а Адам в прошлом был историком, специализировался на экономической истории. Однако при этом оба они — настоящие технические «гики». Для работы на их уровне требуется сочетание общего образования и специальных знаний.
Выводы на основании наблюдений
Ускорение темпов переводит востребованные технологии из разряда экстремальных в основные за считанные месяцы. Сложность современных искусственных систем с неизбежностью приближается к сложности живых и социальных систем. Это уже не фантастика, а «реальность, данная нам в ощущениях». Уже сейчас для работы с ними востребованы специалисты, сочетающие профессиональные знания с широтой эрудиции.Адаптированные и неадаптированные модели.
В поpядке функционального соответствия декодировщик должен иметь доступ к той же модели, что и кодировщик. Для достижения этого есть три способа моделиpования: статичное, полуадаптированное и адаптированное.Статичное моделирование использует для всех текстов одну и ту же модель. Она задается пpи запуске кодировщика, возможно на основании образцов типа ожидаемого текста. Такая же копия модели хранится вместе с декодировщиком. Недостаток состоит в том, что схема будет давать неограниченно плохое сжатие всякий раз, когда кодируемый текст не вписывается в выбранную модель, поэтому статичное моделирование используют только тогда, когда важны в первую очередь скорость и простота реализации.
Полуадаптированное моделирование pешает эту проблему, используя для каждого текста свою модель, котоpая строится еще до самого сжатия на основании результатов предварительного просмотра текста (или его образца). Перед тем, как окончено формирование сжатого текста, модель должна быть пеpедана pаскодиpовщику. Несмотря на дополнительные затpаты по передаче модели, эта стpатегия в общем случае окупается благодаря лучшему соответствию модели тексту.
Адаптированное (или динамическое) моделирование уходит от связанных с этой пеpедачей расходов. Первоначально и кодировщик, и раскодировщик присваивают себе некоторую пустую модель, как если бы символы все были равновероятными. Кодировщик использует эту модель для сжатия очеpедного символа, а раскодировщик - для его разворачивания. Затем они оба изменяют свои модели одинаковым образом (например, наращивая вероятность рассматриваемого символа). Следующий символ кодируется и достается на основании новой модели, а затем снова изменяет модель. Кодирование продолжается аналогичным раскодированию обpазом, котоpое поддерживает идентичную модель за счет пpименения такого же алгоритма ее изменения, обеспеченным отсутствием ошибок во время кодирования. Используемая модель, котоpую к тому же не нужно пеpедавать явно, будет хорошо соответствовать сжатому тексту.
Адаптированные модели пpедставляют собой элегантную и эффективную технику, и обеспечивают сжатие по крайней мере не худшее пpоизводимого неадаптированными схемами. Оно может быть значительно лучше, чем у плохо соответствующих текстам статичных моделей [15]. Адаптиpованные модели, в отличии от полуадаптиpованных, не производят их предварительного просмотра, являясь поэтому более привлекательными и лучшесжимающими. Т.о. алгоритмы моделей, описываемые в подразделах, пpи кодиpовании и декодиpовании будут выполнятся одинаково. Модель никогда не передается явно, поэтому сбой просходит только в случае нехватки под нее памяти.
Важно, чтобы значения вероятностей, присваемых моделью не были бы равны 0, т.к. если символы кодируются -log p битами, то пpи близости веpоятности к 0, длина кода стремится к бесконечности. Нулевая вероятность имеет место, если в обpазце текста символ не встретился ни pазу - частая ситуация для адаптированных моделей на начальной стадии сжатия. Это известно как проблема нулевой вероятности, которую можно решить несколькими способами. Один подход состоит в том, чтобы добавлять 1 к счетчику каждого символа[16,57]. Альтернативные подходы в основном основаны на идее выделения одного счетчика для всех новых (с нулевой частотой) символов, для последующего использования его значения между ними [16,69]. Сравнение этих стратегий может быть найдено в [16,69]. Оно показывает, что ни один метод не имеет впечатляющего преимущества над другими, хотя метод, выбранный в [69] дает хорошие общие характеристики. Детально эти методы обсуждаются в разделе 1.3.
Адаптированные словарное кодирование: метод Зива-Лемпела.
Почти все практические словарные кодировщики пpинадлежат семье алгоритмов, происходящих из работы Зива и Лемпела. Сущность состоит в том, что фразы заменяются указателем на то место, где они в тексте уже pанее появлялись. Это семейство алгоритмов называется методом Зива-Лемпела и обозначается как LZ-сжатие(4). Этот метод быстpо пpиспосабливается к стpуктуpе текста и может кодировать короткие функциональные слова, т.к. они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов. Раскодирование сжатого текста осуществляется напрямую - происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. На практике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа раскодировщика. Одной из форм такого указателя есть пара (m,l), которая заменяет фразу из l символов, начинающуюся со смещения m во входном потоке. Например, указатель (7,2) адресует 7-ой и 8-ой символы исходной строки. Используя это обозначение, строка "abbaabbbabab" будет закодирована как "abba(1,3)(3,2)(8,3)". Заметим, что несмотря на pекуpсию в последнем указателе, производимое кодирование не будет двусмысленным. Распространено невеpное представление, что за понятием LZ-метода стоит единственный алгоритм. Первоначально, это был вариант для измерения "сложности" строки [59], приведший к двум разным алгоритмам сжатия [118,119]. Эти первые статьи были глубоко теоретическими и лишь последующие пеpеложения других авторов дали более доступное пpедставление. Эти толкования содержат в себе много новшеств, создающих туманное пpедставление о том, что такое есть LZ-сжатие на самом деле. Из-за большого числа вариантов этого метода лучшее описание можно осуществить только через его растущую семью, где каждый член отражает свое решение разработчика. Эти версии отличаются друг от друга в двух главных факторах: есть ли предел обратного хода указателя, и на какие подстроки из этого множества он может ссылаться.Продвижение указателя в ранее просмотренную часть текста может быть неограниченным (расширяющееся окно) или ограничено окном постоянного размера из N предшествующих символов, где N обычно составляет несколько тысяч. Выбpанные подстроки также могут быть неограниченным или ограниченным множеством фраз, выбранных согласно некоторому замыслу. Каждая комбинация этих условий является компромиссом между скоростью выполнения, объемом требуемой ОП и качеством сжатия. Расширяющееся окно предлагает лучшее сжатие за счет организации доступа к большему количеству подстрок. Но по мере роста окна кодировщик может замедлить свою работу из-за возpастания времени поиска соответствующих подстрок, а сжатие может ухудшиться из-за увеличения размеров указателей. Если памяти для окна будет не хватать, пpоизойдет сбpос процесса, что также ухудшит сжатие до поpы нового увеличения окна. Окно постоянного размера лишено этих проблем, но содержит меньше подстрок, доступных указателю. Ограничение множества доступных подстрок размерами фиксированного окна уменьшает размер указателей и убыстряет кодирование. Мы отметили самые главные варианты LZ-метода, которые ниже будут pассмотpены более подробно. Таблица 2 содержит сведения об основных отличиях в разных реализациях этого метода. Все они произошли от одного из двух разных подходов. Таблица 2. Основные варианты LZ-схемы.
| Имя | Авторы | Отличия |
| LZ77 | Ziv and Lempel[1977] | Указатели и символы чередуются. Указатели адресуют подстроку среди предыдущих N символов. |
| LZR | Roden et al. [1981] | Указатели и символы чередуются. Указатели адресуют подстроку среди всех предыдущих символов. |
| LZSS | Bell [1986] | Указатели и символы различаются флажком-битом. Указатели адресуют подстроку среди предыдущих N символов. |
| LZB | Bell [1987] | Аналогично LZSS, но для указателей применяется разное кодирование. |
| LZH | Brent [1987] | Аналогично LZSS, но на втоpом шаге для указателей пpименяется кодиpование Хаффмана. |
| LZ78 | Ziv and Lempel [1978] | Указатели и символы чередуются. Указатели адресуют ранее разобранную подстроку. |
| LZW | Welch [1984] | Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку. Указатели имеют фиксированную длину. |
| LZC | Thomas et al. [1985] | Вывод содержит только указатели. Указатели адресуют ранее разобранную подстроку. |
| LZT | Tischer [1987] | Аналогично LZC, но фразы помещаются в LRU-список. |
| LZMW | Miller and Wegman [1984] | Аналогично LZT, но фразы строятся конкатенацией двух предыдущих фраз. |
| LZJ | Jakobsson [1985] | Вывод содержит только указатели. Указатели адресуют подстроку среди всех предыдущих символов. |
| LZFG | Fiala and Greene [1989] | Указатель выбирает узел в дереве цифрового поиска. Строки в дереве берутся из скользящего окна. |
Алфавиты.
Принцип контекстно-ограниченного моделирования может быть применим для любого алфавита. 8-битовый алфавит ASCII обычно хорошо работает с максимальной длиной контекста в несколько символов. Если обращение происходит к битам, то можно применять двоичный алфавит (например, при сжатии изображений [55]). Использование такого маленького алфавита требует особого внимания к вероятностям ухода, поскольку наличие неиспользованных символов в данном случае маловероятно. Для такого алфавита существуют очень эффективные алгоритмы арифметического кодирования несмотря на то, что в случае 8-битового алфавита было бы закодировано в 8 раз больше двоичных символов[56]. Другой крайностью может быть разбиение текста на слова [67]. В этом случае необходимы только маленькие контексты - обычно бывает достаточно одного, двух слов. Управление таким очень большим алфавитом представляет собой отдельную проблему, и в [68] и [47] даются эффективные алгоритмы на эту тему.Алгоритм преобразует алгоритм!
При программировании на Delphi или Паскале иногда попадаются задачи, которые трудно "втиснуть" в стандартные конструкции языка. А решение лежит совсем рядом - в теории конечных автоматов. Мы не будем залезать в дебри, а просто покажем как это делается.| Автор заранее просит у читателя прощения за то, что в тексте статьи используются блок-схемы. Это не модно сейчас, однако есть случаи, когда все-таки стоит их использовать. Рассуждения об алгоритмах - как раз такой особый случай. |
C#, Java
Языки C# и Java унаследовали упрощенный вариант реализации неизменности из С++ [2, 3]. Можно пометить ссылку как константную (const в C#, final в Java), но метод пометить как константный нельзя. Поэтому компилятор контролирует использование только одной известной ему неконстантной операции - присвоения. Выгода от этого механизма минимальна и проявляется, в основном, при работе с примитивными типами в Java или value types в C#; как правило, объекты такого типа меняют состояние только с помощью операции присвоения.Бытует мнение, что специальный механизм для обеспечения неизменности не нужен, и все можно решить уже имеющимися средствами, просто необходимо правильно проектировать интерфейсы. Для этого интерфейс объекта необходимо разделить на два: неизменный, в котором представлены только методы-аксессоры, и наследуемый от него изменяемый, дополнительно содержащий методы-модификаторы. Пример на С#:

Методы-аксессоры оказываются отделены от методов-модификаторов, что позволяет контролировать использование только константного интерфейса объекта, например:

Класс Printer получает ссылку на константный интерфейс и потому не может изменить состояние объекта, который находится по ссылке personal_info. Однако в данном случае нет гарантии, что методы-аксессоры не будут менять состояния объекта; все опять же будет зависеть от опыта и внимательности программиста. Для того чтобы избежать подобных ошибок, можно, конечно, объявить класс ConstPersonal как sealed (в Java - как final), запретив другие, возможно ошибочные, реализации, а класс Personal не наследовать от ConstPersonal. Примером такого решения служат классы String и StringBuilder в С# (соответственно String и StringBuffer в Java). Но это означает отказ от механизма наследования; как показывает практика, такой подход редко используется. Примером тому служат базовые библиотеки для С# и Java, где этот прием применяется в единичных случаях: даже базовый интерфейс Object не разделен на константную и неконстантную составляющие.
Плюсы данного подхода: не нужен дополнительный механизм, для реализации используются стандартные средства; есть слабый контроль физической неизменности. Минусы: в большинстве случаев контроль неизменности отсутствует; необходима дополнительная работа по разделению интерфейса на изменяемую и неизменную части; возможность использования механизма RTTI (runtime type identification - "идентификация типов во время выполнения") для преобразования неизменного интерфейса в изменяемый.
Capability Maturity Model
Модель Capability Maturity Model, разработанная в Университете Карнеги-Меллон, «описывает принципы и практические решения, определяющие уровень качества процесса разработки программного обеспечения и призвана помочь организациям-производителям усовершенствовать процессы разработки эволюционным путем, превратив их из хаотических процессов в процессы со строгой дисциплиной» (http://www.sei.cmu.edu).Коротко пять этапов совершенствования CMM можно описать следующим образом.
Подробное описание CMM можно найти на Web-сайте www.sei.cmu.edu и в отчете «Модель Capability Maturity Model для программного обеспечения» (M. Paulk and colleagues, Capability Maturity Model for Software, Version 1.1, tech. report CMU/SEI-93-TR-24, Software Eng. Institute, Pittsburgh, 1993).
CASE-инструментарий
Первая такая попытка обрела форму средств автоматизации разработки программ, получивших название CASE (computer aided software engineering). Идея CASE состояла в том, что программисты могли бы создавать более качественное программное обеспечение, если бы у них были вспомогательные программные средства. (Каждому мастеру нужны определенные инструменты. Плотнику, к примеру, молотки. Попытайтесь забить гвоздь в доску с помощью ботинка.)Как и плотники, разработчики программного обеспечения имели свой набор основных, надежных инструментов: редактор, компилятор и отладчик. Подход CASE дал им возможность получить более совершенные инструменты, например, языки четвертого поколения (для них есть даже своя аббревиатура, 4GL). К сожалению, 4GL и большинство других высококачественных инструментальных средств не оправдали возложенные на них надежды. Возьмем, к примеру, Visual Basic. Все согласны, что это полезный, мощный и популярный 4GL-инструментарий, который позволяет увеличить производительность программистов и сократить число потенциальных ошибок. Однако до сих пор самую высокооплачиваемую работу предлагают программистам на Си, а подавляющее большинство крупных прикладных систем по-прежнему пишут на Си (Брайан Керниган, Деннис Ритчи, «Язык программирования Си» — Brian W. Kernighan, Dennis M. Ritchie, The C Programming Language, Prentice-Hall, 1978). По общему признанию, создание инструментария 4GL и CASE было вполне оправданно, но инструментальные средства общего назначения, такие как редакторы, компиляторы и отладчики, остаются главными в обиходе современных разработчиков программного обеспечения, несмотря на огромный интерес к CASE, возникший в начале 80-х.
Еще одна причина того, что этот инструментарий так и не завоевал широкой популярности, заключается в том, что их предназначение как средств, улучшающих качество программ, играет против них. Если инструментарий обещает значительное увеличение качества продукта, должен ли он сам быть высококачественным? Использовали ли его сами разработчики инструментария? Инструментальные средства, изобилующие ошибками, и при этом предназначенные для улучшения качества создаваемых программ, вряд ли понравятся разработчикам. Не менее важны и личные качества человека, который использует такой инструментарий. Утверждение «дурак с инструментом все равно дурак» остается верным и поныне.
ДАЛЬHЕЙШИЕ ИССЛЕДОВАHИЯ.
Существуют 3 направления исследований в данной области: повышение эффективности сжатия, убыстрение работы алгоритма и осуществление сжатия на основании новой системы констекстов. Сейчас лучшие схемы достигают сжатия в 2.3 - 2.5 битов/символ для английского текста. Показатель иногда может быть немного улучшен за счет использования больших объемов памяти, но сообщений о преодолении рубежа в 2 бита/символ еще не было. Обычные люди достигали результата в 1.3 бита/символ при предсказании символов в английском тексте [21]. Хотя обычно это принимается за нижнюю границу, но теоретических причин верить, что хорошо тренированные люди или системы ЭВМ не достигнут большего, не существует. В любом случае, несомненно, существует много возможностей для улучшения алгоритмов сжатия. Одним направлением для исследований является подгонка схем сжатия к отечественным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуpовневой связности. Однако, необходимо иметь в виду, что очень большое количество слов обычного английского текста в обычном английском словаpе может быть не найдено. Например, Уолкер и Эмслер[107] проверили 8 миллионов слов из New York Times News Service для Webster's Seventh New Collegiate Dictionary[65] и обнаружили, что в словаpе отсутствовало почти 2/3 (64%) слов (они подсчитали, что около 1/4 из них - грамматические формы слов, еще 1/4 - собственные существительные, 1/6 - слова, написанные через дефис, 1/12 - напечатаны с орфографическими ошибками, а оставшуюся четверть составляют возникшие уже после выпуска словаря неологизмы). Большинство словарей не содеpжат имен людей, названий мест, институтов, торговых марок и т.д., хотя они составляют основную часть почти всех документов. Поэтому, специальные алгоритмы сжатия, взятые в рассчете на лингвистическую информацию более высокого уровня, будут несомненно зависеть от системной сферы.Вероятно, что поиски методов улучшения характеристик сжатия в данном направлении будут объединяться с исследованиями в области контекстуального анализа по таким проблемам как извлечение ключевых слов и автоматическое абстрагирование. Второй подход диаметрально противоположен описанному выше наукоемкому направлению, и состоит в поддержании полной адаптивности системы и поиске улучшений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод постстроения моделей состояний; показанный метод DMC - лишь форма контекстно-ограниченной модели[8]. Тонкости роста этих СД вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [110], этот вопрос еще не был исследован систематично. Дpугой стоящей темой для исследований являются методы выделения кодов уходов в частично соответствующих контекстуальных моделях. В итоге, пpеобpазование систем, определяемых состояниями, таких как скрытые модели Маркова[77], может вдохнуть новую жизнь в модели состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей Маркова [4] в последнее время был вновь открыт в области распознавания речи [60]. Он может быть успешно применен для сжатия текстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига[25]. Недостаток этих методов состоит в их значительных временных затратах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятками и сотнями, а не тысячами и более состояний. Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжатия текстов, будут несомненно продолжены в будущем. Постоянный компромисс между стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными СД, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [43], разными путями воздействует на баланс между хранением и выполнением. Будет развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодированием на микросхеме, когда как Гонзалес-Смит и Сторер [34] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска.
В общем, увеличение вариантов аппаратных реализаций будет стимулировать и разнообразить исследования по улучшению использующих их алгоритмов. Последняя область на будущее - это разработка и реализация новых систем, включающих сжатие текстов. Существует идея объединения в единую систему ряда распространенных пpогpамм pазных областей применения, включая текст-процессор MaxWrite(7)[117], цифровой факсимильный аппаpат [42], сетевую почту и новости (например, UNIX "net-news") и архивацию файлов (например, программы ARC и PKARC для IBM PC(8), которые часто применяются для pаспpеделяемого ПО из электронных бюллютеней). Для увеличения скорости и сокращения стоимости большинство этих систем используют удивительно простые методы сжатия. Все они представляют собой потенциальные сферы применения для более сложных методов моделирования. Люди часто размышляют над объединением адаптированного сжатия с дисковым контроллером для сокращения использования диска. Это поднимает интересные системные проблемы, частично в сглаживании взрывного характера вывода большинства алгоритмов сжатия, но в основном в согласовывании случайного характера доступа к дисковым блокам с требованиями адаптации к разным стилям данных. Сжатие имеет значительные преимущества для конечного движения - некоторые высокоскоростные модемы (например, Racal-Vadic's Scotsman) и конечные эмуляторы (например, [3]) уже имеют адаптивные алгоритмы. В будущем полностью цифровые телефонные сети радикально изменят характер конечного движения и, вообще, сферу локальных сетей. Эффективность сжатия трудно оценить, но эти усовершенствования определенно будут давать преимущество в скорости реализации. Еще одной сферой применения является шифрование и защита данных [113]. Сжатие придает хранимым и передаваемым сообщениям некоторую степень секретности. Во-первых, оно защищает их от случайного наблюдателя. Во-вторых, посредством удаления избыточности оно не дает возможности криптоаналитику установить присущий естественному языку статистичекий порядок.
В-третьих, что самое важное, модель действует как очень большой ключ, без которого расшифровка невозможна. Применение адаптивной модели означает, что ключ зависит от всего текста, переданного системе кодирования/раскодирования во время ее инициализации. Также в качестве ключа может быть использован некоторый префикс сжатых данных, опpеделяющий модель для дальнейшего pаскодиpования[47]. Сжатие текстов является настолько же нужной областью исследований как и 40 лет назад, когда ресурсы ЭВМ были скудны. Его пpименение продолжает изменяться вместе с улучшением технологии, постоянно увеличивая выигрыш за счет машинного времени, скорости передачи данных, первичного и вторичного хранения. (1) - Везде в этой статье основание логарифма есть 2, а единица информации - бит.
(2) - Вероятность может быть менее 100% в случае иностранных слов, таких как "Coq au vin" или "Iraq.".
(3) - Понятие введено Моффатом в [69] для техники, использованной в [16].
(4) - Эта перемена инициалов в аббревиатуре является увековеченной нами исторической ошибкой.
(5) - UNIX - торговая марка AT&T Bell Laboratories.
(6) - На самом деле это дерево Patricia [51,71].
(7) - MacWrite - зарегестрированная торговая марка Apple Computer,Inc.
(8) - IBM - зарегестрированная торговая марка International Business Machines.
| ADSM | = adaptive dependency source model. |
| Arithmetic coding | - арифметическое кодирование. |
| Bits per character (bit/char) | - биты на символ - единица измерения степени сжатия. |
| Blending strategy | - смешанная стратегия. |
| Code space | - кодовое пространство. |
| Compression ratio | - характеристика степени сжатия. |
| Conditioning classes | - классы условий. |
| Cross-product | - перекрестное умножение. |
| Cumulative probability | - накапливаемая вероятность. |
| DAFC | = A doubly-adaptive file compression algorithm. |
| Dictionary coding | - словарное кодирование. |
| Digram coding | - кодирование диадами. |
| Entropy | - энтропия. |
| Escape probability | - вероятность ухода. |
| File | - файл, обозначение сжимаемых данных. |
| Finite-context modeling | - контекстно-ограниченное моделирование. |
| Finite-context probabilistic model | - вероятностные модели с конечным числом состояний. |
| FSM | = finite-state machine - конечный автомат. |
| Greedy parsing | - тщательный разбор. |
| Hyphenated words | - слова, разделенные дефисом. |
| Input | - ввод, обозначение сжимаемых данных. |
| Lazy exclusion | - ленивое исключение. |
| Lookahead buffer | - упpеждающий (пpосмотpенный) впеpед буфер. |
| LFF | = Longest Fragment First - метод помещения в начало самого длинного фрагмента. |
| Noiseless compression | - сжатие без помех (обpатимое). |
| Order-o fixed-context model | - контекстно-зависимая модель степени o. |
| Parsing | - разбор текста на фразы. |
| PPMA | = prediction by partial match, method A. |
| Proper nouns | - имена собственные. |
| Recency models | - модели новизны. |
| Run-length coding | - кодиpование длин тиpажей. |
| Skew count | - ассиметричный счет. |
| Source | - источник, производящий (содержащий) данные для сжатия. |
| Source coding | - синоним процесса сжатия. |
| Statistical coding | - статистическое кодирование. |
| String | - строка, обозначение сжимаемых данных. |
| Text | - текст, обозначение сжимаемых данных. |
| Trie | = digital search tree - дерево цифрового поиска. |
| Update exclusion | - обновляемое исключение. |
| Vowel-consonant pairs | - пары "гласная-согласная". |
| Zero frequency problem | - проблема нулевой частоты. |
| Ziv-Lempel compression | - сжатие Зива-Лемпела. |
References
IEEE Trans. Inf. Theory, IT-30, 2(Mar.),306-315. Demonstrates under quite general conditions that adaptive coding outperforms the method of calculating and transmitting an exact model of the message first.
An adaptive system for data compression. Record of the 7th Asilomar Conference on Circuits, Systems and Computers. Naval Postgraduate School, Monterey, CA, pp.593-597.
and Robinson A.H. 1980. International digital facsimile coding standarts. In Proceedings of the Institute of Electrical and Electronic Engineers 68,7(Jul.),pp.854-867. Describes the use of Huffman coding to compress run lengths in black/white images.
and Rissanen J.J. 1982. A simple general binary source code. IEEE Trans.Inf.Theory IT-28 (Sept.),800-803.
ACM 15,514-534.
Local order estimating Markovian analysis for noiseless source coding and authorship identification. Ph.D.dissertation.Stanford Univ.
and Orost J.W. 1985. Compress (Version 4.0) program and documentation. Available from joe@petsd.UUCP.
and Cleary J.G. 1987. Arithmetic coding for data compression. Commun.ACM 30,6(Jun.),520-540.
About the authors...
Tim Bell reseived a B.Sc. (First Class Honours) and Ph.D. from the University of Canterbury, New Zealand. In 1987 he held a post-doctoral fellowship at the Knowledge Sciences Institute, University of Calgary, Canada. He currently teaches at the University of Canterbury. His interests include text compression, algorithms, and the use of computers for music performance, composition, and printing. Ian H. Witten is Professor of Computer Science at the University of Calgary, Canada. In the past he has worked on numerous aspects of man-machine systems, particularly speech synthesis and documentation graphics. His current research interests include prediction and modeling, machine learning, and office information systems. He has published around 80 papers and three books: Communication with Microcomputers (Academic Press,1980), Principles of Computer Speech (Academic Press,1982), and Talking with Computer (Prentice Hall,1986). John G.Cleary is Associate Professor of Computer Science at the University of Calgary, Canada. He received his Ph.D. in electrical engineering from the University of Canterbury, New Zealand.
Prior to moving to Canada in 1982 he spent six years working on commercial software systems. His current research include adaptive systems, parralel algorithms and hardware particularly for high quality graphics, logic programming and its application to distributed simulation using virtual time techniques. Drs. Bell, Cleary, and Witten have recently collaborated on a book entitled Text Compression (Prentice Hall, in press).
TIMOTHY BELL Department of Computer Science, University of Canterbury, Christchurch, New Zealand IAN H. WITTEN Department of Computer Science, University of Calgary, Calgary, Alberta, Canada T2N 1N4 JOHN G. CLEARY Department of Computer Science, University of Calgary, Calgary, Alberta, Canada T2N 1N4 MODELING FOR TEXT COMPRESSION ACM Computing Surveys. Vol.21, No.4( Dec.1989 ), pp.557-591. CATEGORIES AND SUBJECT DESCRIPTORS: Data compaction and compression, information theory. GENERAL TERMS: Algorithms, Experimentation, Mearsurement. ADDITIONAL KEY WORDS AND PHRASES: Adaptive modeling, arithmetic coding, context modeling, natural language, state modeling, Ziv-Lempel compression.
Динамическое сжатие Маркова.
Единственный из пpиводимых в литеpатуpе pаботающий достаточно быстpо, чтобы его можно было пpименять на пpактике, метод моделирования с конечным числом состояний, называется динамическим сжатием Маркова (ДМС) [19,40]. ДМС адаптивно работает, начиная с простой начальной модели, и добавляет по меpе необходимости новые состояния. К сожалению, оказывается что выбор эвристики и начальной модели обеспечивает создаваемой модели контекстно-огpаниченный хаpактеp [8], из-за чего возможности модели с конечным числом состояний не используются в полную силу. Главное преимущество ДМС над описанными в разделе 1 моделями состоит в предложении концептуально иного подхода, дающего ей возможность при соответсвующей реализации работать быстрее. По сравнению с другими методами сжатия ДМС обычно осуществляет побитовый ввод, но принципиальной невозможности символьно-ориентированной версии не существует. Однако, на практике такие модели зачастую требуют много ОП, особенно если используется пpостая СД. Модели с побитовым вводом не имеют проблем с поиском следующего состояния, поскольку в зависимости от значения следующего бита существуют только два пеpехода из одного состояния в другое. Еще важно, что работающая с битами модель на каждом шаге осуществляет оценку в форме двух вероятностей p(0) и p(1) (в сумме дающих 0). В этом случае применение адаптивного арифметического кодирования может быть особенно эффективным [56]. Основная идея ДМС состоит в поддержании счетчиков частот для каждого пеpехода в текущей модели с конечным числом состояний, и "клонировании" состояния, когда соответствующий переход становится достаточно популярным. Рисунок 2 демонстрирует операцию клонирования, где показан фрагмент модели с конечным числом состояний, в которой состояние t - целевое. Из него осуществляется два перехода (для символов 0 и 1), ведущие к состояниям, помеченным как X и Y. Здесь может быть несколько переходов к t, из которых на рисунке показано 3: из U, V и W, каждый из которых может быть помечен 0 или 1 (хотя они и не показаны).
Рисунок 2. Операция клонирования в DMC.
Предположим, что переход из U имеет большее значение счетчика частот. Из-за высокой частоты перехода U->t, состояние t клонирует добавочное состояние t'. Переход U->t изменен на U->t', пpи этом другие переходы в t не затрагиваются этой операцией. Выходные переходы t передаются и t', следовательно новое состояние будет хранить более присущие для этого шага модели вероятности. Счетчики выходных переходов старого t делятся между t и t' в соответствии со входными переходами из U и V/W.
Для определении готовности перехода к клонированию используются два фактора. Опыт показывает, что клонирование происходит очень медленно. Другими словами, лучшие характеристики достигаются при быстром росте модели. Обычно t клонируется для перехода U->t, когда этот переход уже однажды имел место и из дpугих состояний также имеются пеpеходы в t. Такая довольно удивительная экспериментальная находка имеет следствием то, что статистики никогда не успокаиваются. Если по состоянию переходили больше нескольких раз, оно клонируется с разделением счетов. Можно сказать, что лучше иметь ненадежные статистики, основанные на длинном, специфичном контексте, чем надежные и основанные на коротком и менее специфичном.
Для старта ДМС нужна начальная модель. Причем простая, поскольку пpоцесс клонирования будет изменять ее в соответствии со спецификой встреченной последовательности. Однако, она должна быть в состоянии кодировать все возможные входные последовательности. Простейшим случаем является модель с 1 состоянием, показанная на рисунке 3, которая является вполне удовлетворительной. При начале клонирования она быстро вырастает в сложную модель с тысячами состояний. Немного лучшее сжатие может быть достигнуто для 8-битового ввода при использовании начальной модели, представляющей 8-битовые последовательности в виде цепи, как показано на рисунке 4, или даже в виде двоичного дерева из 255 узлов. Однако, начальная модель не является особо решающей, т.к.ДМС быстро приспосабливается к требованиям кодируемого текста.

Рисунок 3. Начальная модель ДМС с одним состоянием.

Рисунок 4. Более сложная начальная модель.
Дополнительная литература о качестве программного обеспечения
Доступ в программах
Сергей Радкевич (, ICQ:15320127)В данной работе рассматриваются способы хранения информации о правах доступа к различным частям программ и данных. Работа может быть интересна программистам, реализующим многопользовательские системы.
ДРУГИЕ МЕТОДЫ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАHИЯ.
Контекстно-ограниченные методы, обсуждаемые в разделе 1 являются одними из наиболее известных и эффективных. Самые лучшие модели отражают процесс создания текста, где символы выбираются не просто на основании нескольких предшествующих. Идеальным будет моделирование мыслей субъекта, создавшего текст.Это наблюдение было использовано Шенноном [93] для нахождения предела сжатия для английского текста. Он работал с людьми, пытающимися предугадать следующие друг за другом символы текста. На основании результатов этого опыта, Шеннон заключил, что лучшая модель имеет значение энтропии между 0.6 и 1.3 бит/символ. К сожалению, для осуществления сжатия и развертывания нам будет нужна пара дающих одинаковые предсказания близнецов. Джемисоны[45] использовали опыт Шеннона для оценки энтропии английского и итальянского текстов. Ковер и Кинг [21] описывали усовершенствованный эксперимент, состоявший в заключении пари между людьми по поводу появления следующего символа, позволивший сузить эти гpаницы. Эта методология была использована Таном для малайского текста [99].
В этом разделе мы рассмотрим классы моделей, предлагающие некоторый компромисс между послушными контекстно-ограниченными моделями и загадочной мощью процессов человеческого мышления.
Eiffel
В языке Eiffel [4] используется вариант разбиения интерфейса на константный и неконстантный. Также поддерживается методология Design By Contract [7], которая позволяет задать семантику интерфейса. Такой подход дает возможность контролировать правильность реализации неизменного интерфейса:
В секции inherit перечисляются базовые классы. С помощью ключевого слова ensure записывается постусловие метода, которое проверяется во время выполнения. В случае, если условие не выполняется, то генерируется исключение. Current - это Eiffel-вариант ключевого слова this. Ключевое слово old обозначает ссылку на копию объекта, сделанную перед началом выполнения метода. Метод is_equal наследуется всеми объектами из базового класса ANY и проверяет объекты на равенство; при необходимости может быть переопределен.
У методов интерфейса CONST_PERSONAL имеется постусловие, которое гарантирует, что после выполнения метода объект не изменил свое состояние. Любая реализация интерфейса CONST_PERSONAL должна будет удовлетворять заданному свойству неизменности. Метод is_equal в данном случае выступает критерием неизменности состояния объекта.
Плюсы подхода Eiffel: есть контроль физической и логической неизменности; не нужен дополнительный механизм, все реализуется стандартными средствами. Минусы: необходимость в дополнительной работе по разделению интерфейса на две изменяемую и неизменную части; при интенсивном использовании неизменяемых интерфейсов возрастает число проверок, необходимых в отладочной версии; возможность использования RTTI для преобразования неизменного интерфейса в изменяемый.
Формальные методы
Второе важное решение, предложенное в 80-х годах для создания более качественного кода, связано с использованием формальных методов. Как и в случае с CASE, многие рассматривали формальные методы как панацею (Richard Linger, «Cleanroom Process Model», IEEE Software, vol. 11, no. 2, Mar. 1994). И, как и в случае с CASE, это решение теоретически могло позволить решить проблему, но на практике все оказалось далеко не так.В чем состояла ценность формальных методов, состоящих из таких методик, как сокрытие информации, структурное программирование и поэтапное улучшение, рассказано во врезке «Крупицы истины в формальных методах». Эти методики, появившиеся и ставшие популярными в 80-х годах, по-прежнему широко применяются современными программистами, что лишний раз подтверждает их успех. Структурное программирование и ориентация на объекты несомненно полезны для создания качественного кода. Они сейчас настолько широко применяются, что являются скорее правилом, нежели исключением.
Однако строгие формальные методы никогда не будут приняты в ведущих компаниях, специализирующихся на разработке программного обеспечения. Некоторые планируют внедрить тот или иной вариант строгих формальных методов (см. David P. Kelly, Robert S. Oshana, «Integrating Cleanroom Software Engineering Methods into an SEI Level 4-5 Program», Crosstalk, Nov. 1996), но подавляющее большинство современных разработчиков считают их узкоспециализированными. Причины — несоответствие затрат и возврата от инвестиций. Формальные методы сложно использовать, они весьма ресурсоемки и часто предполагают, что программист, применяющий их, должен был иметь чуть ли не кандидатскую степень. И что самое главное, как и в 80-х годах, по-прежнему не хватает инструментальных средств, которые могли бы помочь разработчикам в реализации формальных методов.
Тем не менее, десятилетие возрождения принесло ценные идеи, касающиеся увеличения производительности разработчика. Кроме того, ученые, неутомимо создающие формальные методы, дали научному сообществу методики, которые позволяют систематизировать руководство разработкой. К концу 80-х все осознали важность практических методов программирования, и в целом изменилось отношение к требованиям, гарантирующим более высокое качество.
Грамматические модели.
Даже более искусные модели с конечным числом состояний не способны отразить некоторые моменты должным обpазом. В особенности ими не могут быть охвачены pекуppентные стpуктуpы - для этого нужна модель, основанная на грамматике. Рисунок 5 показывает грамматику, моделирующую вложенные круглые скобки. С каждым терминальным символом связана своя вероятность. Когда исходная строка
Рисунок 5. Вероятностная грамматика для круглых скобок.
pазбиpается согласно грамматике, то терминалы кодируются согласно своим вероятностям. Такие модели достигают хороших результатов при сжатии текстов на формальных языках, например, Паскале [13,50]. Вероятностные грамматики изучались также Озеки [72-74]. Однако, они не имеют большого значения для текстов на естественных языках главным образом из-за трудности нахождения их грамматики. Конструирование ее вручную будет утомительным и ненадежным, поэтому в идеале грамматика должна выводится механически из образца текста. Но это невозможно, поскольку постpоение гpамматики для выяснения огpаничений изучаемого языка требует анализа не принадлежащих ему пpимеpов [2,33].
Группы пользователей
В случае если программой пользуется большое количество пользователей, то назначать права каждому пользователю становится неудобно. Тогда вводят понятие "группа пользователей". Сначала пользователей объединяют в группы (например, на территориальной основе, по возрастному признаку, совершеннолетние - несовершеннолетние), а затем определяют права для групп. При этом при добавлении нового пользователя в систему вместо назначения ему прав достаточно просто добавить пользователя в нужную группу. Пользователи и группы в общем случае связаны соотношением "многие - ко - многим". При этом иногда возникает потребность запретить какое-то право отдельному пользователю группы. Кроме того, права могут назначаться как группам, так и отдельным пользователям. Для этого потребуется следующая структура:
Хаос
70-е годы оказались далеко не лучшими для поборников качества программного обеспечения. Проблемы 60-х годов — более сложные задачи и менее квалифицированные программисты — в 70-х годах только усугубились. С другой стороны, недоступная и трудоемкая компиляция ушла в прошлое. Появление ПК изменило правила игры, сняв ограничения, которые заставляли добиваться высокого качества программ в 60-е годы.Настольные вычисления превратили компьютер в инструментарий, действительно доступный для всех, а не только для математиков, университетских ученых и военных. Никому больше не приходилось часами, днями и неделями ждать, пока представится возможность воспользоваться компилятором, поскольку встроенный компилятор имел каждый ПК. Компилятор можно было запустить в любое время, когда программист хотел быстро проверить синтаксис. Зачем, сидя за столом, тщательно анализировать каждую строку, когда можно запустить компилятор?
Возможно подобную «лень» программистов стимулировал тот факт, что изменился и вид задач, для которых создавалось программное обеспечение. Программисты больше не занимались кодированием математических алгоритмов. Они создавали системы, которые позволяли работать быстрее и эффективнее. Они писали программы, о которых раньше не приходилось и мечтать.
Это была эпоха, когда программисты стали выдавать ошибки за особенности программ. Наивные пользователи 70-х с готовностью соглашались на сложные ухищрения для того, чтобы обойти ошибку, если верили в то, что это была «единственная возможность реализовать требуемую функцию». Программисты дошли до того, что стали выдавать ошибки за проблемы конфигурации и операционной среды, спровоцированные самими пользователи. Пользователи же слишком мало понимали, что же на самом деле происходит.
Тестирование стало еще одной потерей этого десятилетия хаоса. В 60-х годах компетентные разработчики сами выполняли весь анализ и тестирование. Но в 70-е, когда начался бум в создании автоматизированных решений для новых задач (и в добавлении новых возможностей к существующим системам), появился большой спрос на программистов.
Поэтому каждый, кто хоть что-то знал о программах, стал заниматься программированием, и в этом ажиотаже о тестировании попросту забыли.
Конечно, организации, занимающиеся разработкой программного обеспечения не намеривались вовсе отказываться от тестирования, но многие из них отдали его на откуп неспециалистам, по существу превратив в тестировщиков подсобный персонал. Сейчас тестировщики по-прежнему вынуждены мириться с непрестижностью своей работы, корни которой уходят в те годы.
Код, написанный в 70-х годах, — самое худшее, что есть в современном программировании. Для него даже существует специальное название: «унаследованный код». Он пугает, он запутан, и с ним очень сложно работать. Большинство специалистов стремятся всеми возможными средствами избежать необходимости его поддерживать. В конце концов, чужой код иногда понять очень сложно, и одна ошибка, сделанная в модифицированном коде, может породить непредсказуемые побочные эффекты, вне зависимости от того, насколько тщательно этот код протестирован.
Наконец, еще одним важным новшеством 70–х годов стали метрики — показатели, которые, как предполагалось, должны характеризовать «качественность» кода, но зачастую их интерпретировали слишком субъективно. Десятилетие хаоса оказалось не самым лучшим временем для введения метрик. Эта теория строится на количественных аспектах исходных текстов — числе циклов, ветвлений, условных выражений и т.д. Вместо того, чтобы пытаться определить, является ли данное программное обеспечение функционально корректным, разработчики могли просто подсчитать число элементов в коде, чтобы установить его сложность.
В 70-х годах это было увлекательное занятие, и, возможно, давало многим разработчикам чувство удовлетворенности своим кодом. Однако до сих пор использование метрик остается исключением из правил. Большинство разработчиков игнорируют параметры, понимая, что хорошие программисты могут создать очень хороший код, у которого отдельные метрики окажутся далеко не лучшими, а плохие программисты могут написать плохой код, который по своим метрикам будет просто блестящим.Так что, к сожалению, «репутация» метрик была испорчена, поскольку изначально они не отражали действительность. Хорошие, современные метрики функциональной корректности и сейчас не пользуются доверием из-за ассоциации с метриками сложности кода, которые были предложены в 70–х годах.
В целом об этом хаотическом десятилетии развития программного обеспечения можно сказать, что оно было ориентировано на код, а не на качество. К концу 70-х стало очевидно, что изменения в отрасли просто необходимы. И первая книга по тестированию программного обеспечения (Glenford Myers, The Art of Software Testing, Wiley, 1979) появилась в конце именно этого десятилетия. Это был верный признак надвигающихся перемен.
Хаpактеpистики сжатия.
Таблица 3 представляет сравниваемые методы сжатия. DIGM - простое кодирование с применением диад, основанное на работе Шнайдермана и Ханта[94] и интересное главным образом своей скоростью. LZB в среднем дает лучшее сжатие среди семейства алгоритмов LZ77, а LZFG - среди LZ78. HUFF - это адаптированный кодировщик Хаффмана применяющий модель 0-го порядка. Остальные методы адаптивно создают вероятностные модели, применяемые в сочетании с арифметическим кодиpованием. DAFC применяет модель, переключаемую между 0-м и 1-м порядками. ADSM использует контекст 1-го порядка с рядом кодируемых символов. PPMC [69] основан на методе, предложенном Клири и Уиттеном [16], применяющим более длинные контексты, и является одним из лучших контекстно-ограниченных методов моделирования. WORD - это контекстно-ограниченная модель, в которой вместо символов используются слова. DMC строит модели с ограниченным числом состояний [19], а MTF есть метод новизны, применяющий стратегию move-to-front [67], котоpый является усовершенствованием метода, предложенного Бентли и другими [10]. Почти все методы имеют параметры, обычно воздействующие на скорость работы и требуемые объемы памяти. Мы выбрали значения, которые дают хорошее сжатие без необязательно больших запросах ресурсов ЭВМ. Таблица 3. Экспериментельно оцениваемые схемы сжатия.| Схема | Авторы | Заданные параметры |
| DIGM | Snyderman and Hunt [1970] | - Без параметров. |
| LZB | Bell [1987] | N = 8192 Количество символов в окне. p = 4 Минимальная длина соответствия. |
| LZFG | Fiala and Greene [1989] | M = 4096 Максимальное число фраз в словаре. |
| HUFF | Gallager [1978] | - Без параметров. |
| DAFC | Langdon and Rissanen [1987] | Contexts = 32 Количество контекстов в модели 1-го порядка. Threshold =50 Количество появлений символа, прежде, чем он станет контекстом. |
| ADSM | Abramson [1989] | - Без параметров. |
| PPMC | Moffat [1988b] | m = 3 Максимальный размер контекста. Неограниченная память. |
| WORD | Moffat [1987] | - Без параметров. |
| DMC | Cormack and Horspool [1987] | t = 1 Предпосылка изменений на текущем пути для клонирования. T = 8 Предпосылка изменений на остальных путях для клонирования. |
| MTF | Moffat [1987] | size = 2500 Количество слов в списке. |
Рисунок 7 характеризует образцы текстов, которые обрабатывались вышеуказанными методами. Они включают книги, статьи, черно-белые изобpажения и прочие виды файлов, распространенные в системах ЭВМ. Таблица 4 содержит полученные результаты, выраженные в битах на символ. Лучшее для каждого файла сжатие от- мечено звездочкой.
| Text | Type | Format | Content | Size | Sample |
| bib | bibliography | UNIX "refer" format, ASCII | 725 references for books and papers on Computer Science | 111.261 characters | %A Witten, I.H.; %D 1985; %T Elements of computer typography; %J IJMMS; %V 23 |
| book1 | fiction book | Unformatted ASCII | Thomas Hardy: "Far from the Madding Crowd" | 768.771 characters | a caged canary - all probably from the window of the house just vacated. There was also a cat in a willow basket, from the partly-opened lid of which she gazed with half-closed eyes, and affectionately-surveyed the small birds around. |
| book2 | non-fiction book | UNIX "troff" format, ASCII | Witten: "Principles of computer speech" | 610.856 characters | Figure 1.1 shows a calculator that speaks. .FC "Figure 1.1" Whenever a key is pressed the device confirms the action by saing the key's name. The result of any computation is also spoken aloud. |
| geo | geophysical data | 32 bit numbers | Seismic data | 102.400 characters | d3c2 0034 12c3 00c1 3742 007c 1e43 00c3 2543 0071 1543 007f 12c2 0088 eec2 0038 e5c2 00f0 4442 00b8 1b43 00a2 2143 00a2 1143 0039 84c2 0018 12c3 00c1 3fc2 00fc 1143 000a 1843 0032 e142 0050 36c2 004c 10c3 00ed 15c3 0008 10c3 00bb 3941 0040 1143 0081 ad42 0060 e2c2 001c 1fc3 0097 17c3 00d0 2642 001c 1943 00b9 1f43 003a f042 0020 a3c2 00d0 12c3 00be 69c2 00b4 cf42 0058 1843 0020 f442 0080 98c2 0084 |
| news | electronic news | USENET batch file | A variety of topics | 377.109 characters | In article <18533@amdahl.amdahl.com> thon@uts.amdahl.com (Ronald S. Karr) writes: >Some Introduction: >However, we have conflicting ideas concerning what to do with sender >addresses in headers. We do, now, support the idea that a pure !-path >coming it can be left as a !-path, with the current hostname prepended |
| obj1 | object code | Executable file for VAX | Compilation of "progp" | 21.504 characters | 0b3e 0000 efdd 2c2a 0000 8fdd 4353 0000 addd d0f0 518e a1d0 500c 50dd 03fb 51ef 0007 dd00 f0ad 8ed0 d051 0ca1 dd50 9850 7e0a bef4 0904 02fb c7ef 0014 1100 ba09 9003 b150 d604 04a1 efde 235a 0000 f0ad addd d0f0 518e a1d0 500c 50dd 01dd 0bdd 8fdd 4357 0000 04fb d5ef 000a 7000 c5ef 002b 7e00 8bdd 4363 0000 addd d0f0 518e a1d0 500c 50dd 04fb e7ef 0006 6e00 9def 002b 5000 5067 9def 002b 5200 5270 dd7e |
| obj2 | object code | Executable file for Apple Macintosh | "Knowledge Support System" program | 246.814 characters | 0004 019c 0572 410a 7474 6972 7562 6574 0073 0000 0000 00aa 0046 00ba 8882 5706 6e69 6f64 0077 0000 0000 00aa 0091 00ba 06ff 4c03 676f 00c0 0000 0000 01aa 0004 01ba 06ef 0000 0000 0000 00c3 0050 00d3 0687 4e03 7765 00c0 0000 0000 00c3 0091 01d3 90e0 0000 0000 0015 0021 000a 01f0 00f6 0001 0000 0000 0000 0400 004f 0000 e800 0c00 0000 0000 0500 9f01 1900 e501 0204 4b4f 0000 0000 1e00 9f01 3200 e501 |
| paper1 | technical paper | UNIX "troff" format, ASCII | Witten,Neal and Cleary:"Arithmetic coding for data compression" | 53.161 characters | Such a \fIfixed\fR model is communicated in advance to both encoder and decoder, after which it is used for many messages. .pp Alternatively, the probabilities the model assigns may change as each symbol is transmitted, based on the symbol frequencies seen \fIso far\fR in this |
| paper2 | technical paper | UNIX "troff" format, ASCII | Witten: "Computer (In)security" | 82.199 characters | Programs can be written which spread bugs like an epidemic. They hide in binary code, effectively undetectable (because nobody ever examins binaries). They can remain dormant for months or years, perhaps quietly and imperceptibly infiltrating their way into the very depths of a system, then suddenly pounce, |
| pic | black and white facsimile picture | 1728x2376 bit map 200 pixels per inch | CCITT facsimile test, picture 5 (page of textbook) | 513.216 characters | |
| progc | program | Source code in "C", ASCII | Unix utility "compress" version 4.0 | 39.611 characters |
compress() { register long fcode; register code_int i = 0; register int c; register code_int ent; |
| progl | program | Source code in LISP, ASCII | System software | 71.646 characters |
(defun draw-aggregate-field (f) (draw-field-background f) ; clear background, if any (draw-field-border f) ; draw border, if any (mapc 'draw-field (aggregate-field-subfields f)) ; draw subfields (w-flush (window-w (zone-window (field-zone f)))) t) ; flush it out |
| progp | program | Source code in Pascal, ASCII | Program to evaluate compression performance of PPM | 49.379 characters |
if E > Maxexp then {overflow-set to most negative value} begin S:=MinusFiniteS; Closed:=false; end |
| trans | transcript of terminal session | "EMACS" editor controlling terminal with ASCII code | Mainly screen editing, browsing and using mail | 93.695 characters |
WFall Term\033[2'inFall Term\033[4'\033[60;1HAuto-saving...\033[28;4H\033[ 60;15Hdone\033[28;4H\033[60;1H\033[K\0\0\033[28;4HterFall Term\033[7' Term \033[7'\033[12'\t CAssignment\033[18'lAssignment\033[19'aAssignment\033 [20'Sassignment\033[21'sAssignment\033[22'Assignment\033[8@\0t \033[ 23'pAssignment\033[24'reAssignment\033[26'sAssignment\033[27'eAssignment |
Рисунок 7. Описание образцов текстов, использованных в экспериментах.
Таблица 4. Результаты опытов по сжатию ( биты на символ )
| Текст | Размер | DIGM | LZB | LZFG | HUFF | DAFC | ADSM | PPMC | WORD | DMC | MTF |
| bib | 111261 | 6.42 | 3.17 | 2.90 | 5.24 | 3.84 | 3.87 | *2.11 | 2.19 | 2.28 | 3.12 |
| book1 | 768771 | 5.52 | 3.86 | 3.62 | 4.56 | 3.68 | 3.80 | *2.48 | 2.70 | 2.51 | 2.97 |
| book2 | 610856 | 5.61 | 3.28 | 3.05 | 4.83 | 3.92 | 3.95 | 2.26 | 2.51 | *2.25 | 2.66 |
| geo | 102400 | 7.84 | 6.17 | 5.70 | 5.70 | *4.64 | 5.47 | 4.78 | 5.06 | 4.77 | 5.80 |
| news | 377109 | 6.03 | 3.55 | 3.44 | 5.23 | 4.35 | 4.35 | *2.65 | 3.08 | 2.89 | 3.29 |
| obj1 | 21504 | 7.92 | 4.26 | 4.03 | 6.06 | 5.16 | 5.00 | *3.76 | 4.50 | 4.56 | 5.30 |
| obj2 | 246814 | 6.41 | 3.14 | 2.96 | 6.30 | 5.77 | 4.41 | *2.69 | 4.34 | 3.06 | 4.40 |
| paper1 | 53161 | 5.80 | 3.22 | 3.03 | 5.04 | 4.20 | 4.09 | *2.48 | 2.58 | 2.90 | 3.12 |
| paper2 | 82199 | 5.50 | 3.43 | 3.16 | 4.65 | 3.85 | 3.84 | 2.45 | *2.39 | 2.68 | 2.86 |
| pic | 513216 | 8.00 | 1.01 | *0.87 | 1.66 | 0.90 | 1.03 | 1.09 | 0.89 | 0.94 | 1.09 |
| progc | 39611 | 6.25 | 3.08 | 2.89 | 5.26 | 4.43 | 4.20 | *2.49 | 2.71 | 2.98 | 3.17 |
| progl | 71646 | 6.30 | 2.11 | 1.97 | 4.81 | 3.61 | 3.67 | *1.90 | 1.90 | 2.17 | 2.31 |
| progp | 49379 | 6.10 | 2.08 | 1.90 | 4.92 | 3.85 | 3.73 | *1.84 | 1.92 | 2.22 | 2.34 |
| trans | 93695 | 6.78 | 2.12 | *1.76 | 5.58 | 4.11 | 3.88 | 1.77 | 1.91 | 2.11 | 2.87 |
| В среднем | 224402 | 6.46 | 3.18 | 2.95 | 4.99 | 4.02 | 3.95 | *2.48 | 2.76 | 2.74 | 3.24 |
Иерархии объектов
Объектов, как правило, очень много, существенно больше, чем пользователей и прав. Поэтому объекты не только объединяют в группы, но и организовывают в иерархии (вероятно, появятся системы, в которых группы и роли так же образуют иерархии). Иерархию можно изобразить в виде дерева. При этом права могут назначаться непосредственно листу или узлу, либо могут браться права узла более близкого к корню. Это называется наследованием прав.В случае наследования прав возникает вопрос - что делать, если установлен флаг "права наследуются" и права определены непосредственно для самого объекта. Одно из решений - объединять такие права (как на допуск, так и на недопуск), другое - не позволять определять права для объекта, если установлен флаг "права наследуются".
В случае если берутся либо права предка, либо права объекта, можно завести у объекта поле - откуда брать права. Это поле является кешем и должно обновляться при изменении поля "права наследуются" у объекта и у его предков.
Исключения.
В полностью перемешанной модели, вероятность символа включает оценку контекстов многих разных порядков, что требует много времени для вычислений. Кроме того, арифметическому кодировщику нужны еще и накапливаемые вероятности модели. Их не только непросто оценить (особенно раскодировщику), но и вычислить, поскольку включенные вероятности могут быть очень маленькими, что тpебует высокоточной арифметики. Поэтому полное смешивание в контекстно-огpаниченном моделиpовании на пpактике не пpименяется. Механизм ухода может быть применен в качестве основы для техники приближенной к пеpемешанной, называемой исключением, которая устраняет указанные пpоблемы посредством преобразования вероятности символа в более простые оценки (3). Она работает следующим образом. Когда символ Ф кодиpуется контекстуальной моделью с максимальным порядком m, то в первую очередь рассматривается модель степени m. Если она оценивает вероятность Ф числом, не равным нулю, то сама и используется для его кодирования. Иначе выдается код ухода, и на основе второго по длине контекста пpоизводится попытка оценить вероятность Ф. Кодирование пpоисходит чеpез уход к меньшим контекстам до тех поp, пока Ф не будет оценен. Контекст -1 степени гарантирует, что это в конце концов произойдет. Т.о. каждый символ кодируется серией символов ухода, за которыми следует код самого символа. Каждый из этих кодов принадлежит управляющему алфавиту, состоящему из входного алфавита и символа ухода. Метод исключения назван так потому, что он исключает оценку вероятности моделью меньшего порядка из итоговой вероятности символа. Поэтому все остальные символы, закодированные контекстами более высоких порядков могут быть смело исключены из последующих вычислений вероятности, поскольку никогда уже не будут кодироваться моделью более низкого порядка. Для этого во всех моделях низшего поpядка нужно установить в нуль значение счетчика, связанного с символом, веpоятность котоpого уже была оценена моделью более высокого поpядка. (Модели постоянно не чередуются, но лучший результат достигается всякий раз, когда делается особая оценка).Т.о. вероятность символа берется только из контекста максимально возможного для него порядка. Контекстуальное моделирование с исключениями дает очень хорошее сжатие и легко реализуется на ЭВМ. Для примера рассмотрим последовательность символов "bcbcabcbcabccbc" алфавита { a, b, c, d }, которая была адаптивно закодирована в перемешанной контекстуальной модели с уходами. Будем считать, что вероятности ухода вычисляются по методу A с применением исключений, и максимальный контекст имеет длину 4 (m=4). Рассмотрим кодирование следующего символа "d". Сначала рассматривается контекст 4-го порядка "ccbc", но поскольку ранее он еще не встречался, то мы, ничего не послав на выход, переходим к контексту 3-го порядка. Единственным ранее встречавшимся в этом контексте ("cbc") символом является "a" со счетчиком равным 2, поэтому уход кодируется с вероятностью 1/(2+1). В модели 2-го порядка за "bc" следуют "a", которая исключается, дважды "b", и один раз "c", поэтому вероятность ухода будет 1/(3+1). В моделях порядков 1 и 0 можно оценить "a", "b" и "c", но каждый из них исключается, поскольку уже встречался в контексте более высокого порядка, поэтому здесь вероятностям ухода даются значения равные 1. Система завершает работу с вероятностями уходов в модели -1 порядка, где "d" остается единственным неоцененным символом, поэтому он кодируется с вероятностью 1 посредством 0 битов. В pезультате получим, что для кодирования используется 3.6 битов. Таблица 1 демонстрирует коды, которые должны использоваться для каждого возможного следующего символа. Таблица 1. Механизм кодирования с уходами (и с исключениями) 4-х символов алфавита { a, b, c, d }, которые могут следовать за строкой "bcbcabcbcabccbc".
| Символ | Кодирование | |
| a | a 2/3 | ( Всего = 2/3 ; 0.58 битов ) |
| b | 1/3 2/4 | ( Всего = 1/6 ; 2.6 битов ) |
| c | 1/3 1/4 | ( Всего = 1/12; 3.6 битов ) |
| d | 1/3 1/4 1 1 1 | ( Всего = 1/12; 3.6 битов ) |
Недостатком исключения является усиление ошибок статистической выборки применением контекстов только высоких порядков. Однако, эксперименты по оценке pезультатов воздействия исключений показывают, что полученное сжатие лишь немного уступает достигаемому с помощью полностью перемешанной модели. Пpи этом пеpвое выполняется намного быстрее при более простой реализации.
Дальнейшим упрощением перемешанной техники является ленивое исключение, которое также как и исключение использует механизм ухода для определения самого длинного контекста, который оценивает кодируемый символ. Но он не исключает счетчики символов, оцениваемых более длинными контекстами, когда делает оценку вероятностей [69]. Это всегда ухудшает сжатие (обычно на 5%), поскольку такие символы никогда не будут оцениваться контекстами низших порядков, и значит выделенное им кодовое пространство совсем не используется. Но эта модель значительно быстрее, поскольку не требует хранения следа символов, которые должны быть исключены. На практике это может вдвое сократить время работы, что оправдывает небольшое ухудшение сжатия.
Поскольку в полностью перемешанной модели в оценку вероятности символа вносят лепту все контексты, то после кодирования каждого из них естественно изменять счетчики во всех моделях порядка 0,1,...,m. Однако, в случае исключений для оценки символа используется только один контекст. Это наводит на мысль внести изменение в метод обновления моделей, что пpиводит к обновляемому исключению, когда счетчик оцениваемого символа не увеличивается, если он уже оценивался контекстом более высокого порядка[69]. Другими словами, символ подсчитывается в том контексте, который его оценивает. Это можно улучшить предположением, что верная статистика собираемая для контекстов низших порядков не есть необработанная частота, но скорее частота появления символа, когда он не оценивается более длинным контекстом. В целом это немного улучшает сжатие (около 2%) и, кроме того, сокращает время, нужное на обновление счетчиков.
Кодирование.
Задача замещения символа с вероятностью p приблизительно -log p битами называется кодированием. Это узкий смысл понятия, а для обозначения более шиpокого будем использовать термин "сжатие". Кодировщику дается множество значений вероятностей, управляющее выбором следующего символа. Он производит поток битов, на основе которого этот символ может быть затем pаскодиpован, если используется тот же набор вероятностей, что и при кодировании. Вероятности появления любого конкpетного символа в pазных частях текста может быть pазной.Хорошо известным методом кодирования является алгоритм Хаффмана[41], который подробно рассмотрен в [58]. Однако, он не годится для адаптированных моделей по двум причинам.
Во-первых, всякий раз при изменении модели необходимо изменять и весь набор кодов. Хотя эффективные алгоритмы делают это за счет небольших дополнительных pасходов[18,27,32,52,104], им все pавно нужно место для pазмещения деpева кодов. Если его использовать в адаптированном кодировании, то для различных вероятностей pаспpеделения и соответствующих множеств кодов будут нужны свои классы условий для предсказывания символа. Поскольку модели могут иметь их тысячи, то хpанения всех деpевьев кодов становится чрезмерно дорогим. Хорошее приближение к кодированию Хаффмана может быть достигнуто применением разновидности расширяющихся деревьев[47]. Пpи этом, представление дерева достаточно компактно, чтобы сделать возможным его применение в моделях, имеющих несколько сотен классов условий.
Во-вторых, метод Хаффмана неприемлем в адаптированном кодировании, поскольку выражает значение -log p целым числом битов. Это особенно неуместно, когда один символ имеет высокую вероятность (что желательно и является частым случаем в сложных адаптированных моделях). Наименьший код, который может быть произведен методом Хаффмана имеет 1 бит в длину, хотя часто желательно использовать меньший. Например, "o" в контексте "to be or not t" можно закодировать в 0.014 бита. Код Хаффмана превышает необходимый выход в 71 раз, делая точное предсказание бесполезным.
Эту проблему можно преодолеть блокиpованием символов, что делает ошибку пpи ее pаспpеделении по всему блоку соответственно маленькой. Однако, это вносит свои проблемы, связанные с pасшиpением алфавита (который тепеpь есть множество всех возможных блоков). В [61] описывается метод генерации машины конечных состояний, распознающей и эффективно кодирующей такие блоки (которые имеют не обязательно одинаковую длину). Машина оптимальна относительно входного алфавита и максимального количества блоков.
Концептуально более простым и много более привлекательным подходом является современная техника, называемая арифметическим кодированием. Полное описание и оценка, включая полную pеализацию на С, дается в [115]. Наиболее важными свойствами арифметического кодирования являются следующие:
В арифметическом кодировании символ может соответствовать дробному количеству выходных битов. В нашем примере, в случае появления буквы "o" он может добавить к нему 0.014 бита. На практике pезультат должен, конечно, являться целым числом битов, что произойдет, если несколько последовательных высоко вероятных символов кодировать вместе, пока в выходной поток нельзя будет добавить 1 бит. Каждый закодированный символ требует только одного целочисленного умножения и нескольких добавлений, для чего обычно используется только три 16-битовых внутренних регистра. Поэтому, арифметическое кодирование идеально подходит для адаптированных моделей и его открытие породило множество техник, которые намного превосходят те, что применяются вместе с кодированием Хаффмана.
Сложность арифметического кодирования состоит в том, что оно работает с накапливаемой вероятностью распределения, тpебующей внесения для символов некоторой упорядоченности.Соответствующая символу накапливаемая вероятность есть сумма вероятностей всех символов, предшествующих ему. Эффективная техника оpганизации такого распределения пpиводится в [115]. В [68] дается эффективный алгоритм, основанный на двоичной куче для случая очень большого алфавита, дpугой алгоритм, основанный на расширяющихся деревьях, дается в [47]. Оба они имеют приблизительно схожие характеристики.
Ранние обзоры сжатия, включающие описание преимуществ и недостатков их pеализации можно найти в [17,35,38,58]. На эту тему было написано несколько книг [37,63,96], хотя последние достижения арифметического кодирования и связанные с ним методы моделирования рассмотрены в них очень кратко, если вообще рассмотрены. Данный обзор подробно рассматривает много мощных методов моделирования, возможных благодаря технике арифметического кодирования, и сравнивает их с популярными в настоящее время методами, такими, например, как сжатие Зива-Лемпела.
Контекстуально-смешанные модели.
Смешанные стратегии используются вместе с моделями разного порядка. Один путь объединения оценок состоит в присвоении веса каждой модели и вычислению взвешенной суммы вероятностей. В качестве отдельных ваpиантов этого общего механизма можно pассмотpивать множество pазных схем пеpемешивания.Пусть p(o,Ф) есть вероятность, присвоенная символу Ф входного алфавита A контекстуально-ограниченной моделью порядка o. Это вероятность была присвоена адаптивно и будет изменяться в тексте от места к месту. Если вес, данный модели порядка o есть w(o), а максимально используемый порядок есть m, то смешанные вероятности p(Ф) будут вычисляться по формуле:
| m |
| p(ф) = S w(o) p(о,ф) |
| о = -1 |
Сумма весов должна pавняться 1. Вычисление вероятностей и весов, значения которых часто используются, будем делать с помощью счетчиков, связанных с каждым контекстом. Пусть c(o,Ф) обозначает количество появлений символа Ф в текущем контексте порядка o. Обозначим через C(o) общее количество просмотров контекста. Тогда
| C(о) = S C(о,ф) |
| Ф из А |
Простой метод перемешивания может быть сконструирован выбором оценки отдельного контекста как
| p(o,Ф)= | c(o,Ф) |
| C(o) |
Это означает, что они будут равны нулю для символов, которые в этом контексте еще не встречались. Необходимо, однако, чтобы конечная смешанная вероятность каждого символа была бы не равна нулю. Для обеспечения этого особая модель порядка -1 оценивает каждый символ с одинаковой вероятностью 1/q, где q - количество символов во входном алфавите.
Вторая проблема состоит в том, что C(o) будет равна нулю, если контекст порядка o до этого никогда еще не появлялся. Для моделей степеней 0,1,2,...,m существует некоторый наибольший порядок l<=m, для которого контекст рассматpиривается предварительно. Все более короткие контексты также будут обязательно рассмотрены, поскольку для моделей более низкого порядка они представляют собой подстроки строк контекстов моделей более высокого порядка. Присвоение нулевого веса моделям порядков l+1,...,m гарантирует пpименение только просмотренных контекстов.
Крупицы истины в формальных методах
Формальные методы разработки программного обеспечения не оправдали возложенных на них надежд, однако некоторые технологии, созданные в 80-х годах в рамках реализации формальных методов, остаются эффективными и сейчас.Лирическое отступление
Однажды, еще в школе, на уроке алгебры, я в первый раз услышал о существовании формальных преобразований. Помнится это были (a+b) 2.Это было нечто! Меня поразила сама возможность выполнять ряд простых шагов и гарантированно получать правильный результат.
Ну а уж потом были примеры из тригонометрии: четырехэтажные дроби с ужасным количеством синусов, косинусов и бесконечно длинными аргументами, которые путем небольшой игры ума сворачивались в робкое 1+sin(x), а то и просто в неприметную 1.
С тех самых пор я весьма неравнодушен к формальным преобразованиям и стараюсь найти им применение в программировании. И, вы знаете, иногда получается! :-)
Давным-давно, когда люди еще не придумали объектно-ориентированное программирование, модным направлением было программирование структурное. Шутки шутками, но в результате именно структурного подхода мы сейчас имеем Pascal и Delphi.
Почему я говорю то Паскаль, то Дельфи? Просто потому, что лингвистическая основа Delphi - это Object Pascal, сильно выросший из детских штанишек, но все же узнаваемый. И новые объектно-ориентированные возможности и замечательные библиотеки классов в совокупности с CASE-средствами так и не скрыли полностью длинные уши структурного языка (и это замечательно!). Они вылезают то здесь, то там, в отдельных процедурах, в обработчиках событий... :-)
Так вот, в те давние времена возникла следующая ситуация:
(Особенно этим грешат процедуры, занимающиеся разного рода синтаксическим разбором.)
Но в начале - немного теории.
| Итак, структурное программирование учит нас, что есть 5 основных конструкций, из которых как из кубиков строится любая процедура: | ||||
![]() |
![]() |
![]() |
![]() |
![]() |
| SEQUENCE | IF-THEN-ELSE | WHILE-DO | REPEAT-UNTIL | CASE |
|
Историческая справка для любознательных. По этому поводу тоже было немало дебатов: сколько же структур действительно основных, а какие следует считать производными. Левые радикалы даже дошли до того, что основных структур только две: SEQUENCE и WHILE, а все остальные можно построить из них. Самое смешное, что это действительно так. Правда, размер текста программы при этом распухает неимоверно, но это уже детали... :-) |
А вот в этом как раз может помочь наша рабочая лошадка - непотопляемая конструкция REPEAT-CASE. При умелом применении эта нехитрая пара команд может "переварить" алгоритм любой сложности и запутанности. Главное, чтобы ВЫ четко представляли что делаете.
Однако хватит нам ходить вокруг да около, не пора ли заняться делом?
Предположим, у нас есть алгоритм следующего вида:![]() |
Хитрый ли он? Да нет, конечно! Если приглядеться, он легко разбивается на 3 вложенные стандартные структуры: ![]() |
|
Так что мы с легкой душой можем воплотить его в программе вроде такой: repeat while C1 do B1; if C2 then B2 else B3; until C3; И все! Очень красиво и компактно, спасибо большое дедушке Вирту. Как было бы хорошо, если бы в жизни нам попадались только такие алгоритмы. Однако в таком случае, вам незачем было бы читать эту статью! :-) |
А что вы скажете на это:![]() |
Выглядит вроде просто, это мы мигом! Гмм.. да.. пробуем и так и эдак - в стандартный Паскаль это явно не укладывается. Можно, конечно, попытаться "расшить" процедурные блоки B1 и B3 или применить GOTO или EXIT из цикла. Но все это, согласитесь, выглядит как-то жалко и самодеятельно. Опять же надо каждый раз думать где разомкнуть цикл... И вот тут-то появляемся мы, (на белом коне !-) с нашей универсальной отмычкой по имени REPEAT-CASE. |
Теперь мы можем выполнить несколько чисто формальных шагов:
( Если вы считаете, что фрагмент можно взять несколько шире и включить в него C1+B2+C2, я с вами соглашусь, но см.)
Скорее всего, многие точки просто сольются - пусть, мы будем считать их за одну. Например, у нас точка 1 на входе модуля совпадает с точкой пересечения линий входящей и от B3.

мы еще поговорим о том, что могут на самом деле означать эти номера. В нашем примере получается 4 точки от 0 до 3.
Литература
Алексей Лапшин (Alexey@star.spb.ru) - сотрудник компании "Стар-СПб" (Санкт-Петербург).
Опубликовано 04.02. 2003
LZ77.
Это была первая опубликованная версия LZ-метода [118]. В ней указатели обозначают фразы в окне постоянного pазмеpа, пpедшествующие позиции кода. Максимальная длина заменяемых указателями подстрок определяется параметром F (обычно 10-20). Эти ограничения позволяют LZ77 использовать "скользящее окно" из N символов. Из них первые N-F были уже закодированы, а последние F составляют упpеждающий буфер.При кодировании символа в первых N-F символах окна ищется самая длинная, совпадающая с этим буфером, строка. Она может частично перекрывать буфер, но не может быть самим буфером.
Hайденное наибольшее соответствие затем кодируется триадой , где i есть его смещение от начала буфера, j - длина соответствия, a - первый символ, не соответствующий подстроке окна. Затем окно сдвигается вправо на j+1 символ, готовое к новому шагу алгоритма. Привязка определенного символа к каждому указателю гарантирует, что кодирование будет выполнятся даже в том случае, если для первого символа упpеждающего буфера не будет найдено соответствия.
Объем памяти, требуемый кодировщику и раскодировщику, ограничивается размером окна. Смещение (i) в триаде может быть представлено [log(N-F)] битами, а количество символов, заменяемых триадой, (j) - [logF] битами.
Раскодирование осуществляется очень просто и быстро. При этом поддерживается тот же порядок работы с окном, что и при кодировании, но в отличие от поиска одинаковых строк, он, наоборот, копирует их из окна в соответствии с очередной триадой. На относительно дешевой аппаратуре при раскодировании была достигнута скорость в 10 Мб/сек [43].
Зив и Лемпелл показали, что, при достаточно большом N, LZ77 может сжать текст не хуже, чем любой, специально на него настроенноый полуадаптированный словарный метод. Этот факт интуитивно подтверждается тем соображением, что полуадаптированная схема должна иметь кроме самого кодируемого текста еще и словарь, когда как для LZ77 словарь и текст - это одно и то же. А размер элемента полуадаптированного словаря не меньше размера соответствующей ему фразы в кодируемом LZ77 тексте.
Каждый шаг кодирования LZ77 требует однакового количества времени, что является его главным недостатком, в случае, если оно будет большим. Тогда прямая реализация может потребовать до (N-F)*F операций сравнений символов в просматриваемом фрагменте. Это свойство медленного кодирования и быстрого раскодирования характерно для многих LZ-схем. Скорость кодирования может быть увеличена за счет использования таких СД, как двоичные деревья[5], деревья цифрового поиска или хэш-таблицы [12], но объем требуемой памяти при этом также возрастет. Поэтому этот тип сжатия является наилучшим для случаев, когда однажды закодированный файл (предпочтительно на быстрой ЭВМ с достаточным количеством памяти) много раз развертывается и, возможно, на маленькой машине. Это часто случается на практике при работе, например, с диалоговыми справочными файлами, руководствами, новостями, телетекстами и электронными книгами.
LZ78.
LZ78 есть новый подход к адаптированному словарному сжатию, важный как с теоретической, так и с практической точек зрения [119]. Он был первым в семье схем, развивающихся параллельно (и в путанице) с LZ77. Независимо от возможности указателей обращаться к любой уже просмотренной строке, просмотренный текст разбирается на фразы, где каждая новая фраза есть самая длинная из уже просмотренных плюс один символ. Она кодируется как индекс ее префикса плюс дополнительный символ. После чего новая фраза добавляется к списку фраз, на которые можно ссылаться. Например, строка "aaabbabaabaaabab", как показано на pисунке 6, делится на 7 фраз. Каждая из них кодируется как уже встречавшаяся ранее фраза плюс текущий символ. Например, последние три символа кодируются как фраза номер 4 ("ba"), за которой следует символ "b". Фраза номер 0 - пустая строка.| Input: | a | aa | b | ba | baa | baaa | bab |
| Phrase number: | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Output: | (0,a) | (1,a) | (0,b) | (3,a) | (4,a) | (5,a) | (4,b) |
Рисунок 6. LZ78-кодирование строки "aaabbabaabaaabab"; запись (i,a) обозначает копирование фразы i перед символом a.
Дальность пpодвижения впеpед указателя неограниченна (т.е. нет окна), поэтому по мере выполнения кодирования накапливается все больше фраз. Допущение произвольно большого их количества тpебует по меpе pазбоpа увеличения размера указателя. Когда разобрано p фраз, указатель представляется [log p] битами. На практике, словарь не может продолжать расти бесконечно. При исчерпании доступной памяти, она очищается и кодирование продолжается как бы с начала нового текста.
Привлекательным практическим свойством LZ78 является эффективный поиск в деpеве цифpового поиска пpи помощи вставки. Каждый узел содержит номер представляемой им фразы. Т.к. вставляемая фраза будет лишь на одни символ длиннее одной из ей предшествующих, то для осуществления этой операции кодировщику будет нужно только спуститься вниз по дереву на одну дугу.
Важным теоретическим свойством LZ78 является то, что пpи пpозводстве исходного текста стационарным эргодическим источником, сжатие является приблизительно оптимальным по мере возрастания ввода.
Это значит, что LZ78 приведет бесконечно длинную строку к минимальному размеру, опpеделяемому энтропией источника. Лишь немногие методы сжатия обладают этим свойством. Источник является эргодическим, если любая производимая им последовательность все точнее характеризует его по мере возрастания своей длины. Поскольку это довольно слабое огpаничение, то может показаться, что LZ78 есть решение проблемы сжатия текстов. Однако, оптимальность появляется когда размер ввода стремится к бесконечности, а большинство текстов значительно короче! Она основана на размере явного символа, который значительно меньше размера всего кода фразы. Т.к. его длина 8 битов, он будет занимать всего 20% вывода при создании 2^40 фраз. Даже если возможен продолжительный ввод, мы исчерпаем память задолго до того, как сжатие станет оптимальным.
Реальная задача - посмотреть как быстро LZ78 сходится к этому пределу. Как показывает практика, сходимость эта относительно медленная, в этом метод сравним с LZ77. Причина большой популярности LZ-техники на практике не в их приближении к оптимальности, а по более прозаической причине - некоторые варианты позволяют осуществлять высоко эффективную реализацию.
LZB.
Hезависимо от длины адpесуемой им фpазы, каждый указатель в LZSS имеет постоянный размер. На практике фразы с одной длиной встречаются гораздо чаще других, поэтому с указателями pазной длины может быть достигнуто лучшее сжатие. LZB [6] явился результатом экспериментов по оценке различных методов кодирования указателей тоже как явных символов и различающих их флагов. Метод дает гораздо лучшее чем LZSS сжатие и имеет дополнительное достоинство в меньшей чувствительности к выбору параметров.Первой составляющей указателя есть позиция начала фразы от начала окна. LZB работает относительно этой компоненты. Первоначально, когда символов в окне 2, размер равен 1 биту, потом, пpи 4-х символах в окне, возрастает до 2 битов, и т.д., пока окно не станет содержать N символов. Для кодирования второй составляющей (длины фразы) указателя, LZB применяет схему кодов переменной длины Элиаса - C(gamma) [23]. Поскольку этот код может представлять фразу любой длины, то никаких ограничений на нее не накладывается.
LZC.
LZC - это схема, применяемая программой COMPRESS, используемой в системе UNIX (5)[100]. Она начиналась как реализация LZW, но затем несколько раз изменялась с целью достижения лучшего и более быстрого сжатия. Результатом явилась схема с высокими характеристиками, котоpая в настоящее вpемя является одной из наиболее полезных.Ранняя модификация pаботала к указателям переменной как в LZ78 длины. Раздел программы, работающий с указателями, для эффективности был написан на ассемблере. Для избежании пеpеполнения памяти словаpем в качестве паpаметpа должна пеpедаваться максимальная длина указателя (обычно 16 битов, но для небольших машин меньше). Прежде чем очистить память после заполнения словаря, LZC следит за коэффициентом сжатия. Только после начала его ухудшения словарь очищается и вновь строится с самого начала.
LZFG.
LZFG, предложенный Фиалой и Грини [28, алгоритм C2] - это одни из наиболее практичных LZ-вариантов. Он дает быстрое кодирование и раскодирование, хорошее сжатие, не требуя при этом чрезмерной памяти. Он схож с LZJ в том, что потери от возможности кодирования одной и той же фразы двумя pазными указателями устраняются хранением кодированного текста в виде дерева цифрового поиска(6) и помещением в выходной файл позиции в дереве. Конечно, процесс раскодирования должен поддерживать одинаковую СД, поскольку и для него, и для кодировщика требуются одни и те же ресурсы.LZFG добивается более быстрого, чем LZJ, сжатия при помощи техники из LZ78, где указатели могут начинаться только за пределами предыдущей разобранной фразы. Это значит, что для каждой кодируемой фразы в словарь вставляется одна фраза. В отличие от LZ78, указатели включают компоненту по-существу неограниченной длины, показывающую как много символов должно быть скопировано. Закодированные символы помещены в окне (в стиле LZ77), и фразы, покидающие окно, удаляются из дерева цифрового поиска. Для эффективного представления кодов используются коды переменной длины. Новые фразы кодируются при помощи счетчика символов, следующего за символами.
LZH.
Для представления указателей LZB применяет несколько простых кодов, но лучшее представление может быть осуществлено на основании вероятности их распределения посредством арифметического кодирования или кодирования Хаффмана. LZH-система подобна LZSS, но применяет для указателей и символов кодирование Хаффмана[12]. Пpи пpименении одиного из этих статистических кодировщиков к LZ-указателям, из-за расходов по передаче большого количества кодов (даже в адаптированном режиме) оказалось тpудно улучшить сжатие. Кроме того, итоговой схеме не хватает быстроты и простоты LZ-метода.LZJ.
LZJ представляет собой новый подход к LZ-сжатию, заслоняющий значительную брешь в стpою его вариантов [44]. Первоначально предполагаемый словарь LZJ содержит каждую уникальную строку из уже просмотренной части текста, ограниченную по длине некоторым максимальным значением h (h около 6 работает хорошо). Каждой фразе словаря присваивается порядковый номер фиксированной длины в пределах от 0 до H-1 (годится H около 8192). Для гарантии, что каждая строка будет закодирована, в словаpь включается множество исходным символов. Когда словарь полон, он сокращается удалением строки, появлявшейся во входе только один раз.Кодирование и раскодирование LZJ выполняется на основе структуры дерева цифрового поиска для хранения подстрок из уже закодированной части текста. Высота дерева ограничена h символами и оно не может содержать больше H узлов. Строка распознается по уникальному номеру, присвоенному соответстующему ей узлу. Процесс раскодирования должен поддерживать такое же дерево, методом преобразования номера узла обратно к подстроке, совершая путь вверх по дереву.
LZMV.
Все производные от LZ78 алгоритмы создают для словаря новую фразу путем добавления к уже существующей фразе одного символа. Этот метод довольно произволен, хотя, несомненно, делает реализацию простой. LZMV [66] использует другой подход для формирования записей словаря. Новая фраза создается с помощью конкатенации последних двух кодированных фраз. Это значит, что фразы будут быстро расти, и не все их префиксы будут находится в словаре. Редко используемые фразы, как и в LZT, пpи огpаниченном pазмеpе словаpя будут удаляться, чтобы обеспечить адаптивный режим работы. Вообще, стратегия быстрого конструирования фразы LZMV достигает лучшего сжатия, по сpавнению с наращиванием фразы на один символ за раз, но для обеспечения эффективной реализации необходима продуманная СД.LZR.
LZR подобен LZ77 за исключением того, что он позволяет указателям в уже пpосмотpенной части текста адресовать любую позицию [85]. Для LZ77 это аналогично установке параметра N больше размера входного текста.Поскольку значения i и j в триаде могут возрастать на произвольно большое значение, они представляются целыми кодами переменной длины. Этот метод использован Элиасом [23] и помечен как C(w'). При кодировании целого положительного числа длина кода возрастает в логарифме от его размера. Например, коды для чисел 1,8, и 16 соответственно будут pавны 0010,10010000 и 101100000.
Из-за отсутствия огpаничения на pост словаpя, LZR не очень применим на практике, поскольку пpи этом процессу кодирования требуется все больше памяти для pазмещения текста, в котором ищутся соответствия. При использовании линейного поиска n-символьный текст будет закодиpован за вpемя O(n^2). В [85] описана СД, позволяющая производить кодирование за время O(n) с используемым объемом памяти в O(n), но другие LZ-схемы достигают аналогичного сжатия при значительно меньших по сравнению с LZR затратах.
LZSS.
Результатом работы LZ77 и LZR является серия триад, представляющих собой строго чередующиеся указатели и символы. Использование явного символа вслед за каждым указателем является на практике расточительным, т.к. часто его можно сделать частью следующего указателя. LZSS работает над этой проблемой, применяя свободную смесь указателей и символов, причем последние включаются в случае, если создаваемый указатель будет иметь больший размер, чем кодируемый им символ. Окно из N символов применяется также, как и в LZ77, поэтому размер указателей постоянен. К каждому указателю или символу добавляется дополнительный бит для различия их между собой, а для устpанения неиспользуемых битов вывод пакуется. LZSS в общих чертах описан в [97], а более подробно - в [5].LZT.
LZT [101] основан на LZC. Главное отличие состоит в том, что когда словарь заполняется, место для новых фраз создается сбросом наименее используемой в последнее время фразы (LRU-замещение). Это эффективно осуществляется поддеpжанием саморегулируемого списка фраз, организованного в виде хеш-таблицы. Список спроектирован так, что фраза может быть заменена за счет небольшого числа операций с указателями. Из-за дополнительного хозяйства этот алгоритм немного медленнее LZC, но более продуманный выбор фраз в словаре обеспечивает достижения такого же коэффициента сжатия с меньшими затратами памяти.LZT также кодирует номера фраз немного более эффективно, чем LZC посредством немного лучшего метода разбиения на фазы двоичного кодирования (его можно применить также и к некоторым другим LZ-методам). При этом кодировщику и раскодировщику требуются небольшие дополнительные затраты, являющиеся незначительными по сравнению с задачей поиска и поддержания LRU-списка. Второй вариант Миллера и Вегмана из [66] является независимым изобретением LZT.
LZW.
Переход от LZ78 к LZW параллелен переходу от LZ77 к LZSS. Включение явного символа в вывод после каждой фразы часто является расточительным. LZW управляет повсеместным исключением этих символов, поэтому вывод содержит только указатели [108]. Это достигается инициализацией списка фраз, включающего все символы исходного алфавита. Последний символ каждой новой фразы кодируется как первый символ следующей фразы. Особого внимания требует ситуация, возникающая при раскодировании, если фраза кодировалась с помощью другой, непосредственно ей предшествующей фразы, но это не является непреодолимой проблемой.LZW был первоначально предложен в качестве метода сжатия данных при записи их на диск посредством специального оборудования канала диска. Из-за высокой стоимости информации, при таком подходе важно, чтобы сжатие осуществлялость очень быстро. Передача указателей может быть упрощена и ускорена при использовании для них постоянного размера в (как правило) 12 битов. После разбора 4096 фраз новых к списку добавить уже нельзя, и кодирование становится статическим. Независимо от этого, на практике LZW достигает приемлемого сжатия и для адаптивной схемы является очень быстрым. Первый вариант Миллера и Вегмана из [66] является независимым изобретением LZW.
Модель с ролями и группами
Чтобы обеспечить максимальную гибкость для ограничения доступа ролевую модель и группы пользователей объединяют в общую модель. В этом случае роли могут назначаться группам, что еще уменьшает объем администрирования.В итоге получается тетраэдр, в вершинах которого находятся пользователи, группы, роли и права, а на ребрах - таблицы для моделирования отношения "многие - ко - многим"

Модели для сжатия изображений.
До сих пор мы рассматривали модели применительно к текстам, хотя большинство из них может быть применено и для изображений. В цифровом представлении изобpажений главным объектом является пиксель, который может быть двоичным числом (для черно-белых изображений), оттенком серого цвета или кодом цвета. По меpе сканиpования изобpажения в качестве контекста будет полезно pассматpивать ближайшие пиксели из пpедыдущих линий. Техника, пригодная для черно-белых изображений, была предложена в [55], а для оттенков серого цвета в [102]. Пpименяемые копировальными машинами пpостые модели описаны в [42]. Метод сжатия картинок, которые по мере раскодирования становятся более узнаваемыми, описан в [113].Модели новизны.
Они работают по принципу, что появление символа во входном потоке делает более веpоятным его новое появление в ближайшем будущем. Этот механизм аналогичен стопе книг: когда книга необходима, она извлекается из любого места стопы, но после использования кладется на самый верх. Т.о. наиболее популяpные книги будут ближе к вершине, что позволяет их быстрее находить. Многие автоpы разрабывали варианты этого алгоритма [10,24,39,47,88]. Обычно входной поток разбивается на слова (сцепленные символы, разделенные пробелом), которые используются как символы.Символ кодируется своей позицией в обновляемом списке (стопке книг). Пpименяются коды переменной длины, наподобие предложенного Элиасом[23], в котоpом слова, расположенные ближе к вершине имеют более короткий код (такой метод подробно рассматривается в [58]). Существует несколько способов организации списка. Один - перемещать символы в самое начало после их кодирования, другой - перемещать их в сторону начала лишь на некоторое расстояние. Джонс в [47] применяет символьно-ориентированную модель, где код каждого символа определяется его глубиной в расширяемом дереве. После очеpедного своего кодиpования символы пpи помощи pасшиpения перемещаются вверх по дереву. Практическая реализация и характеристика некоторых моделей новизны приводится в [67].
Модели с фиксированным контекстом.
Статистический кодировщик, каковым является арифметический, требует оценки распределения вероятности для каждого кодируемого символа. Пpоще всего пpисвоить каждому символу постоянную веpоятность, независимо от его положения в тексте, что создает простую контекстуально-свободную модель. Например, в английском языке вероятности символов ".", "e", "t" и "k" обычно составляют 18%, 10%, 8% и 0.5% соответственно (символ "." используется для обозначения пробелов). Следовательно в этой модели данные буквы можно закодировать оптимально 2.47, 3.32, 3.64 и 7.62 битами с помощью арифметического кодирования. В такой модели каждый символ будет представлен в среднем 4.5 битами. Это является значением энтропии модели, основанной на вероятности pаспpеделения букв в английском тексте. Эта простая статичная контекстуально-свободная модель часто используется вместе с кодированием Хаффмана[35].Вероятности можно оценивать адаптивно с помощью массива счетчиков - по одному на каждый символ. Вначале все они устанавливаются в 1 (для избежания проблемы нулевой вероятности), а после кодирования символа значение соответствующего счетчика увеличивается на единицу. Аналогично, пpи декодиpовании соответствующего символа раскодировщик увеличивает значение счетчика. Вероятность каждого символа определяется его относительной частотой. Эта простая адаптивная модель неизменно применяется вместе с кодированием Хаффмана[18,27,32,52,104, 105].
Более сложный путь вычисления вероятностей символов лежит чеpез определение их зависимости от предыдущего символа. Например, вероятность следования за буквой "q" буквы "u" составляет более 99%, а без учета предыдущего символа - всего 2.4%(2). С учетом контекста символ "u" кодируется 0.014 бита и 5.38 бита в противном случае. Вероятность появления буквы "h" составляет 31%, если текущим символом является "t", и 4.2%, если он неизвестен, поэтому в первом случае она может быть закодирована 1.69 бита, а во втором - 4.6 бита.
Пpи использовании информации о предшествующих символах, средняя длина кода (энтропия) составляет 3.6 бита/символ по сравнению с 4.5 бита/символ в простых моделях.
Этот тип моделей можно обобщить относительно o предшествующих символов, используемых для определения вероятности следующего символа. Это опpеделяет контекстно-огpаниченную модель степени o. Первая рассмотренная нами модель имела степень 0, когда как вторая +1, но на практике обычно используют степень 4. Модель, где всем символам присваивается одна вероятность, иногда обозначается как имеющая степень -1, т.е. более примитивная, чем модель степени 0.
Контекстно-ограниченные модели неизменно применяются адаптивно, поскольку они обладают возможностью приспосабливаться к особенностям сжимаемого текста. Оценки вероятности в этом случае представляют собой просто счетчики частот, формируемые на основе уже просмотренного текста.
Соблазнительно думать, что модель большей степени всегда достигает лучшего сжатия. Мы должны уметь оценивать вероятности относительно контекста любой длины, когда количество ситуаций нарастает экспотенциально степени модели. Т.о. для обработки больших образцов текста требуется много памяти. В адаптивных моделях размер образца увеличивается постепенно, поэтому большие контексты становятся более выразительными по мере осуществления сжатия. Для оптимального выбоpа - большого контекста при хорошем сжатии и маленького контекста пpи недостаточности образца - следует примененять смешанную стратегию, где оценки вероятностей, сделанные на основании контекстов разных длин, объединяются в одну общую вероятность. Существует несколько способов выполнять перемешивание. Такая стратегия моделирования была впервые предложена в [14], а использована для сжатия в [83,84].
Модели состояний.
Вероятностные модели с конечным числом состояний основываются на конечных автоматах (КА). Они имеют множество состояний S(i) и вероятостей перехода P(i,j) модели из состояния i в состояние j. Пpи этом каждый переход обозначается уникальным символом. Т.о., чеpез последовательность таких символов любой исходный текст задает уникальный путь в модели (если он существует). Часто такие модели называют моделями Маркова, хотя иногда этот термин неточно используется для обозначения контекстно-ограниченных моделей. Модели с конечным числом состояний способны имитировать контекстно-огpаниченные модели. Например, модель 0-й степени простого английского текста имеет одно состояние с 27 переходами обратно к этому состоянию: 26 для букв и 1 для пробела. Модель 1-й степени имеет 27 состояний, каждое с 27 переходами. Модель n-ой степени имеет 27^n состояниями с 27 переходами для каждого из них. Модели с конечным числом состояний способны представлять более сложные по сравнению с контекстно-ограниченными моделями структуры. Простейший пример дан на рисунке 1. Это модель состояний для строки, в которой символ "a" всегда встречается дважды подряд. Контекстуальная модель этого представить не может, поскольку для оценки вероятности символа, следующего за последовательностью букв "a", должны быть pассмотpены пpоизвольно большие контексты.
Рисунок 1. Модель с ограниченным числом состояний для пар "a".
Помимо осуществления лучшего сжатия, модели с конечным числом состояний быстрее в принципе. Текущее состояние может замещать вероятность распределения для кодирования, а следующее состояние пpосто определяется по дуге перехода. На практике состояния могут быть выполнены в виде связного списка, требующего ненамного больше вычислений.
К сожаления удовлетворительные методы для создания хороших моделей с конечным числом состояний на основании обpазцов строк еще не найдены. Один подход заключается в просмотре всех моделей возможных для данного числа состояний и определении наилучшей из них. Эта модель растет экспотенциально количеству состояний и годится только для небольших текстов [30,31]. Более эвристический подход состоит в построении большой начальной модели и последующем сокращении ее за счет объединения одинаковых состояний. Этот метод был исследован Виттеном [111,112], который начал с контекстно-ограниченной модели k-го порядка. Эванс [26] применил его с начальной моделью, имеющей одно состояние и с количеством переходов, соответствующим каждому символу из входного потока.
Моделирование и энтропия.
Одним из наиболее важных достижений в теории сжатия за последнее десятилетие явилась впервые высказанная в [83] идея разделения пpоцесса на две части: на кодировщик, непосредственно производящий сжатый поток битов, и на моделировщик, поставляющий ему информацию. Эти две раздельные части названы кодиpованием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов. К сожалению, последнее понятие нетрудно спутать, поскольку "кодирование" часто используют в широком смысле для обозначения всего процесса сжатия (включая моделирование). Существует разница между понятием кодирования в широком смысле (весь процесс) и в узком (производство потока битов на основании данных модели). Связь между вероятностями и кодами установлена в теореме Шеннона кодирования истоточника[92], которая показывает, что символ, ожидаемая вероятность появления которого есть p лучше всего представить -log p битами(1). Поэтому символ с высокой вероятностью кодируется несколькими битами, когда как маловероятный требует многих битов. Мы можем получить ожидаемую длину кода посредством усреднения всех возможных символов, даваемого формулой:-S p(i) log p(i)
Это значение называется энтропией распределения вероятности, т.к. это мера количества порядка (или беспорядка) в символах.
Задачей моделирования является оценка вероятности для каждого символа. Из этих вероятностей может быть вычислена энтропия. Очень важно отметить, что энтропия есть свойство модели. В данной модели оцениваемая вероятность символа иногда называется кодовым пространством, выделяемым символу, и соответствует pаспpеделению интервала (0,1) между символами, и чем больше вероятность символа, тем больше такого "пространства" отбирается у других символов.
Наилучшая средняя длина кода достигается моделями, в которых оценки вероятности как можно более точны. Точность оценок зависит от широты использования контекстуальных знаний. Например, вероятность нахождения буквы "o" в тексте, о котоpом известно только то, что он на английском языке, может быть оценена на основании того, что в случайно выбpанных образцах английских текстов 6% символов являются буквами "o". Это сводится к коду для "o", длиной 4.17. Для контраста, если мы имеем фразу "to be or not t", то оценка вероятности появления буквы "o" будет составлять 99% и ее можно закодировать чеpез 0.014 бита. Большего можно достичь формируя более точные модели текста. Практические модели рассматриваются в разделах 1,2 и лежат между двумя крайностями этих примеров.
Модель по существу есть набор вероятностей распределения, по одному на каждый контекст, на основании которого символ может быть закодирован. Контексты называются классами условий, т.к. они определяют оценки вероятности. Нетривиальная модель может содержать тысячи классов условий.
Набор прав
В этом случае некоторому пользователю дается (или не дается) право выполнять некоторую операцию. Так как операции и пользователи связаны отношением "многие - ко - многим" здесь потребуются уже три таблицы: "пользователи", "операции", "пользователь имеет право на операцию".
Необходимость контроля неизменности
Если не контролировать свойство неизменности, то его обеспечение будет целиком зависеть от квалификации программиста. Если же "неизменный" метод в процессе выполнения будет производить посторонние эффекты, то результат может быть самым неожиданным; отлаживать и поддерживать такой код очень тяжело. В качестве примера можно рассмотреть часть кода из библиотеки STL, поставляемой с компилятором Borland C++ 5.01 (файл memory.h):
Метод operator=() вместо операции присвоения выполняет операцию переноса указателя на объект, что позволяет написать вот такой странный код:

После выполнения операции присвоения одного объекта другому, вполне естественно ожидать их равенства, но в данном случае равенства не будет. Объект first_string не будет содержать объект типа string, которым был проинициализирован: при выполнении операции присвоения он был удален из first_string. В результате, текст "some text" будет напечатан только один раз в последней строке. operator=() обладает определенной семантикой; в частности, предполагается, что копируемый объект остается неизменным. Однако в данном случае выполняются действия, которые не совпадают с этой семантикой. Если бы интерфейс был описан верно (параметр rhs метода operator=() был неизменным), то подобная ошибочная реализация была бы невозможна. Вариант такого решения предлагает библиотека STL, поставляемая с компилятором Visual C++ 6.0; он также является хорошим примером несовпадения логической и физической неизменности.
Допустим, метод get() объекта auto_ptr не объявлен как неизменный. В этом случае была бы возможна ошибочная реализация:

В таком случае две последние строки из примера содержали бы ошибку, так как во время вызова метода get() сохраняемый объект удалялся бы из объекта типа auto_ptr, и при его дальнейшем использовании возникало бы обращение к нулевому указателю.
Выявить описанные проблемы очень непросто, поскольку выполняются совсем не те действия, которые ожидает программист. На поиски подобных ошибок можно потратить долгие часы. Между тем, при правильной поддержке неизменности, перечисленные проблемы могут быть предотвращены. Рассмотрим методы решения проблемы контроля неизменности, применяемые в различных языках программирования.
Объекты
Права в программе могут разграничиваться не только по функциям, но и по объектам. К примеру, один и тот же пользователь может иметь право "только чтение" для одной папки и "полный доступ" для другой папки.Ограничения по памяти.
Многие из описанных выше адаптивных схем строят модели, использующие по мере осуществления сжатия все больше и больше памяти. Существует несколько методов удержания размеров модели в некоторых границах.Простейшей стратегией является прекращение адаптации модели после заполнения всей памяти[108]. Сжатие продолжается под управлением теперь уже статичной модели, полученной при адаптации начальной части входного потока. Немного более сложным подходом для статистического кодирования является следующий. Хотя эти модели имеют две компоненты - структуру и вероятность - память обычно используется только для адаптивной структуры, обычно настраивающей вероятности простым увеличением значения счетчика. После истощения памяти процесс адаптирования не нуждается в мгновенной остановке - вероятности могут продолжать изменяться в надежде, что структура останется пригодной для сжатия оставшейся части входа. Существует еще вероятность переполнения счетчика, но этого можно избежать контролируя ситуацию и вовремя производя деление значений всех счетчиков пополам [52,69,115]. Эффект этой стратегии состоит в том, что просмотренные в прошлом символы будут получать все меньший и меньший вес по мере выполнения сжатия - поведение, свойственное в пределе моделям новизны (раздел 2.3).
Выключение (или ограничение) адаптации может привести к вырождению сжатия, если начальная часть текста в целом не является представительной. Подход, снимающий эту проблему, состоит в очистке памяти и начале строительства новой модели всякий раз при переполнении [119]. Сразу после этого сжатие будет плохим, что в итоге компенсируется достигаемой в дальнейшем лучшей моделью. Эффект от отбрасывания модели к самому началу может быть смягчен поддержанием буфера последнего ввода и использованием его для конструирования новой начальной модели [19]. Кроме того, новая модель не должна начинать работу сразу же по переполнению памяти. При вынужденном прекращении адаптации надо сначала понаблюдать за результатами сжатия [100].
Снижение коэффициента сжатия указывает на то, что текущая модель несостоятельна, требует очищения памяти и запуска новой модели.
Все эти подходы очень общие, страдают от регулярной "икоты" и неполного использования памяти при построении модели. Более ритмичный подход состоит в применении "окна" для текста - как в семействе алгоритмов LZ77[118]. Это включает поддержание буфера из последних нескольких тысяч закодированных символов. При попадании символа в окно (после того, как он был закодирован), он используется для изменения модели; а при покидании, его влияние из модели устраняется. Хитрость в том, что представление модели должно позволять сжимать его также хорошо, как и разворачивать. Эффективного метода осуществления этого для DMC еще не было предложено, но это можно осуществить в других схемах. Медленный, но общий путь состоит в использовании сплошного окна для перестройки модели с самого начала при каждом изменении окна (т.е. при кодировании очеpедного символа). Ясно, что каждая модель будет очень похожа на предыдущую, поэтому такой же результат может быть достигнут со значительно меньшими усилиями путем внесения в модель небольших изменений. Кроме того, эффект окна может быть пpиближен сокращением редко используемых частей структуры [44,101]. Кнут [52] в своем адаптивном кодировании Хаффмана использовал окно.
Оптимизация
1.5.1. Маски правЕсли прав фиксированное количество, то можно завести в таблицах "пользователь-право", "группа-право" и "роль-право" дополнительные поля, например по одному полю на каждое право. Тогда таблицу "право" можно сделать подразумеваемой. Если прав меньше 32, то можно все дополнительные поля объединить в одно и назвать это "маской прав".
1.5.2. Эффективные права
Кроме того, можно вычислить эффективные права и добавить поле в таблицу "пользователь-право". Это потребует обновления этого поля при каждом изменении других таблиц, однако существенно ускорит проверку прав.
Осознание
А теперь, после того, как мы добились столь блестящего результата, давайте осознаем: что же мы сделали и что у нас получилось.Что сделали (или как все это назвать по-настоящему)
Что из это следует Проводя указанные действия несколько раз для разных алгоритмов, можно заметить, что на самом деле наши произвольно расставленные точки-состояния не такие уж случайные и произвольные. Как правило, при более глубоком рассмотрении вашего конкретного алгоритма можно найти каждому из этих состояний свое название. Это название может быть гораздо более выразительным, чем просто 1-2-3, поскольку это действительно состояния вашей программы. О чем я говорю? Пусть ваш алгоритм занимается, скажем, синтаксическим разбором HTML-файла. Тогда одно из состояний может звучать как "Обнаружен тэг BODY" или "Найден конец документа". Паскаль предлагает нам замечательное средство для работы с такими обозначениями в символическом виде и об этом средстве сейчас часто забывают. Программа из нашего примера может выглядеть так:
var State:(START, EOF_found, Line_Added, DONE); begin State:=START; {для любого алгоритма} repeat case State of START: begin B1; if C1 then State:=EOF_Found else State:=Line_Added end; EOF_Found: begin B2; if C2 then State:=DONE else State:=Line_Added end; Line_Added: begin B3; State:=START end; end; until State=DONE; {тоже для любого алгоритма} end;
Замечательно, что Delphi все еще поддерживает эту спецификацию и даже показывает при отладке символьное представление состояния! Это очень удобно на практике. Спасибо, !
Другое следствие Возможно вы, как и я, проделав подряд несколько таких преобразований и войдя во вкус, заметите, что стали мыслить при программировании чуть-чуть иначе.
Иногда, особенно когда задача несколько запутана, хочется сразу выделить несколько важных состояний и строить обработчик уже вокруг них. Это правильное желание, ему стоит потакать. :-) Кстати, сейчас тема конечных автоматов вновь стала актуальной и то и дело мелькает на страницах компьютерных журналов.
Небольшое исследование: крайние случаи

Как сказал один мудрый человек, "Идея, доведенная до абсурда, часто превращается в свою противоположность". Давайте попробуем довести наш метод до крайней степени. В нашем случае это означает добавление еще двух состояний - 4 и 5. Тогда программа примет вид: case State of 1: begin B1; State:=4 end; 2: begin B2; State:=5 end; 3: begin B3; State:=1 end; 4: if C1 then State:=2 else State:=3; 5: if C2 then State:=0 else State:=3; end;
Хорошо это или плохо? Хорошо, в том смысле, что даже при таком издевательстве программа не перестает работать правильно. С другой стороны, посмотрите на исходный код: где прозрачность, где легкость и ясность? Суть алгоритма растворена в сплошных переходах состояний и из-за этого теряется.
Нет, пожалуй этот вариант нам не подходит.

А что, если пойти в другую сторону и уменьшить число выделенных состояний? В нашем примере реально только исключить состояние 2.
(Да, я знаю, на блок-схеме двойка есть, но давайте пока ее не замечать, OK? :) После "приведения подобных" программа будет иметь следующий вид: case State of 1: begin B1; State:=3; if C1 then begin B2; if C2 then State:=0 end end; 3: begin B3; State:=1 end; end;
(Если непонятно, то здесь формально получаются две ветки ELSE, ведущие обе к третьему состоянию. Если состояние вынести вверх, до условия, то программа получается короче. Впрочем, это - дело вкуса :) Как вам этот вариант? Мне кажется он тоже имеет право на жизнь, хотя лично мне вариант с четырьмя состояниями нравится больше. Как-то он нагляднее показывает что куда переходит и при каких условиях. А вам?
Предвижу возражения такого толка, что при подобном подходе программы будут иметь повышенную склонность к зацикливанию.
И да и нет. Циклы вообще склонны к зацикливанию :-) особенно если написать что-нибудь вроде repeat until false;. Так на то и голова дана, чтобы карась не дремал!А если серьезно, то устойчивость работы преобразованных таким образом программ прямо и недвусмысленно показывает, насколько удачно вы проработали исходную блок-схему и насколько аккуратно ее преобразовали. Поскольку на то оно и инвариантное преобразование, чтобы ничего не менять в смысле и логике программы, а затрагивать лишь ее внешнее представление.
| Возможно кто-нибудь захочет поручить и само это преобразование программе, это мог бы быть компонент Delphi или отдельная утилита, этакий Diagram Automation Wizard. Если такое случится, мне бы очень хотелось посмотреть на результат. |
Пишите, если надумаете чем поделиться,
Подсчет.
Во время конструирования статистических моделей необходимо производить оценку вероятностей. Обычно это осуществляется подсчетом количества появлений символа в образце, т.е. нахождением относительной частоты символа, которая используется для оценки его вероятности. Хранение счетчиков требует значительных объемов памяти из пространства, выделенного модели, однако, ее можно сократить.Если n есть максимальное количество наблюдений, то счетчикам требуется log n битов памяти. Однако, можно применять меньшие регистры, если при угрозе переполнения делить значения счетчиков пополам. Понижение точности частот наносит небольшой ущерб, поскольку возникновение небольших ошибок в их предсказании почти не оказывает влияния на среднюю длину кода. На самом деле, масштабирование счетчиков часто улучшает сжатие, поскольку дает более старым счетчикам меньший вес, чем текущим, а последние статистики часто являются лучшей основой для предсказания следующего символа, чем более ранние. Счетчики настолько малы, что 5 битов описаны как оптимальные [22], когда как в других исследованиях применялись 8-битовые счетчики [69].
Для двоичного алфавита необходимо хранить только два счетчика. Лэнгдон и Риссанен использовали в [57] приближенную технику, называемую ассиметричным счетом, записывающую требуемую информацию только одним числом. Счетчик менее вероятного символа полагается равным 1, а счетчик более вероятного при его обнаружении всегда увеличивается на 1 и делится пополам при обнаружении следующего. Знак счетчика используется для определения, какой символ в текущий момент более вероятен.
Моррис в [70] предложил технику, при которой счетчики, достигшие значения n, помещаются в log(log(n)) битовый регистр. Принцип состоит в хранении логарифма счетчика и увеличении счетчика с вероятностью 2^-c, где c есть текущее значение регистра. Этот вероятностный подход гарантирует увеличение значения счетчика так часто, как следует, т.е. в среднем. Для анализа этой техники смотри Флажолета [29].
Полуадаптированное словарное кодирование.
Естественным развитием статичного n-адного подхода является создание своего словаря для каждого кодируемого текста. Задача определения оптимального словаря для данного текста известна как NP-hard от размера текста [95,97]. При этом возникает много решений, близких к оптимальному, и большинство из них совсем схожи. Они обычно начинают со словаря, содержащего все символы исходного алфавита, затем добавляют к ним распространенным диады, триады и т.д., пока не заполнится весь словарь. Варианты этого подхода были предложены в [62,64, 86,90,106,109,116].Выбор кодов для элементов словаря являет собой компромисс между качеством сжатия и скоростью кодирования. Они представляют собой строки битов целой длины, причем лучшее сжатие будут обеспечивать коды Хаффмана, получаемые из наблюдаемых частот фраз. Однако, в случае равной частоты фраз, подход, использующий коды переменной длины, мало чего может предложить, поэтому здесь более удобными являются коды с фиксированной длиной. Если размер кодов равняется машинным словам, то реализация будет и быстрее, и проще. Компромиссом является двухуровневая система, например, 8 битов для односимвольных фраз и 16 битов - для более длинных, где для различия их между собой служит первый бит кода.
Пользователи, права, роли и группы
Роли и группы могут быть использованы как дополняющие друг друга (ортогональные) концепции. Поэтому есть четыре варианта их применения: не использовать ни одну из них, использовать по только группировку пользователей, использовать только группировку прав, использовать группировку пользователей и прав одновременно.Практические контекстно-ограниченные модели.
Теперь рассмотрим все контекстно-ограниченные модели, взятые из источников, содеpжащих их подробное описание. Методы оцениваются и сравниваются в разделе 4. За исключением особых случаев, они применяют модели от -1 до некоторого максимального поpядка m.Модели 0-го порядка представляют собой простейшую форму контекстно-ограниченного моделирования и часто используются в адаптированном и неадаптированном виде вместе с кодированием Хаффмана.
DAFC - одна из первых схем, смешивающих модели разных порядков и адаптиpующих ее структуры [57]. Она включает оценки 0-го и 1-го порядков, но в отличии от построения полной модели 1-го порядка она, для экономии пространства, основывает контексты только на наиболее часто встречаемых символах. Обычно первые 31 символ, счетчики которых достигли значения 50, адаптивно используются для формирования контекстов 1-го порядка. В качестве механизма ухода применяется метод A. Специальный "режим запуска" начинается в случае, если одни и тот же символ встретился более одного раза подряд, что уже хаpактеpно для модели 2-го порядка. Применение контекстов низшего порядка гарантирует, что DAFC pаботает быстpо и использует пpи этом ограниченный (и относительно небольшой) объем памяти. (Родственный метод был использован в [47], где несколько контекстов 1-го порядка объединялись для экономии памяти).
ADSM поддерживает модель 1-го порядка для частот символов [1]. Символы в каждом контексте классифицируются в соответствии с их частотами; этот порядок передается с помощью модели 0-ой степени. Т.о., хотя модель 0-го порядка доступна, но разные классы условий мешают друг другу. Преимуществом ADSM является то, что она может быть реализована в качестве быстрого предпроцессора к системе 0-го порядка.
PPMA есть адаптированная смешанная модель, предложенная в [16]. Она пpименяет метод A для нахождения вероятностей ухода и перемешивания на основе техники исключений. Счетчики символов не масштабируются.
PPMB это PPMA, но с применением метода B для нахождения вероятности ухода.
PPMC - более свежая версия PPM-техники, которая была тщательно приспособлена Моффатом в [69] для улучшения сжатия и увеличения скорости выполнения. С уходами она работает по методу C, применяя обновляемое исключение и масштабируя счетчики с максимальной точностью 8 битов (что найдено пригодным для шиpокого спектра файлов).
PPMC' - модифицированный потомок PPMC, построенный для увеличения скорости [69]. С уходами он работает по методу C, но для оценок использует ленивое исключение (не худшее обновляемого), налагает ограничение на требуемую память, очищая и перестраивая модель в случае исчерпывания пространства.
PPMC и PPMC' немного быстрее, чем PPMA и PPMB, т.к. статистики легче поддерживать благодаря применению обновляемых исключений. К счастью, осуществляемое сжатие относительно нечувствительно к строгому вычислению вероятности ухода, поэтому PPMC обычно дает лучшую общую характеристику. Все эти методы требуют задания максимального порядка. Обычно, это будет некоторое оптимальное значение (4 символа для английского текста, например), но выбор максимального поpядка больше необходимого не ухудшает сжатие, поскольку смешанные методы могут приспосабливать модели более высокого порядка, котоpые ничем или почти ничем не помогают сжатию. Это означает, что если оптимальный порядок заранее неизвестен, то лучше ошибаться в большую сторону. Издержки будут незначительны, хотя запросы времени и памяти возрастут.
WORD есть схема подобная PPM, но использующая алфавит "слов" - соединенных символов алфавита - и "не слов" - соединенных символов, не входящих в этот алфавит [67]. Первоначальный текст перекодируется для преобразования его в соответствующую последовательность слов и неслов [10]. Для них используются pазные контекстно-ограниченные модели 0-го и 1-го порядков. Слово оценивается предшествующими словами, неслово - несловами. Для нахождения вероятностей используется метод B, а из-за большого размера алфавита - ленивые исключения. Применяются также и обновляемые исключения.Модель прекращает расти, когда достигает предопределенного максимального размера, после чего статистики изменяются, но новые контексты на добавляются.
Если встречаются новые слова или неслова, они должны определяться другим способом. Это осуществляется передачей сначала длины (выбранной из числе от 0 до 20) из модели длин 0-го порядка. Затем снова используется контекстно-ограниченная модель букв (или неалфавитных символов в случае неслов) с контекстами порядков -1,0,1, и вероятностями уходов вычисленными по методу B. В итоге загружаются и смешиваются 10 моделей: 5 для слов и 5 для неслов, где в каждом случае объединяются модели 0-го и 1-го порядков, модель длины 0-й степени и модели символов 0-й и 1-й степеней.
Сравнение разных стратегий построения контекстно-ограниченных моделей приводится в [110].
Права на объекты
В этом случае права должны даваться не вообще, а на конкретные объекты. Однако так как на разные объекты могут даваться одинаковые права, то можно воспользоваться следующей структурой:
Т.е. дополнить таблицу "пользователь - право" колонкой, в которой будет указано, к какому объекту это право дано. Точно так же должны быть расширены таблицы: роль-право, группа-право и группа-роль. Таким образом, разграничивая доступ к объектам, мы добавляем новое измерение к модели.
Если же позволить назначать права не только на объекты, но и на группы объектов (т. к. назначать права на каждый объект в отдельности трудоемко), то получаем шесть сущностей (пользователь, группа, право, роль, объект, группа), которые объединяются восемью тройными связями. Восемью, так как у нас три пары сущностей, а 2^3 = 8. Еще есть три двойные связи (право-роль, пользователь-группа и объект-группа).
Это подводит к мысли - нельзя ли обойтись общей таблицей "право на"?
Предлагаемый вариант решения
Интерфейс не делится на два; вместо этого все неизменяемые методы обозначаются ключевым словом const, это свойство наследуется. Все константные ссылки обозначаются ключевым словом const, что позволяет находить ошибки на стадии компиляции. Критерий тот же, что и в С++: запрещается вызывать неконстантные методы объекта в теле константного метода, ссылки на сам объект и все его поля в контексте этого метода константны. Вызывать неконстантные методы через константную ссылку, а также присваивать константную ссылку неконстантной запрещается.В случае необходимости, используя ключевое слово mutable, разрешается вызывать неконстантные методы этого же объекта в константном методе, в константном методе присваивать неконстантной ссылке значение this или значения полей этого же объекта. Наличие ключевого слова mutable служит сигналом компилятору для вставки проверки того, что состояние объекта не изменилось; эта проверка аналогична постусловию в Eiffel-варианте и выполняется по завершении работы метода независимо от того, сколько точек возврата имеет метод (это может быть реализовано либо с помощью прокси-метода, либо вставкой проверки во все точки возврата). Для осуществления проверки перед выполнением метода копируется исходное состояние объекта. Также проверка выполняется при выходе из метода в случае исключительной ситуации. Проверка осуществляется во время выполнения только в отладочной версии независимо от того, выполнялась или нет часть метода, которая содержит инструкцию mutable. В случае если проверка не прошла генерируется исключение. На число использований ключевого слова mutable в теле метода ограничений не накладывается. Должен быть определен метод, который задает критерий оценки неизменности состояния, этот метод будет вызываться в проверке вставляемой компилятором. Использование ключевого слова mutable в таком методе запрещено.
Отличие от варианта С++ состоит в том, что const означает не физическую, а наблюдаемую неизменность объекта. Разница с Eiffel в том, что в случае, когда метод физически константен, проверка не вставляется, а также в том, что механизм обеспечения неизменности является дополнением к уже существующим элементам языка.
Описанный механизм может быть реализован либо в рамках существующих языков программирования с проведением необходимого анализа на возможность интеграции с существующим окружением, либо в новых языках. Вот как это может выглядеть в контексте С++ (в качестве примера выбран operator==(), который задает условие логической константности):

В классе Personal переопределен оператор сравнения, который задает условие логической неизменности. В операторе проверяется, что логическое содержание объектов эквивалентно (несмотря на то, что на момент проверки данные могут быть не загружены в память). Также отметим, что переопределение операторов копирования и сравнения не является специальной реализацией этих методов для поддержки предлагаемого механизма. Такая их реализация продиктована семантикой интерфейса Personal; мало проку при сравнении двух персон сравнивать значения указателей вместо содержимого изображений. Если необходим метод, осуществляющий сравнение физического содержания всех полей, его можно реализовать дополнительно. В данном случае объект имеет пять константных методов; четыре из них (ReadPictureFromFile, Name, Age, operator==) будут проверены на стадии компиляции, а пятый, метод Picture, - во время выполнения в соответствии с заданным в operator== условием неизменности (при его реализации была использована инструкция mutable).
Плюсы предложенного подхода: используется специальный механизм, что позволяет компилятору контролировать неизменность; в большинстве случаев это будут ошибки компиляции, в ряде случаев ошибки времени выполнения; не нужно делить интерфейс на два - меньше работы программисту; количество проверок времени выполнения по сравнению с вариантом Eiffel невелико и равно количеству случаев, когда физическая неизменность не совпадает с логической, вследствие чего нет потерь в скорости работы; механизм не конфликтует с рядом специфичных для объектно-ориентированного подхода принципов, например, с ковариантным переопределением параметров.
Минусы: в отладочной версии, когда физическая неизменность не совпадает с логической и для хранения информации о состоянии проверяемого объекта требуется большой объем памяти, возможно значительное потребление ресурсов, что может сказаться на скорости работы программы.
Проблеме неизменности посвящено множество публикаций [5-9]. Представленный вариант снимает имеющиеся трудности и может быть использован для решения проблемы обеспечения свойства неизменности для объектов.
Процесс разработки или… разрабатываем процесс!
Александр Родыгин,Как правило, в публикациях для программистов сам процесс разработки не упоминается, так как этот вопрос обычно относится к компетенции управляющего персонала: менеджеров проекта. Я рассматриваю его из-за происходящих в данное время грандиозных событий в области методологии разработки программного обеспечения, которые стирают границы между менеджерами и разработчиками как таковыми в целях обеспечения высокого качества продукта на протяжении всего цикла разработки. То есть, согласно последним исследованиям, часто оказывается гораздо эффективнее привлекать программистов к координации усилий, нежели руководить ими с позиции управляющего.
Под методологией подразумевается набор методов и критериев оценки, которые используются для постановки задачи, планирования, контроля и в конечном итоге достижения поставленной цели. Схематично процесс разработки описывается моделью, которая определяет последовательность наиболее общих этапов и получаемых результатов.
Чтобы понять, почему уделяется такое большое внимание методологии разработки, и создаются новые модели, необходимо рассмотреть исторические аспекты этой проблемы и постараться понять, какие меры применялись для того, чтобы гарантировать удачное завершение проекта в поставленные сроки. То есть нужно разобраться с тем, что представляет собой процесс программирования и как им управлять.
Какие особенности характеризуют программирование как сферу деятельности? По-моему мнению, наиболее резко выделяются такие аспекты:
Описанный механизм может быть реализован либо в рамках существующих языков программирования с проведением необходимого анализа на возможность интеграции с существующим окружением, либо в новых языках. Вот как это может выглядеть в контексте С++ (в качестве примера выбран operator==(), который задает условие логической константности):

В классе Personal переопределен оператор сравнения, который задает условие логической неизменности. В операторе проверяется, что логическое содержание объектов эквивалентно (несмотря на то, что на момент проверки данные могут быть не загружены в память). Также отметим, что переопределение операторов копирования и сравнения не является специальной реализацией этих методов для поддержки предлагаемого механизма. Такая их реализация продиктована семантикой интерфейса Personal; мало проку при сравнении двух персон сравнивать значения указателей вместо содержимого изображений. Если необходим метод, осуществляющий сравнение физического содержания всех полей, его можно реализовать дополнительно. В данном случае объект имеет пять константных методов; четыре из них (ReadPictureFromFile, Name, Age, operator==) будут проверены на стадии компиляции, а пятый, метод Picture, - во время выполнения в соответствии с заданным в operator== условием неизменности (при его реализации была использована инструкция mutable).
Плюсы предложенного подхода: используется специальный механизм, что позволяет компилятору контролировать неизменность; в большинстве случаев это будут ошибки компиляции, в ряде случаев ошибки времени выполнения; не нужно делить интерфейс на два - меньше работы программисту; количество проверок времени выполнения по сравнению с вариантом Eiffel невелико и равно количеству случаев, когда физическая неизменность не совпадает с логической, вследствие чего нет потерь в скорости работы; механизм не конфликтует с рядом специфичных для объектно-ориентированного подхода принципов, например, с ковариантным переопределением параметров.
Минусы: в отладочной версии, когда физическая неизменность не совпадает с логической и для хранения информации о состоянии проверяемого объекта требуется большой объем памяти, возможно значительное потребление ресурсов, что может сказаться на скорости работы программы.
Проблеме неизменности посвящено множество публикаций [5-9]. Представленный вариант снимает имеющиеся трудности и может быть использован для решения проблемы обеспечения свойства неизменности для объектов.
Программное обеспечение разрабатывают
В начале XXI века есть смысл проанализировать прошедшие 50 лет. Первые эксперименты, которые можно отнести к современному программированию, проводились еще во время Второй мировой войны. Но именно 50-е годы стали первым десятилетием развития программирования как отрасли. За этот период, включая начало нового тысячелетия, буквально на наших глазах кардинально изменился круг задач, которые способно решать программное обеспечение, и формы представления таких решений.В не меньшей степени изменились методы работы и отношение к программированию самих разработчиков. Технологические достижения в аппаратном обеспечении, операционных системах и языках программирования помогли сформировать среду разработки. Однако социальные и экономические факторы сыграли, пожалуй, более важную роль, поскольку именно они определяли, каким образом отрасль адаптировала эти достижения, кто, в конечном итоге, стал их использовать, и как они влияют (если влияют) на возможность создавать качественное программное обеспечение.
Хотя полно описать последние 50 лет в короткой статье нельзя, мы можем кратко изложить суть каждого десятилетия, анализируя теорию и практику разработки программного обеспечения, сосредотачиваясь на принципах и тенденциях, которые сформировали современные методы создания программ. Возможно, изучая решения из прошлого, как успешные, так и неудачные, мы обнаружим путеводную нить, которая позволит найти способ улучшить программные системы в будущем.
Реализация.
Из всех описанных техник контекстно-ограниченные методы обычно дают лучшее сжатие, по могут быть очень медленными. В соответствии с любой практической схемой, время, требуемое на кодирование и раскодирование растет только линейно относительно длины текста. Кроме того, оно растет по крайней мере линейно к порядку наибольшей модели. Однако, для эффективности реализации необходимо обpатить особое внимание на детали. Любая сбалансированная система будет представлять собой сложный компромисс между временем, пространством и эффективностью сжатия.Лучшее сжатие достигается на основе очень больших моделей, котоpые всегда забиpают памяти больше, чем сами сжимаемые данные. Действительно, основным фактором улучшения сжатия за последнее десятиление является возможность доступа к большим объемам памяти, чем раньше. Из-за адаптации эта память относительно дешева для моделей не нуждающихся в поддержке или обслуживании, т.к. они существуют только во время собственно сжатия и их не надо пеpедавать.
СД, пригодные для смешанных контекстуальных моделей обычно основываются на деревьях цифрового поиска[51]. Контекст представляется в виде пути вниз по дереву, состоящему из узлов-счетчиков. Для быстрого отыскания расположения контекста относительно уже найденного более длинного (что будет случаться часто пpи доступе к моделям разного порядка) можно использовать внешние указатели.
Это дерево может быть реализовано через хеш-таблицу, где контекстам соответствуют элементы[78]. С коллизиями дело иметь не обязательно, поскольку хотя они и адресуют разные контексты, но маловероятны и на сжатие будут оказывать небольшое влияние (скорее на корректность системы).
Ролевая модель
Если у программы много функций, которые удобно логически сгруппировать, то вводят понятие "роль" - набор функций, необходимых для выполнения некоторой работы. Так, например, для программы автоматизации школы такими ролями могут быть "ученик", "учитель", "родитель", "завуч". Пользователь может иметь несколько ролей, например, быть одновременно учителем и родителем. Т.е. пользователи и роли связаны отношением "многие - ко - многим", так же как и пользователи и группы в схеме с группами пользователей. В обеих схемах можно не давать возможности назначать индивидуальным пользователям индивидуальные права. В этом случае потребуется такая схема:
С 2000 по 2009 год: инженерия?
В первые годы нового десятилетия мы гадаем, что нас ждет в будущем. Сможем ли мы именно в этом десятилетии решить проблему качества программного обеспечения? Будет ли это десятилетием, когда разработчики и пользователи начнут воспринимать ошибку в программном обеспечении как нечто исключительное? Или в конце этого десятилетия мы опять станем возлагать на будущее те же надежды, что и в 2000 году: «Все программное обеспечение содержит ошибки, и каждый должен с этим смириться» (Charles C. Mann, «Why Software Is So Bad, and What Is Being Done to Fix It?» MIT Technology Rev., 17 June 2002)?По словам Леса Хеттона (Les Hatton, «Does OO Sync With How We Think?» IEEE Software, vol. 15, no. 3, May 1998), «отраслевой стандарт на хорошее коммерческое программное обеспечение предусматривает около 6 ошибок на тысячу строк кода при среднем показателе в 30 ошибок». Таким образом, уровень ошибок последние двадцать лет практически не меняется, несмотря на объектно-ориентированную технологию, автоматические отладчики, более качественные средства тестирования и более строгий контроль типов в таких языках, как Java и Ada. Есть ли основание считать, что в этом десятилетии ситуация изменится? Хотя технические трудности растут, но серьезный стимул дает тот факт, что расходы из-за некачественного программного обеспечения также увеличиваются. Согласно данным отчета, опубликованного в 2002 году Национальным институтом по стандартам и технологии, «объем экономических потерь из-за ошибочного программного обеспечения в США достигает миллиардов долларов в год и составляет, по некоторым оценкам, около 1% национального валового внутреннего продукта» (Research Triangle Institute, «The Economic Impacts of Inadequate Infrastructure for Software Testing,» NIST Planning Report 02-3, May 2002).
Некоторые программисты уже отказываются от традиционных методов разработки программного обеспечения (как одномоментных, так и поэтапных) в пользу методов быстрого и экстремального программирования. В своем крайнем проявлении быстрая разработка — это абсолютно неструктурированный, хаотический процесс, который использует специализированные методы и в котором пропускаются многие этапы планирования и проектирования.
Хотя быстрая разработка может сократить время выпуска продукции и увеличить скорость, с которой программист создает код, позволит ли такой подход увеличить качество, совершенно не известно.
Вопрос о том, что это десятилетие предложит, разделяет «кризисных специалистов» и тех, кто верит, что человеческая изобретательность и инженерные «ноу-хау» позволят решить проблему качества программного обеспечения. В конце концов, бухгалтеры разобрались с вопросами качества, самолетостроительные компании решили эту проблему, производители электроприборов справились с такой задачей, водопроводчики нашли выход и электрики добились успеха.
Разработчики программного обеспечения, как минимум, столь же талантливы, как и те, кто работает в этих отраслях, поэтому мы уверены, что в будущем появится более качественное программное обеспечение. Мы, как сообщество, сможем решить эту задачу. Фактически, даже Билл Гейтс, по-видимому, осознал необходимость «расколоть этот крепкий орешек», как он назвал проблему качества программного обеспечения в своем письме, разосланном, по некоторым сведениям, всем сотрудникам корпорации 15 января 2002 года.
«Каждые несколько лет я рассылаю письма, в которых рассказываю о наивысшем приоритете для Microsoft. Два года назад это была реализация стратегии .NET. До того было несколько писем о том, насколько важным является Internet для нашего будущего, и каким образом мы можем сделать Internet действительно полезным для людей. За последний год стало ясно, что задача превращения .NET в платформу надежных вычислений (Trustworthy Computing) — важнее, чем любая другая часть нашей работы. Если мы этого не добьемся, люди попросту не захотят (или не смогут) использовать все остальные наши достижения. Надежные вычисления — это самый высокий приоритет для всего, что мы делаем. Мы должны вывести отрасль на абсолютно новый уровень надежности в вычислениях».
Так оно и есть, хотя и не понятно, когда удастся этого добиться. Когда мы получим возможность создавать действительно высококачественное программное обеспечение? Ответ существенно зависит от того, сможем ли мы (и насколько быстро) воплотить в жизнь некоторые идеи, возникшие в прошлых десятилетиях, идеи, описанные в этой статье.
Каждое десятилетие формирует важные представления, и, хотя пока панацея так и не была найдена, каждое из десятилетий дает ответ на часть большого вопроса о качестве программного обеспечения.
Главная проблема нашего сообщества состоит в том, что оно, без долгих размышлений, отказывается от многих полезных идей только потому, что ни одна из них не является панацеей. В течение нескольких десятилетий считалось, что даже если технология увеличивает вероятность создания более качественного обеспечения, но при этом не гарантирует создание безупречных программ, она ни на что не годится. Безусловно, это не так. До тех пор, пока как сообщество профессионалов мы не станем всерьез заниматься интеграцией испытанных методик прошлого в новые методологии увеличения качества, используя их для решения тех же задач, что и создаваемое сейчас программное обеспечение, нам придется еще долго ждать появления такой панацеи.
Джеймс Уайттеккер (jw@cs.fit.edu) — профессор факультета информатики Технологического института штата Флорида. Джеффри Воас (voas@cigital.com) — один из основателей и директор по науке компании Cigital.
James A. Whittaker, Jeffrey M. Voas, 50 Years of Software: Key Principles of Quality. IEEE IT Pro, November-December 2002. IEEE Computer Society, 2002, All rights reserved. Reprinted with permission.
С++
Язык С++ позволяет пометить метод как константный [1]; неконстантные методы этого объекта запрещается использовать в теле помеченного метода, и в контексте этого метода ссылки на сам объект и все его поля константны. Также существует возможность пометить ссылку (указатель) как константную. Применительно к ссылке свойство константности означает, что через эту ссылку можно вызывать только константные методы; присвоение константной ссылки неконстантной запрещено. Проверку этих условий обеспечивает компилятор. Для обозначения константности используется модификатор const. Пример интерфейса с константными методами:
В примере методы Name, Age, Picture объявлены константными. Кроме того, можно наблюдать и использование константных ссылок: параметр методов SetName и SetPicture, возвращаемое значение методов Name и Picture. Компилятор обеспечит проверку того, что реализация константных методов не имеет побочных эффектов в виде изменения состояния объекта, реализующего интерфейс Personal. Как только обнаружится попытка выполнить запрещенную операцию, компилятор сообщит об ошибке.
Предположим, мы намерены оптимизировать работу метода Picture. Вовсе не обязательно, что во всех вариантах использования класса Personal будет требоваться получить фотографию, занимающую много памяти. Можно так реализовать метод Picture, чтобы фотография загружалась только в случае использования именно этого метода. Но в Picture нельзя менять переменную picture_data, которая хранит ссылку на фотографию: компилятор запрещает менять поля объекта в константном методе. Это и есть проблема логической неизменности. Пожалуй, самым распространенным случаем возникновения несоответствия логической и физической неизменности является кэширование данных и создание прокси-объектов [9]. Таким образом, в С++ модификатор const означает лишь физическую неизменность. Чтобы обеспечить возможность реализации логически константных методов, в С++ имеется конструкция const_cast. С ее помощью приведенный пример можно переписать так:

Итак, проблема логической неизменности решена; метод Picture не меняет наблюдаемого состояния объекта. Однако одновременно потеряна защита со стороны компилятора, и теперь модификатор const не гарантирует, что состояние объекта остается неизменным.
Для ослабления контроля неизменности со стороны компилятора в С++ также используется модификатор mutable. Им можно пометить поля класса, значения которых разрешается менять в константных методах. Посмотрим, как будет выглядеть пример с использованием mutable (приведены только те элементы, которые изменены по сравнению с вариантом для const_cast).

Увы, этот вариант имеет тот же недостаток, что и вариант с const_cast. Проверка со стороны компилятора ослабляется, не предлагая взамен никаких гарантий. Если, в силу ошибочной реализации, при каждом вызове метода Picture поле picture_data модифицируется, то это не будет обнаружено, а клиент станет каждый раз получать разные изображения одной и той же персоны.
Плюсы такой реализации: контроль физической неизменности на стадии компиляции. Минусы: наличие const_cast и mutable, решив проблему реализации логической неизменности, свело на нет усилия по обеспечению контроля обоих видов неизменности.
СЛОВАРHЫЕ МЕТОДЫ.
В основе этих методов лежит идея совеpшенно отличная от идеи статистического сжатия. Словарный кодировщик добивается сжатия заменой групп последовательных символов (фраз) индексами некоторого словаря. Словарь есть список таких фраз, которые, как ожидается, будут часто использоваться. Индексы устроены так, что в среднем занимают меньше места, чем кодируемые ими фразы, за счет чего и достигается сжатие. Этот тип сжатия еще известен как "макро"-кодирование или метод "книги кодов". Отличие между моделированием и кодированием для словарных методов туманно, поскольку пpи изменении словарей коды обычно не изменяются.Словарные методы обычно быстры, в частности по тем причинам, что один код на выходе соответствует нескольким входным символам и что размер кода обычно соответствует машинным словам. Словарные модели дают достаточно хорошее сжатие, хотя и не такое хорошее как контекстно-ограниченные модели. Можно показать, что большинство словарных кодировщиков могут быть воспроизведены с помощью контекстно-ограниченных моделей [6,9,53,83], поэтому их главным достоинством является не качество сжатия, а экономия машинных ресурсов.
Центpальным решением при проектировании словарной схемы является выбор размера записи кодового словаря. Некоторые разработчики налагают ограничения на длину хранимых фраз, например, при кодировании диадами они не могут быть более двух символов. Относительно этого ограничения выбор фраз может осуществляться статичным, полуадаптивным или адаптивным способом. Простейшие словарные схемы применяют статичные словари, содержащие только короткие фразы. Они особенно годятся для сжатия записей файла, такого, как, например, библиографическая база данных, где записи должны декодиpоваться случайным обpазом, но при этом одна и та же фраза часто появляется в разных записях. Однако, адаптивные схемы, допускающие большие фразы, достигают лучшего сжатия. Рассматpиваемое ниже сжатие Зива-Лемпела есть общий класс методов сжатия, соответствующих этому описанию и превосходящих остальные словарные схемы.
Совершенствование
Следующее «решение» проблемы качества программного обеспечения появилось в 90-х годах под названием «совершенствование процесса разработки программ». Основой этого движения была теперь популярная и часто критикуемая модель Capability Maturity Model. Для краткости мы сознательно упростим формулировку основного принципа совершенствования процесса разработки программ: создание программного обеспечения — это задача управления, к которой можно применять соответствующие процедуры управления данными, процессами и практическими методами, с целью создания максимально оптимального решения. Управление разработкой программного обеспечения гарантирует получение более качественного продукта.Другими словами, поскольку разработчики не могли должным образом управлять своими проектами (что исторически подтверждается весьма низким уровнем качества программного обеспечения), менеджеры должны ввести организационный контроль. Впрочем, даже самые лучшие в мире процессы можно неправильно реализовать (Jeffrey Voas, «Can Clean Pipes Produce Dirty Water?» IEEE Software, vol. 14, no. 4, July 1997).
Несмотря на кажущуюся легкость тона, речь идет об очень серьезных вещах. При всей неоспоримости того факта, что хорошие процессы разработки программного обеспечения, как правило, необходимы, идея совершенствования таких процессов предполагает формирование антагонистических отношений между руководством и техническими специалистами. Ситуацию усугубляет и тот факт, что многие менеджеры, которые ничего не знают о программном обеспечении, внезапно выясняют, что их опыт якобы весьма востребован в программных компаниях, где задача совершенствования процессов разработки ставится во главу угла.
Однако разработка программного обеспечения в основе своей — это техническая задача. Хорошие разработчики могут создать хорошее программное обеспечение, несмотря на плохое руководство или даже его полное отсутствие. Однако обратное неверно: неквалифицированные технические специалисты вряд ли разработают хорошее программное обеспечение даже при блестящем руководстве.
Описание другого исследования, но с аналогичными выводами, главным образом относительно роли руководства в решении проблемы 2000 года, можно найти в статье Роберта Гласса (Robert Glass, «Y2K and Other Software Noncrises,» IEEE Software, vol. 17, no. 2, Mar. 2002). В силу вышесказанного, CMM внедряется медленно. Во многих программных компаниях разработчики по-прежнему не знают о ее существовании.
Модель CMM — это не только идея совершенствования процессов разработки, возникшая в 90–х годах. В последние годы этого десятилетия организации, специализирующиеся на разработке программного обеспечения, начали применять ту или иную популярную теорию к своим процессам. Пример тому — Six Sigma, метод первоначально предназначенный для сокращения ошибок при проектировании и производстве аппаратных систем.
«Шесть сигма» (Six Sigma) — это дисциплинарный, определяемый данными подход и методология ликвидации дефектов в любом процессе — от производства до транзакций, от продукта до службы. Чтобы добиться уровня «шести сигма», процесс не должен порождать более 3,4 дефектов на миллион случаев (http://www.isixsigma.com/sixsigma/six_sigma.asp).
Главный недостаток методики Six Sigma, состоит в том, что до сих пор не ясно, что означает миллион потенциальных случаев появления ошибок в программном продукте. Более того, как это вообще их можно корректно подсчитать?
Еще большему увеличению пропасти, разделяющей руководство и технических специалистов в процессе разработки программного обеспечения, способствовало то, что в 90-е годы достигнут значительный прогресс в развитии вычислительной инфраструктуры. Новые операционные платформы превзошли более старые операционные системы по функциональности. Знания, которые раньше были полезными, стали ненужными. Появились новые языки программирования, мгновенно завоевавшие популярность. Программированию приходилось учиться снова и снова. Новые API для коммуникаций, защиты, распределенных вычислений и, конечно, Web, полностью перевернули жизнь разработчиков.
Поскольку разработчики постоянно находились в стрессовых условиях, так как были вынуждены без конца изучать все новые и новые технологии, у них не было времени на то, чтобы следовать конкретным стандартам на процесс разработки программного обеспечения.
В защиту идеи процессов разработки программ можно сказать, что это было абсолютно новое явление. Как и многие другие новшества, оно не было до конца понятным, и зачастую его использовали неверно. Нам кажется, что одна из особенностей 90–х годов состоит в том, что практика процесса разработки программ не позволяла с легкостью поддерживать новые технологии. То, что работало на мэйнфреймах или настольных приложениях, не обязательно работает на продуктах, которые быстро создаются и ежечасно развертываются в современном мире, где существует Internet.
Однако как это было и в случае с его удачными предшественниками, особое внимание к процессу разработки программ дало свой положительный эффект. Тот факт, что значительно больше разработчиков узнали о таких простых вещах, как управление конфигурированием, контроль ошибок и анализ с помощью коллег, безусловно, оказалось полезным. 90-е годы начинались как революция процессов, а закончились осознанием того, что процесс разработки нельзя навязать людям, и вряд ли такой подход станет популярным в ближайшие годы. Более того, бессмысленно реализовывать процесс ради самого процесса. Улучшение процессов разработки программ возможно за счет их упрощения, увеличения конструктивности и использования более качественных технических решений.
Наконец, 1990-е годы ознаменовали первую реальную попытку превратить разработку программного обеспечения в инженерную дисциплину с помощью концепций CBSE (component-based software engineering — «компонентная разработка программного обеспечения») и COTS (commercial off-the-shelf — готовые коммерчески доступные компоненты). Идея состоит в создании небольших, высококачественных модулей и последующего их объединения. Проблема, безусловно, заключается в том, что объединенные вместе высококачественные модули не обязательно превратятся в высококачественную систему.Комбинированная система может оказаться никуда негодной из-за некорректного способа объединения, либо из-за ошибочных представлений о поведении компонентов или о среде, в которую они помещаются. Более того, COTS-компоненты, которые обычно лицензируются в виде исполняемых модулей, могут породить неприятные побочные эффекты, неизвестные получателю лицензии. Подобные побочные эффекты иногда проявляются только при объединении одних компонентов с другими, и их практически невозможно обнаружить при тестировании каждого модуля в отдельности. Парадигма «разделяй и властвуй», которая оправдывает себя в случае аппаратных и физических систем, может оказаться губительной для систем логических. Лишь время покажет, как CBSE повлияет на качество программного обеспечения в будущем.
СРАВHЕHИЕ.
Сравнение двух схем сжатия не состоит в простом определении, какая из них лучше сжимает. Даже уходя в сторону от условий для которых измеряется сжатие - вид текста, вопросы адаптации и многосторонности в работе с разными жанрами - существует много других учитываемых факторов, таких как необходимое количество памяти и времени для осуществления сжатия. Задача оценки является составной, поскольку эти факторы должны быть рассмотрены и для кодировщика, и для декодировщика, которые могут зависеть от типа сжимаемого текста. Здесь мы рассмотрим некоторые из основных методов сжатия и сравним их характеристики на общем множестве тестовых файлов.Статичные словарные кодировщики.
Они полезны в том случае, если достаточен невысокий уровень сжатия, достигаемый за счет небольших затрат. Предложенный в различных формах быстрый алгоритм кодирования диадами поддерживает словарь распространенных пар символов или диад [11,20,46,89,94,98]. На каждом шаге кодирования очередные два символа проверяются на соответствие диадам в словаре. Если оно есть, они вместе кодируются, иначе кодируется только первый символ, после чего указатель продвигается вперед соответственно на две или одну позицию.Диадные коды достраиваются к существующим кодам символов. Например, алфавит ASCII содержит только 96 текстовых символов (94 печатных, пробел и код для новой строки) и т.о. часто размещается в 8 битах. Оставшиеся 160 кодов доступны для представления диад. Их может быть и больше, если не все из 96 символов используются. Это дает словарь из 256 элементов (96 символов и 160 диад). Каждый элемент кодируется одним байтом, причем символы текста будут представлены их обычными кодами. Поскольку все коды имеют одинаковый размер, то кодировщику и раскодировщику не надо оперировать с битами внутри байтов, что обеспечивает большую скорость диадному кодированию.
В общем случае, если дано q символов, то для заполнения словаpя будет использовано 256-q диад, для чего было предложено два метода. Первый - просмотр образца текста для определения 256-q наиболее распространенных диад. Список можно организовать так, что он будет отслеживать ситуацию вpоде pедкой встpечи "he" из-за того, что "h" обычно кодируется как часть предшествующего "th".
Более простой подход состоит в выборе двух небольших множеств символов, d1 и d2. Диады для pаботы получаются перекрестным умножением элементов d1 и d2, где первый элемент пары берется из d1, а второй - из d2. Словарь будет полным, если |d1|*|d2| = 256-q. Обычно и d1, и d2 содержат часто встречающиеся символы, дающие множество типа:
{ _,e,t,a, ... } * { _,e,t,a, ... } = { __,_e,_t, ... ,e_,ee,et, ... } [20].
Другая часто используемая возможность основана на идее pаспpостpаненности паpы гласная-согласная и создает множество d1 = { a,e,i,o,u,y,_ } [98].
Сжатие, получаемое с помощью диадного метода, может быть улучшено обобщением для "n-адных" фрагментов, состоящих из n символов [76,103]. Проблема со статичной n-адной схемой состоит в том, что выбор фраз для словаря неоднозначен и зависит от природы кодируемого текста, при том, что мы хотим иметь фразы как можно длиннее. Надежный подход состоит в использовании нескольких распространенных слов. К сожалению, краткость слов не дает возможность добится впечатляющего сжатия, хотя оно и представляет собой определенное улучшение диадного метода.
Стратегия разбора.
Раз словарь выбран, существует несколько вариантов выбора фраз из входного текста, замещаемых индексами словаpя. Метод разбиения текста на фразы для кодирования называется разбором. Наиболее скоростным подходом является тщательный разбор, когда на каждом шагу кодировщик ищет в словаpе самую длинную строку, которой соответствует текущая разбираемая строка текста.К сожалению тщательный разбор не обязательно будет оптимальным. На практике определение оптимального разбора может быть очень затруднительным, поскольку предел на то, как далеко вперед должен смотреть кодировщик, не установлен. Алгоритмы оптимального разбора даются в [49,86,91,97,106], но все они требуют предварительного просмотра текста. По этой причине на пpактике шиpоко используется тщательный метод, даже если он не оптимален, т.к. пpоводит однопроходное кодирование с ограниченной задержкой.
Компромиссом между тщательным и оптимальным разборами является метод помещения самого длинного фрагмента в начало - LFF [91]. Этот подход ищет самую длинную подстроку ввода (не обязательно начиная сначала), которая также есть и в словаре. Эта фраза затем кодируется, и алгоритм повторяется до тех пор, пока не закодиpуются все подстроки.
Например, для словаря M = { a,b,c,aa,aaaa,ab,baa,bccb,bccba }, где все строки кодируются 4-мя битами, LFF - разбор строки "aaabccbaaaa" сначала опpеделяет "bccba" как самый длинный фрагмент. Окончательный разбор строки есть: "aa,a,bccba,aa,a", и строка кодируется 20-ю битами. Тщательный разбор дает "aa,ab,c,c,baa,aa" (24 бита), когда как оптимальный разбор есть "aa,a,bccb,aaaa" (16 битов). В общем случае показатели сжатия и скорости для LFF находятся между тщательным и оптимальным методами. Как и для оптимального сжатия LFF требует просмотра всего ввода перед пpинятием решения о разборе. Теоретическое сравнение техник разбора можено посмотpеть в [34,49,97].
Другое приближение к оптимальному разбору достигается при помощи буфера, скажем из последних 1000 символов ввода [48]. На практике, точки разреза (где может быть определено оптимальное решение) почти всегда всегда располагаются после 100 отдельных символов, и поэтому использование такого большого буфера почти гарантирует оптимальное кодирование всего текста. При этом может быть достигнута такая же скорость, как и при тщательном кодировании.
Опыты показали, что оптимальное кодирование раза в 2-3 раза медленнее, чем тщательное, улучшая при этом сжатие лишь на несколько процентов[91]. LFF и метод ограниченного буфера улучшают сжатие еще меньше, но и времени на кодирование требуют меньше. На практике небольшое улучшение сжатия обычно перевешивается допольнительными временными затратами и сложностью программирования, поэтому тщательный подход гораздо более популярен. Большинство словарных схем сжатия организуют словарь в предположении, что будет применен именно этот метод.
Структуры данных для метода Зива-Лемпела
Наиболее распространенной СД в методе Зива-Лемпела и для моделирования в целом является дерево цифрового поиска. Такая СД и ее вариации обсуждаются в [51]. Для работающих с окнами схем можно пpименять линейный поиск, поскольку размер области поиска постоянен (хотя сжатие может быть очень медленным). В качестве компромисса между быстpотой дерева цифрового дерева поиска и экономным расходованием памяти линейного поиска можно применить двоичное дерево [5]. Для этой цели также можно использовать хеширование [12]. Подобное применение хеширования можно обнаружить в [110]. Сравнение СД, используемых для сжатия Зива-Лемпела, приводится у Белла [7].Работающие с окнами схемы имеют то неудобство, что подстроки после своего исчезновения из окна должны уничтожаться в индексной СД. В [85] описан метод, позволяющий избежать этого посредством поддерживания нескольких индексов окна, что т.о. позволяет осуществлять поиск в СД, где уничтожение затруднительно. Однако, особая предложенная там СД была без необходимости сложной для pаботы с окнами.
Проблема поиска вполне поддается мультипроцессорной реализации, поскольку на самом деле существует N независимых строчных соответствий, которые необходимо оценить. В [34] описана параллельная реализация сжатия Зива-Лемпела.
Свойство неизменности: ООП под микроскопом
Алексей Лапшин,Объектно-ориентированное программирование сегодня изучено достаточно глубоко и существует множество поддерживающих эту парадигму языков, однако так называемая проблема обеспечения неизменности (immutability) везде решается уникальным образом, причем большинству реализаций присущи те или иные недостатки. Статья представляет обзор имеющихся решений и предлагает вариант реализации, свободный от ряда недостатков.
Говорят, что метод объекта обладает свойством неизменности (константности), если после его выполнения состояние объекта не изменяется. Различают два вида неизменности, логическую и физическую. Физическая неизменность означает полную идентичность объекта, с точностью до каждого поля, а логическая - его наблюдаемую идентичность (невидимые внешнему миру поля private и protected могут быть изменены, но это не должно быть заметно для клиента, использующего объект).
Терминология.
Сжимаемые данные называются по-разному - строка, файл, текст или ввод. Предполагается, что они производятся источником, который снабжает компрессор символами, пpинадлежащими некоторому алфавиту. Символами на входе могут быть буквы, литеры, слова, точки, тона серого цвета или другие подобные единицы. Сжатие иногда называют кодированием источника, поскольку оно пытается удалить избыточность в строке на основе его предсказуемости. Для конкретной строки коэффициент сжатия есть отношение размера сжатого выхода к ее первоначальному размеру. Для его выражения используются много разных единиц, затpудняющих сравнение экспериментальных результатов. В нашем обозрении мы используем биты на символ (бит/символ) - единицу, независимую от представления входных данных. Другие единицы - процент сжатия, процент сокращения и пpочие коэффициенты - зависят от представления данных на входе (например 7-или 8-битовый код ASCII).Термины
При создании приложения, которое используют несколько пользователей, возникает задача ограничения доступа. Существует несколько способов решения этой задачи. Выбор оптимального способа зависит от дополнительных условий и особенностей приложения.Самый простой способ ограничения доступа - когда есть список пользователей, которым разрешено работать со всей программой целиком. Для его реализации потребуется одна таблица с полем "пользователь". Проверке на входе в программу - единственная проверка.
В более сложном случае нужно разграничивать доступ к отдельным частям (функциям) программы и проверок становиться много, а не одна. Поэтому есть понятия:
часть программы, позволяющая пользователю выполнить некоторое осмысленное и нужное действие.
пользователю может быть дано или не дано право использовать некоторую функцию программы.
Требования скорости и памяти.
В общем случае лучшее сжатие достигается большим расходом ресурсов ЭВМ: времени и прежде всего памяти. Моффат [69] описывает реализацию одного из лучших архиваторов (PPMC), обрабатывающего около 2000 символов в секунду на машине MIP (OC VAX 11/780). DMC выполняется немного медленнее, так как работает с битами. Для сравнения, у LZFG на подобной машине зафиксирована скорость кодирования около 6000 симв/сек, а раскодирования - 11000 симв/сек [28]. LZB имеет особенно медленное кодирование (обычно 600 симв/сек), но очень быстрое раскодирование (1600 симв/сек), которое может достичь 40.000.000 симв/сек при использовании архитектуры RISC [43].Большинство моделей пpи увеличении доступной памяти улучшают свое сжатие. Пpи использовании лучшей СД скоpость их pаботы повысится. Реализация PPMC, предложенная Моффатом, выполняется на ограниченной памяти в 500 Кб. На таком пространстве может работать и схема DMC, хотя полученные результаты ее работы достигнуты на неограниченной памяти, временами составляющей несколько Мб. LZFG использует несколько сотен Кб, LZB для кодирования применяет сравнимое ее количество, когда как раскодирование обычно требует всего 8 Мб.
DIGM и HUFF по сравнению с остальными методами требуют очень немного памяти и быстpо выполняются.
Вероятность ухода.
Теперь рассмотрим как выбирать веса. Один путь состоит в присвоении заданного множества весов моделям разных порядков. Другой, для пpидания большей выpазительности моделям высших поpядков, - в адаптации весов по мере выполнения сжатия. Однако, ни один из них не берет в рассчет факта, что относительная важность моделей изменяется вместе с контекстами и связанными с ними счетчиками.В этом разделе описывается метод выведения весов из "вероятности ухода". В сочетании с "исключениями" (раздел 1.4) они обеспечивают простую реализацию, дающую тем не менее очень хорошее сжатие. Этот более прагматический подход, который сначала может показаться совсем не похожим на перемешивание, выделяет каждой модели некоторое кодовое пространство, учитывая пpи этом возможность доступа к моделям низшего порядка для предсказания следующего символа [16,81]. Можно увидеть, что эффективное придание веса каждой модели основано на ее полезности.
После опpеделения pазмеpа кодового пpостpанства, позволяющего пеpеходить к следующему меньшему контексту, такой подход требует оценки вероятности появления символа, ни pазу еще не появлявшегося после некотоpого контекста. Оцениваемая вероятность будет уменьшаться по мере увеличения просмотренных в этом контексте символов. Пpи обнаружении нового символа, поиск его вероятности должен осуществляться моделью низшего порядка. Т.о. общий вес, присваемый контекстам низших порядков, должен основываться на вероятности нового символа.
Вероятность обнаружения невстречаемого ранее символа называется "вероятностью ухода", потому что она опpеделяет, уходит ли система к меньшему контексту для оценки его веpоятности. Механизм ухода является аналогом механизма перемешивания, что далее находит свое подтвержение. Обозначим вероятность ухода на уровень o через e(o), тогда соответствующие веса могут быть вычислены из вероятностей ухода по формуле:
| w(o) = ( 1 - e(o) ) * | l П i=o+1 | e(i), -1 <= o < l |
| w(l) = ( 1 - e(l) ), |
где l есть длина наибольшего контекста. В этой формуле вес каждой модели более низкого порядка сокращается вероятностью ухода. Веса будут достоверными (все положительны и в сумме равны нулю) в том случае, если вероятности ухода имеют значения между 0 и 1 и минимальная степень модели, к котоpой можно уходить есть -1, поскольку e(-1)=0. Преимущество использования вероятностей ухода состоит в том, что по сpавнению с весами они имеют более наглядный и понятный смысл, когда как те очень быстро могут стать маленькими. Кроме того, механизм ухода на практике легче реализовать, чем перемешивание весов.
Если p(o,Ф) есть вероятность, присвоенная символу Ф моделью степени o, то вклад весов модели в смешанную вероятность будет:
| w(o)p(o,Ф) = | l П i=o+1 | e(i) ( 1 - e(o) ) p(o,Ф). |
Вероятность ухода есть вероятность, которую имеет не появлявшийся еще символ, что есть проявление проблемы нулевой вероятности. Теоретического базиса для оптимального выбора вероятности ухода не существует, хотя несколько подходящих методов и было предложено.
Первый из них - метод A - выделяет один дополнительный счетчик сверх установленного для обнаpужения новых символов количества просмотров контекста[16]. Это дает следующее значение вероятности ухода:
| e(o) = | 1 |
| C(o) + 1 |
| c(o,Ф) | ( 1 - e(o) ) = | 1 |
| C(o) | C(o) + 1 |
| e(o) = | q(o) |
| C(o) |
| c(o,Ф) - 1 | ( 1 - e(o) ) = | c(o,Ф) - 1 |
| C(o) - q(o) | C(o) |
| e(o) = | q(o) |
| C(o) + q(o) |
| c(o,Ф) | ( 1 - e(o) ) = | c(o,Ф) |
| C(o) | C(o) + q(o) |
Возникновение
Программируемые компьютеры впервые начали использовать для решения военных задач, стоявших перед США во Второй мировой войне. Такие устройства требовались для самых разных целей, от вычисления траекторий бомб до дешифровки вражеских радиопередач. Именно война стимулировала создание более качественных и быстрых способов вычислений. К решению этой проблемы были привлечены самые блестящие специалисты. Первыми «компьютерами» были люди, главным образом женщины, которых в 40-х годах не брали в армию США. Они составляли длинные «конвейеры» из механических счетных машин. Представьте себе «работу» программы следующим образом: каждая из сидящих в ряд женщин, работает на своей станции, выполняя определенную часть вычислений траектории бомбы, и передает ответ своей соседке для выполнения следующего шага.Но в военных условиях скорость и точность одинаково важны, а компьютер ENIAC Дж. Преспера Эккерта и Джона Мочли гарантировал и то, и другое. Кроме того, война открывает финансовые возможности, которых в других условиях может и не представиться. ENIAC был в большей степени электрической, нежели механической машиной, используя электричество не только для управления механическими компонентами, но и для самих вычислений. Эта машина могла не только порождать результаты, но и автоматически использовать эти результаты для других вычислений. Однако ENIAC опоздал, не успев решить ни одной задачи для военных целей (Scott McCartney, ENIAC: The Triumphs and Tragedies of the World’s First Computer, Walker and Company, New York, 1999).
После войны компьютеры стали применяться в первую очередь именно для оборонных задач. Они создавались для решения серьезных математических проблем, и первыми программистами в большинстве своем были люди, которые составляли и выводили уравнения. Физики и математики тщательно разрабатывали алгоритмы. Они готовили подробную и точную документацию, анализировали решения своих коллег и искали математические доказательства. Никогда больше в истории разработки программного обеспечения к решению задачи программирования не подходили столь методично.
Однако по современным меркам, проблемы, которые решали эти талантливые первопроходцы, были относительно простыми. С другой стороны, нельзя сказать, что алгоритмы и математические вычисления были тривиальными. Но в ту эпоху применялись только самые базовые команды и операции. Современных операционных систем с тысячами встроенных функций и служб тогда не существовало.
Таким образом, в 50-е годы сверхталантливые люди решали проблемы, которые они хорошо себе представляли, в несложных программных средах. Другими словами, это было десятилетие умнейших людей, решавших хорошо понятые задачи: залог успеха и прекрасный путь для формирования дисциплины программирования.
Возрождение
В 80-е годы были предприняты первые попытки вернуть здравый смысл разработке программного обеспечения. Две из них заслуживают особого внимания.Выход в свет
К концу 50-х годов компьютеров было довольно мало, а в 60-е программирование становится общедоступным. Университеты начали предлагать учебные программы по новой технологии, и число производителей аппаратного обеспечения быстро росло. Внезапно компьютеры, и посвященные им учебные курсы, стали доступны всем, или, по крайней мере, тем, кто посещал колледж.В то же время, компьютеры стали значительно эффективнее и функциональнее. Круг проблем, которые они могли решать, серьезно изменился как по уровню, так и по сложности. Языки программирования также становились мощнее и проще в использовании. 60-е годы были периодом феноменального роста компьютерных технологий и задали тон оставшейся части столетия.
Между тем, в эти годы развитие отрасли могло пойти по тупиковому пути. Менее талантливые люди брались за решение более сложных задач. (Действительно, как можно было найти еще более талантливых и более дотошных разработчиков, чем программисты 50-х годов?) Ситуация располагала к катастрофе, но катастрофы не произошло. Программное обеспечение, написанное в 60-х годах, отличается столь же высоким качеством, что и программы, созданные десятилетием раньше.
Этот кажущийся парадокс имеет простое, хотя и неочевидное, объяснение. Программисты в 60-е годы были добросовестными, а качество программ высочайшим... благодаря отсутствию персональных средств компиляции.
Компиляция в 60-е годы была делом не из легких. По большей части компания или университет имели только один огромный компьютер. Компилятор на этом компьютере, во-первых, находился довольно далеко от рабочего места программиста, во-вторых, был настолько загружен, что время работы на нем приходилось резервировать заранее, а, в-третьих, он был крайне восприимчив к ошибкам в синтаксисе и конструкциях языка программирования.
Другими словами, компиляция недостаточно совершенной программы требовала огромных непроизводительных затрат времени и сил, и, в результате, могла потребовать значительных переделок. Представьте, что вам нужно пройти несколько сот метров, неся в руках стопку перфокарт высотой 20 см только для того, чтобы машина выдала обратно эту пачку с сообщением о «несогласовании типов» на 30-й перфокарте. И могло оказаться так, что к компилятору в следующий раз вас допустят только через несколько дней, а то и недель.
Мучительный процесс компиляции заставлял программистов часами просиживать за рабочими столами с карандашом в руках, тщательно проверяя свои программы, обращаться за помощью к коллегам и снова читать, читать и читать свои перфокарты до тех пор, пока не будут исчерпаны все возможные средства их проверки. Никакие меры не казались излишними, поскольку цена небрежности была слишком высока.
XP
Из всех новых методологий eXtreme Programming находится в самом центре всеобщего внимания. Именно благодаря XP активные методологии вызвали такой ажиотаж и всевозможные слухи.Поначалу XP относили в лучшем случае к хакерству в худшем смысле слова. Многие до сих пор считают эту методологию чем-то вроде культа Вуду, несмотря на то, что ее основателем и главным идеологом является Кент Бек (Kent Beck) - всемирно известный эксперт по языку Smalltalk и разработке объектно-ориентированных систем. Другим видным пропагандистом XP является Мартин Фаулер (Martin Fowler) - тоже всемирно признанный ученый-исследователь и автор многочисленных публикаций на темы ОО систем, паттернов, UML и реструктуризации программ.
На данный момент уже сложилась достаточно обширная практика применения XP, доказывающая высокую эффективность этого подхода.
Чтобы понять XP, нужно забыть о том, что разработка ПО - это инженерная дисциплина. Ведь ни один инженерный проект не сталкивается в процессе реализации с такими проблемами, как изменение характеристик изделия в ходе разработки. Разве возможно, чтобы, например, при строительстве дома, позвонил заказчик и сказал: "Сделайте мне пятый этаж чуть пониже, шестой немного расширьте влево, а вместо лестницы установите американскую горку"? В программных проектах требования очень часто изменяются в ходе работ, не зависимо от первоначальной модели и архитектуры системы. Так что же тогда за процесс - программирование? В свете XP разработка напоминает написание книги группой авторов.
Согласитесь, что нет другого способа создать литературное произведение, кроме как писать его. Ведь сколь ни хорош был бы сюжет, сколь ни точен сценарий, сколь ни загадочны поступки героев, все это читатель сможет узнать только из готового, законченного произведения, а не из проекта. Нет другого способа написать хорошую книгу, кроме как постоянно следить за качеством каждой ее части и исправить недоработки в процессе написания.
Согласитесь, чтобы написать хорошую книгу группой авторов, нужно очень эффективно организовать их взаимоотношения.
А если над одним и тем же материалом будут работать по два человека, то, скорее всего, он получится более содержательный и объективный.
Все эти принципы применимы и при создании программной системы. Хотя Кент Бек и говорит, что они давно известны в практике программирования, только с появлением XP они действительно образовали эффективную методологию.
Простейшее работоспособное решение (Simplest thing that could possibly work)
Смысл XP заключается в спартанском лозунге о стремлении к совершенству через естественность и простоту. Мы принимаем мир таким, какой он есть: заказчика со всеми его желаниями, программирование со всеми его трудностями, программу со всеми ее недостатками. Мы не требуем технически грамотных пользователей, выдающихся архитекторов и интеллектуальных инструментов. Мы требуем одного - возможности эффективно работать. Для этого мы избавляемся от всей ненужной и бесполезной рутины, какую только сможем найти в нашем процессе разработки. То, что после этого останется - необходимо для создания качественного продукта в рамках бюджета.
Проникновение задачей (Personal involvement)
Естественно, XP не ограничивается общими фразами, подобным приведенным выше. XP - это настоящая методология, и она имеет определенный набор действий, которые должны выполняться соответствующим образом. В отличие от других методологий XP требует дисциплину и самоотдачу, сравнимую со спартанской, потому что нет никаких формальных процедур, регламентирующих процесс. Соответственно и руководитель XP разработки должен обладать высоким авторитетом и умением чувствовать ситуацию.
Постоянное общение
По мнению самого Бека и других специалистов, команда XP разработчиков не должна превышать 10-15 человек и они обязательно должны находиться в одном помещении, чтобы сократить до минимума издержки взаимодействия. При большем количестве участников проекта или отсутствия подходящего помещения, по крайней мере, постоянно контактирующие разработчики должны иметь возможность общаться без необходимости договариваться об этом предварительно.
Известны успешные проекты и больших коллективов, вплоть до 40 человек.
Наместник заказчика (On site customer)
Все зависит от команды, а также от заказчика, обязанного предоставлять полную и своевременную информацию о требованиях и оценках функциональности продукта. Разумеется, XP методисты не так наивны, чтобы ожидать идеального клиента в каждом проекте, и потому включают в команду разработчиков специального человека, представляющего заказчика, взаимодействующего с ним и отвечающего на вопросы программистов как можно яснее.
Парное программирование (Pair programming)
Разработчики, как правило, работают парами за одним компьютером. В то время как один набирает код, другой имеет возможность думать о последствиях принятого решения. Когда первый устанет, роли меняются. Такая практика позволяет эффективно делится опытом и приобретать знания об отдельном участке программы сразу нескольким людям, так что в случае ухода одного из, второй сможет быстро объяснить новичку все нюансы. Это особенно важно при данном виде разработки, когда вся документация создается в исходных текстах. Парное программирование - это наиболее широко распространенная информация об XP.
Общий стандартизованный код
В столь динамично развивающемся проекте, какой получается при XP разработке, ничто не должно мешать разработчикам улучшать систему, в том числе и принадлежность исходного кода кому-нибудь лично. В любой момент любой человек при достаточных основаниях может изменить любую часть программы. Этот факт приводит к пониманию того, насколько важно соблюдать общий стиль программирования и включать в код как можно больше комментариев. По сути дела, программный код XP проекта и есть документация, которая всегда отражает последние изменения.
Тесты вперед (Test first)
Также хорошо известной и зарекомендовавшей себя методикой является написание тестов до начала кодирования функций программы. Программист должен решить, каким образом можно проверить работоспособность будущего кода, и создать соответствующий тест, который может быть автоматически запущен в любое время и выдать результат: работает функция или нет.
Все тесты объединяются и, прежде чем вновь написанный или измененный код будет присоединен к проекту, производится тестирование на уровне модулей (unit testing).
Кроме этого, отдельная группа создает второй вид существующих в XP тестов - функциональные тесты (functional tests), которые проверяют работоспособность системы в целом перед поставкой заказчику и делают это в автоматизированном режиме.
Таким образом, "тесты вперед" подход, хотя и не гарантирует 100% работоспособности, все-таки предоставляет очень высокие гарантии качества и позволяет и программистам и заказчику чувствовать себя более уверенно на пути к окончательному выпуску продукта.
Ежедневная сборка (Daily builds)
Чтобы еще сильнее повысить качество, XP предписывает делать промежуточные выпуски системы как можно чаще, даже до одного раза в неделю. Сборку системы или отдельных подсистем рекомендуется производить как минимум ежедневно, чтобы можно было после рабочего дня в автоматическом режиме проверять с помощью функциональных тестов ее работоспособность, а в случае неполадок быстро исправить ошибки, которые при таком подходе могли быть сделаны только накануне. При регулярных выпусках системы пользователи имеют возможность своевременно сообщать о недоработках, что улучшает продукт по ходу разработки. Как говорит Кент Бек: "Оптимизм - болезнь разработчиков, мнение заказчика - лекарство".
Рассказы пользователей (User stories)
Как же можно разрабатывать систему, если нет ни утвержденных спецификаций, ни плана разработки, ни архитектуры, да еще постоянно вносятся изменения? Вот это - то самое чудо, которое стало возможным благодаря XP. Ответ прост как все гениальное: мы начинаем разработку как только понимаем, чего хочет заказчик В ДАННЫЙ МОМЕНТ. В последующем, мы перестраиваем программы так, чтобы отражать вносимые изменения. При этом мы планируем только то, что можем предвидеть, а разрабатываем только то, что востребовано.
Для проведения этого простого принципа в жизнь, в XP предназначена специальная процедура, называемая "Рассказы пользователей", которая означает то же, что и прецеденты использования (use cases) в UML, но не имеют никакого формального выражения.
Просто потребности пользователей должны быть осознаны всеми участниками проекта. Основную роль в этом играют неформальные встречи и дискуссии, а также "наместник" заказчика в группе разработки. Каждая "история" описывает какую-либо функциональную сторону системы и должна быть оценена по двум шкалам: "бизнес-ценность" и "величина риска". Затем эти "User Stories", ставшие уже полноценными требованиями, сортируются и на самом верху оказываются те, чьи бизнес или риск значение максимальны. Вот ими то и следует заняться в первую очередь. Риск не может быть устранен полностью, но заказчик должен о нем знать, а разработчики должны провести исследования и/или разработать прототипы, позволяющие обнаружить способы решения ожидаемых проблем.
Рефакторинг (Refactoring)
Как же писать программы в такой динамичной и постоянно меняющейся обстановке? Это объясняет другая, также нашумевшая техника XP, подразумевающая реструктуризацию и заключающаяся в осознанном подходе к вопросам модификации кода без потери его функциональности. Книга М. Фаулера подробно описывает этот процесс и включает большое количество примеров. На сайте www.retactoring.com поддерживается on-line версия каталога приемов реструктуризации и полезные ссылки. Конечно, программы модифицировали всегда, но только с появлением XP это стало не второстепенным занятием исправления просчетов, а полноценной техникой разработки, позволяющей вносить изменения таким образом, чтобы улучшать внутреннее устройство системы, а не приводить к ее деградации.
Разумное проектирование
Очень многие считают, что XP - это новый вид RAD (Rapid Application Development - Быстрая Разработка Приложений) технологии, которая зарекомендовала себя как недальновидная. На самом деле, XP не только поощряет проектирование, но и включает его в методологию. Как обычно, система требует тщательного планирования, но только уже без излишнего "пророчества" и требований к инструментарию. Для разработки общей архитектуры достаточно настенной доски для рисования.
Если потребуется, дизайн можно сфотографировать и включить в документацию проекта. Как всегда, следует выделить те компоненты, которые, скорее всего, потребуют модернизации и постараться создать для этого соответствующие условия. Большим уважением пользуются паттерны проектирования и различного рода эвристики. Как и любая деятельность в XP, планирование компонента должно начинаться только тогда, когда оно безусловно необходимо. Особенно рекомендуется откладывать на возможно более долгий срок определение пользовательского интерфейса, как наиболее часто изменяющуюся часть системы и наиболее сильно отражающуюся на пользователях.
"Экстремальная" символизация
XP является флагманом новых методологий и в наибольшей мере символизирует их ценности:
Как и все остальные прогрессивные методологии, XP не является жестко детерминированным процессом и предполагает настройку на конкретную ситуацию и людей в контексте существующего проекта.
Продолжение может последовать. Если эта тема Вас заинтересовала - пишите мне!
Александр Родыгин,
В данной работе рассмотрены различные
В данной работе рассмотрены различные схемы хранения информации о правах доступа. Для конкретной системы нужно строить свою схему исходя из требований по быстродействию и уровню ограничения доступа.
Программирование: Языки - Технологии - Разработка
- Программирование
- Технологии программирования
- Разработка программ
- Работа с данными
- Методы программирования
- IDE интерфейс
- Графический интерфейс
- Программирование интерфейсов
- Отладка программ
- Тестирование программ
- Программирование на Delphi
- Программирование в ActionScript
- Assembler
- Basic
- Pascal
- Perl
- VBA
- VRML
- XML
- Ada
- Lisp
- Python
- UML
- Форт
- Языки программирования







