Компрессия данных в системах промышленной автоматизации. Алгоритм SwingingDoor

    Здравствуйте, уважаемые читатели. Хочу представить вашему вниманию описание алгоритма компрессии данных SwingingDoor и рассказать о том, как мы его применяем.



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

    Зачем использовать компрессию, почему бы не хранить все данные?


    Компрессия данных


    Причины достаточно очевидны:
    • для сокращения дискового пространства для хранения данных;
    • для сокращения нагрузки каналов передачи данных.

    Конечно, сейчас доступны жесткие диски с большим объемом памяти и каналы связи становятся все лучше и лучше, но, будем реалистами, эти вопросы нельзя не рассматривать. К тому же, как будет сказано ниже, хранение всего объема данных не всегда имеет смысл.
    Кстати, вместо компрессии можно использовать прореженные данные (среднее значение параметра за период), но эти значения уже будут отличаться от «сырых» данных, полученных из систем контроля. Усредненные данные будут сглаживать мгновенные максимальные и минимальные значения параметров. Для части задач это допустимо, а для части нет.

    Как мы используем компрессию данных


    Одной из задач нашей системы является консолидация данных из различных СК предприятия в единую базу данных.
    Некоторые СК, например телемеханика, предоставляют данные каждую секунду, при этом сами данные могут изменяться не значительно.
    Например, если взглянуть на график, приведенный ниже, то мы увидим, что значения параметра «Суммарная генерация по ТЭЦ» изменяются в пределах от 11,5 до 12,5 МВт, при этом в большинстве случаев соседние значения отличаются друг от друга менее чем на 0.1, а общая динамика изменений имеет некоторую закономерность.



    Для того чтобы не хранить «лишние» данные, часть отсчетов мы можем пропускать. Компрессия как раз и заключается в выборке «нужных» данных из входного потока.

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

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

    Ниже на графике зеленой линей показаны точки, которые останутся после применения компрессии.


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

    Алгоритм SwingingDoor


    Для компрессии данных мы используем алгоритм SwingingDoor. Алгоритм был запатентован в США в мае 1987 года. Основная область применения алгоритма — системы АСУТП и информационные системы производства.

    Принцип работы

    Алгоритм носит название «Вращающаяся дверь». В названии алгоритма отражен принцип работы.
    Шаг #1 — Получаем первую точку. На расстоянии равном погрешности E откладываем по вертикали две опорные точки L и U.


    Шаг #2 — Получаем вторую точку. Через опорные точки L, U и полученную точку проводим лучи. Лучи образуют двери коридора.

    Шаг #3 — Точка 3 не входит в коридор, построенный на втором шаге. Вращаем луч L по часовой стрелке до точки 3

    Шаг #4 — Точка 4 не входит в коридор, построенный на предыдущем шаге. Вращаем луч U против часовой стрелке до точки 4

    Шаг #5 — Точка 5 входит в коридор, ничего не делаем

    Шаг #6 — Точка 6 не входит в коридор. Начинаем вращать луч U против часовой стрелки до пересечения с точкой 6 и обнаруживаем, что двери коридора открылись

    Шаг #7 — Открываем новый коридор, начиная с точки 5. Точки 1 и 5 сохраняем


    Итого из 5 первых точек сохранены будут только две. В примере 3 точки для нас оказались «лишними», что позволило нам отсечь 60% входных данных.

    В спецификации алгоритма предлагается начинать новый коридор с точки расположенной между точками 5 и 6 и отстоящей от луча U на E / 2. Но в нашем проекте мы поступаем иначе — новый коридор начинаем строить с последней точки, которая входит в коридор, т.е. с точки 5, поскольку при таком поведении мы гарантируем, что все прореженные данные будут иметь временную метку и значение, полученное из системы контроля.

    Настройка алгоритма

    • Погрешность E — задает максимально возможное отклонение точек коридора от результирующей линии (по оси Y). На картинке выше эта линия между точками 1 и 5. Погрешность необходимо задавать для каждого параметра отдельно, исходя из его смысла. Например, скачки генерации на с 10 на 10,2 МВт является допустимым, но скачек частоты на с 50 на 50,2 Гц является серьезным нарушением. Поэтому для генерации погрешность можно задать, например, равной 0,1, а для частоты — 0,01.
    • Время жизни коридора — время, в течение которого должна быть сохранена хотя бы одна точка. Возможны варианты течения процесса, когда данные могут изменяться не значительно (температура воздуха в морозную зимнюю ночь). В таком случае они будут попадать в текущий коридор допустимых значений и алгоритм не будет принимать решение об их сохранении. Чтобы избежать таких случаев вводится соответствующий параметр, который отвечает за то, как долго данные в рамках одного коридора могут не сохраняться. Например, для данных с частотой обновления 1 секунда можно указать этот параметр равный 30 секундам, тем самым обеспечив хотя бы одно значение в прореженном графике за 30 секунд.


    Заключение


    Использование компрессии данных позволило нам:
    • предоставлять сотрудникам предприятия «сырые» тренды параметров, которые были получены из СК месяцы назад;
    • снизить объем дискового пространства хранения данных;
    • снизить нагрузку каналов передачи данных;
    • оптимизировать службы сбора данных из СК предприятия, тем самым снизив загрузку CPU серверов, на которых установлены службы сбора данных.


    Демонстрационное приложение


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



    Материалы


    US-Patent-4669097 — Data compression for display and storage

    Комментарии 43

      +2
      Будьте человеком, уберите под кат.
        +2
        Спасибо. Убрал.
        +2
        Получается компрессия с потерями.
        А что если необходимо обрабатывать данные которые имеют большие колебания?
        Вот если взять не Вашу ТЭЦ, а какую-нибудь покрупнее, там колебания будут побольше и что тогда…
        А почему бы не сглаживать какими-нибудь рядами Фурье и их коэффициенты считать компрессией?
          0
          >> А что если необходимо обрабатывать данные которые имеют большие колебания?
          Для таких параметров указывается более маленькая погрешность, тогда никакие колебания мимо не пройдут — все экстремумы будут сохранены.

          >> А почему бы не сглаживать какими-нибудь рядами Фурье
          Если использовать сглаживание, то значения в экстремумах будут отличаться от действительных значений, полученных, например, с приборов. Для нас важно сохранять именно «сырые» данные, поскольку любое их изменение может повлечь ошибку в анализе процесса.
            0
            Еще насчет колебаний.
            Если под «большими» колебаниями Вы понимаете большую амплитуду, то алгоритм будет прекрасно работать без уточнения погрешности. В ходе работы направление коридора просто будет изменяться, захватывая все новые и новые точки.
            Уточнение погрешности потребуется только в том случае, если мы следим за параметром, значение которого имеет малую амплитуду колебаний, например 0,01.
              +1
              Да, потери есть. Но это не беда, потому что алгоритм обеспечивает интерполяцию с погрешностью не превышающую заданную. Даже в случае больших колебаний.
              Плюс исходные данные всегда содержат погрешность, не надо думать, алгоритм портит идеальные данные (улыбка)
              Что касается рядов Фурье и прочих сложных методов — они не очень хороши для практики, когда надо быстро архивировать тысячи и десятки тысяч значений каждую секунду. Прелесть Swing Door в том, что он получает новую точку и тут же принимает решение архивировать ее или нет. Он не работает с рядом значений, он работает с одной последней точкой.
                0
                А как же FFT
                  –1
                  FFT работает с рядом, а SwingDoor с значением.
                  Сложность быстрого преобразования Фурье обычно что-то типа O(N*ln(N)).
                  Сложность SwingDoor O(1).
                  К тому же FFT не гарантирует непревышение погрешности (могу ошибать, но почти уверен).
                    0
                    К слову. У нас в СГАУ был замечательный преподаватель Владимир Михайлович Чернов. Один из мировых экспертов по быстрым преобразованиям. Так вот он нам рассказывал про кучу методов быстрых FFT. Но все они затратны по вычислениям и по памяти.
                    А еще, когда мы использовали всякие методы для улучшения качества изображений, он говорил, что математическими методами изображение улучшить нельзя, можно только ухудшить. Но это уже другая история, просто вспомнилось.
                +2
                Гмм… я такую же штуку несколько лет назад придумал, и тоже для промышленной автоматики. А оказывается, оно имеет название и запатентовано.
                  0
                  Да. Так оно и есть, существует несколько запатентованных алгоритмов компрессии.

                  Когда мы думали над тем каким образом лучше отфильтровать входной поток, то изучили несколько альтернативных алгоритмов компрессии: Boxcar, Backslope, SLIM1, SLIM2, SLIM3.

                  SwingingDoor оказался более эффективным и быстрым. Коэффициент сжатия на практике получился около 17.
                  +2
                  Очень полезный алгоритм, спасибо.
                    0
                    Пожалуйста. Сами радуемся, что узнали о его существовании.
                    +1
                    а чем полином 6-го порядка плох?
                    То что вы описали похоже на moving average (не умничаю, просто не знаю, как по-русски). Не всякая дата подходит под этот метод, ИМХО.
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        :)
                        может быть.
                        Знал бы как, написал.
                        0
                        Плюсы этого алгоритма — скорость работы. Для ответа на вопрос «Нужно ли сохранять следующую точку?» не надо помнить о предыдущих 5-6 точек, как, полагаю, потребуется для построения полинома.

                        Особенно это условие становиться актуальным если учесть, что нашему Инфоконту надо обрабатывать десятки тысяч параметров в секунду.
                          0
                          Moving average, насколько помню из университетского курса, это обработка сигнала для уменьшения помех. Компрессии там нет.
                          Или я не прав?
                          0
                          Устроим конкурс, кто на предоставленных сырых данных может предоставить лучший алгоритм сжатия? :) Во всяком случае, не смотрели, как жмет gzip/bzip2 алгоритм, к примеру? Насколько они будут менее успешны? Подразумевается, что жать данные нужно порциями, чтобы иметь возможность быстрой перемотки.
                            0
                            Ответил ниже, комментом промахнулся.
                            0
                            Ну если только «just for fun» :)
                            GZIP — сжимает информацию, при этом сохраняет все данные, а SwingingDoor — выполняет компрессию, при этом часть данных «выкидывается».

                            Как вариант — сначала отфильтровать данные при помощи SwingingDoor, а затем полученный остаток сжать.

                            Но даже такой вариант для нас не прокатит, поскольку сохраненные данные мы еще в Инфоконте и на мнемосхемах отображаем. Это тогда перед их показом надо будет на лету «разжимать».
                              0
                              Именно «just for fun» :) Интересно ведь, насколько специализированные алгоритмы быстрей алгоритмов сжатия общего назначения. Сравнивая SwingingDoor с gzip можно будет сказать, что «сжатие с потерями более чем в 10 раз эффективнее lossless алгоритма». Если же только в полтора, невольно задумаешься, может быть не стоило терять точность результата, тем более специально для этого переводя цифры в плавающую точку.
                                +1
                                Боюсь, все же адекватного сравнения не получится, поскольку что бы что-то сравнивать надо установить критерии по которым будет идти сравнение.

                                Предположим, что это время за которое алгоритм обрабатывает N параметров и коэффициент сжатия Z — отношение числа параметров на входе к числу параметров на выходе.

                                Измерив эти данные, мы сможем сказать кто круче по времени, а кто по сжатию. Но эта информация на практике нам будет не интересна, поскольку в Инфоконте с систем контроля мы получаем поток данных, размер которого изначально не определен. За одну итерацию может поступить как 1, так и 10 000 параметров(так работают системы контроля на предприятии, отправляют данные по изменению).

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

                                Другой параметр — это коэффициент сжатия. Если для gzip'a он будет постоянным, то для swingdoor будет существовать зависимость от длины ряда. Например, возможен ход процесса, когда данные меняются не значительно, тогда большую часть из них можно отсечь. Если такие данные подавать непрерывно, то будут сохранено меньше точек, если бы подавали эти данные маленькими кусками, поскольку первая и последняя точка коридора должна быть сохранена.

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

                                И еще для GZIP надо помнить, что для отображения данных на мнемосхеме мы должны прочитать данные из БД, декодировать их, после чего отобразить. Для SwingingDoor декодирование не требуется.

                                Итого, при первом приближение имеем уже 4 коэффициента, которые косвенно связаны между собой. Сравнение алгоритмов сведется к анализу ф-ии GZIP(N, Z, T, S) и SwinginDoor(N, Z, T, S), которое за ближайшие несколько дней мы провести не успеем :)
                                  +1
                                  Этот комментарий сделал статью более понятной. Как-то упустил из вида, что информация о промежуточных точках не сохраняется. Видимо да, тогда алгоритмы сжатия не сравнимы с SwingingDoor в общем случае (лишь в конкретных), поскольку алгоритм скорей относится к фильтрации значений, и в меньшей степени — к компрессии. Все равно статья познавательна. Спасибо :)
                                    0
                                    Мы поняли друг друга ;)
                                  0
                                  Этот алгоритм ещё и уменьшает вычислительную нагрузку при последующей обработке, но при этом позволяет удерживать погрешность в заданном интервале. Его можно и нужно рассматривать не только, как алгоритм компрессии, но и как алгоритм фильтрации.
                                  0
                                  Это тогда перед их показом надо будет на лету «разжимать».
                                  SwingingDoor тоже требуется декодировать. В зависимости от степени сжатия gzip может оказаться не столь уж и тормозным, по сравнению со SwingingDoor. Хотя думаю, все будет зависеть от самих данных: если меняются скачкообразно и часто, то тут преимущества перед gzip большого не будет. Или как на практике?
                                    0
                                    >> SwingingDoor тоже требуется декодировать.
                                    В том то и дело, что декодировать ничего не надо. Мы получаем точку, решаем сохранить ли ее, если да, то укладываем ее в БД.
                                    Далее при просмотре данных на мнемосхеме делаем select из БД.

                                    >>Хотя думаю, все будет зависеть от самих данных: если меняются скачкообразно и часто, то тут преимущества перед gzip большого не будет. Или как на практике?
                                    Сложно сказать, надо проводить опыт над конкретными рядами данных.
                                  0
                                  Добавьте пожалуйста в архив с демоприоложением само приложение .exe :)
                                    0
                                    Вот тут живет .exe отдельно без исходников.
                                      0
                                      спасибо!
                                    +1
                                    Всвязи с тем, что есть массовое недопонимание повторюсь.
                                    Этот алгоритм не только и не столько сжатие данных, сколько фильтрация. Он уменьшает вычислительную нагрузку при последующей обработке и при этом позволяет удерживать погрешность в заданном интервале. Например, у вас есть некие данные в огромном количестве и нужно их отфильтровать. Причём в реальном времени. Но так, чтобы с заданной погрешностью? Как? Этот алгоритм позволит это сделать при минимальных вычислительных затратах и без хранения предыстории. Всякого рода «обычные» цифровые фильтры тут проигрывают по причине большого расхода памяти и/или серьёзных вычислений и не достаточно сложно прогнозируются в плане погрешности.
                                      0
                                      Спасибо, что подвели итог.
                                      Ваш комментарий, действительно, формализует то, что до этого читалось между строк в комментариях, но не было сказано прямо в самой статье.
                                      0
                                      В принципе алгоритм полезный. Если бы не вот это самое E. Получается максимальную погрешность я должен знать заранее? А если я ее не знаю? А если нужно проанализировать уже сжатый поток но с меньшим E?
                                      А если нужно сравнить два сжатых потока, а они сжаты с разным E?
                                      В любом случае, наличие такого рода констант — минус алгоритма.
                                        0
                                        И еще, исходя из картинки с зеленой ломаной, я так понимаю что точки экстремума ломаной не совпадают с точками локального экстремума исходного ряда? Это тоже не есть хорошо.
                                          0
                                          В примере некоторые экстремумы красной линии не совпадают с экстремумами зеленой линии, т.к. точки зеленой линии лежат в пределах заданной погрешности алгоритма.
                                          0
                                          Да, это минус алгоритма.

                                          Для каждого параметра надо экспертным путем решать допустимое значение погрешности(пример в статье про изменения частоты на 0.01 Гц и изменение мощности на 0.1 МВт). Для реализации алгоритма в Инфоконте задача упрощается тем, что мы заранее имеем информацию о типах параметров, а для каждого типа параметра характерна своя допустимая погрешность.

                                          Теоретически алгоритм можно модифицировать, сделав его адаптивным при помощи пересчета погрешности E для каждого нового коридора. Для этого надо ввести показатели на сколько текущая погрешность удовлетворяет нам, например, можно считать, что погрешность «хорошая» если в коридор попадает 20% точек, а если более этого, то на следующем шаге погрешность можно уменьшить на заданную величину. Но это только теоретически, опыты такие не проводили.
                                          0
                                          а чем не устраивают общеизвестные Дугласа-Пекера и Вишванатана-Вата?
                                            0
                                            Не устраивают скоростью, и объемом информации, которую необходимо держать в памяти(чуть выше рассматривали этот вопрос).

                                            Если рассматривать алгоритм Дугласа-Пекера, то чтобы отсечь «лишние» точки необходимо в памяти держать координаты всех предыдущих точек(по крайней мере на первом шаге), перебирать все точки ломанной, находить наиболее удаленную и т.д А Инфоконт поступают десятки тысяч таких точек каждую секунду.

                                            Прелесть алгоритма SwingingDoor в том, что для принятия решения о записи точки не надо помнить о предыдущих данных. Алгоритм принимает решение в реальном времени, чем существенно экономит ресурсы машины.
                                              0
                                              дугласа-пекера не обязывает вас хранить все точки :) можно хранить только кусочек который необходимо сгладить, а судя по описанию алгоритмическая сложность дугласа-пекера проще (ИМХО), всеголишь тривиальный поиск минимумов-максимумов.
                                            0
                                            На топкодер сегодня заканчивается марафон. Задача возможно очень похожа на вашу: community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=24042&rd=15038
                                              0
                                              Виноват. Там без потери данных надо жать…
                                              0
                                              На основании чего принимаем решение какую дверь крутить для следующей точки не вошедшей в коридор?

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

                                              Самое читаемое