Comments 43
Будьте человеком, уберите под кат.
Получается компрессия с потерями.
А что если необходимо обрабатывать данные которые имеют большие колебания?
Вот если взять не Вашу ТЭЦ, а какую-нибудь покрупнее, там колебания будут побольше и что тогда…
А почему бы не сглаживать какими-нибудь рядами Фурье и их коэффициенты считать компрессией?
А что если необходимо обрабатывать данные которые имеют большие колебания?
Вот если взять не Вашу ТЭЦ, а какую-нибудь покрупнее, там колебания будут побольше и что тогда…
А почему бы не сглаживать какими-нибудь рядами Фурье и их коэффициенты считать компрессией?
>> А что если необходимо обрабатывать данные которые имеют большие колебания?
Для таких параметров указывается более маленькая погрешность, тогда никакие колебания мимо не пройдут — все экстремумы будут сохранены.
>> А почему бы не сглаживать какими-нибудь рядами Фурье
Если использовать сглаживание, то значения в экстремумах будут отличаться от действительных значений, полученных, например, с приборов. Для нас важно сохранять именно «сырые» данные, поскольку любое их изменение может повлечь ошибку в анализе процесса.
Для таких параметров указывается более маленькая погрешность, тогда никакие колебания мимо не пройдут — все экстремумы будут сохранены.
>> А почему бы не сглаживать какими-нибудь рядами Фурье
Если использовать сглаживание, то значения в экстремумах будут отличаться от действительных значений, полученных, например, с приборов. Для нас важно сохранять именно «сырые» данные, поскольку любое их изменение может повлечь ошибку в анализе процесса.
Еще насчет колебаний.
Если под «большими» колебаниями Вы понимаете большую амплитуду, то алгоритм будет прекрасно работать без уточнения погрешности. В ходе работы направление коридора просто будет изменяться, захватывая все новые и новые точки.
Уточнение погрешности потребуется только в том случае, если мы следим за параметром, значение которого имеет малую амплитуду колебаний, например 0,01.
Если под «большими» колебаниями Вы понимаете большую амплитуду, то алгоритм будет прекрасно работать без уточнения погрешности. В ходе работы направление коридора просто будет изменяться, захватывая все новые и новые точки.
Уточнение погрешности потребуется только в том случае, если мы следим за параметром, значение которого имеет малую амплитуду колебаний, например 0,01.
Да, потери есть. Но это не беда, потому что алгоритм обеспечивает интерполяцию с погрешностью не превышающую заданную. Даже в случае больших колебаний.
Плюс исходные данные всегда содержат погрешность, не надо думать, алгоритм портит идеальные данные (улыбка)
Что касается рядов Фурье и прочих сложных методов — они не очень хороши для практики, когда надо быстро архивировать тысячи и десятки тысяч значений каждую секунду. Прелесть Swing Door в том, что он получает новую точку и тут же принимает решение архивировать ее или нет. Он не работает с рядом значений, он работает с одной последней точкой.
Плюс исходные данные всегда содержат погрешность, не надо думать, алгоритм портит идеальные данные (улыбка)
Что касается рядов Фурье и прочих сложных методов — они не очень хороши для практики, когда надо быстро архивировать тысячи и десятки тысяч значений каждую секунду. Прелесть Swing Door в том, что он получает новую точку и тут же принимает решение архивировать ее или нет. Он не работает с рядом значений, он работает с одной последней точкой.
А как же FFT
FFT работает с рядом, а SwingDoor с значением.
Сложность быстрого преобразования Фурье обычно что-то типа O(N*ln(N)).
Сложность SwingDoor O(1).
К тому же FFT не гарантирует непревышение погрешности (могу ошибать, но почти уверен).
Сложность быстрого преобразования Фурье обычно что-то типа O(N*ln(N)).
Сложность SwingDoor O(1).
К тому же FFT не гарантирует непревышение погрешности (могу ошибать, но почти уверен).
К слову. У нас в СГАУ был замечательный преподаватель Владимир Михайлович Чернов. Один из мировых экспертов по быстрым преобразованиям. Так вот он нам рассказывал про кучу методов быстрых FFT. Но все они затратны по вычислениям и по памяти.
А еще, когда мы использовали всякие методы для улучшения качества изображений, он говорил, что математическими методами изображение улучшить нельзя, можно только ухудшить. Но это уже другая история, просто вспомнилось.
А еще, когда мы использовали всякие методы для улучшения качества изображений, он говорил, что математическими методами изображение улучшить нельзя, можно только ухудшить. Но это уже другая история, просто вспомнилось.
Гмм… я такую же штуку несколько лет назад придумал, и тоже для промышленной автоматики. А оказывается, оно имеет название и запатентовано.
Да. Так оно и есть, существует несколько запатентованных алгоритмов компрессии.
Когда мы думали над тем каким образом лучше отфильтровать входной поток, то изучили несколько альтернативных алгоритмов компрессии: Boxcar, Backslope, SLIM1, SLIM2, SLIM3.
SwingingDoor оказался более эффективным и быстрым. Коэффициент сжатия на практике получился около 17.
Когда мы думали над тем каким образом лучше отфильтровать входной поток, то изучили несколько альтернативных алгоритмов компрессии: Boxcar, Backslope, SLIM1, SLIM2, SLIM3.
SwingingDoor оказался более эффективным и быстрым. Коэффициент сжатия на практике получился около 17.
Очень полезный алгоритм, спасибо.
а чем полином 6-го порядка плох?
То что вы описали похоже на moving average (не умничаю, просто не знаю, как по-русски). Не всякая дата подходит под этот метод, ИМХО.
То что вы описали похоже на moving average (не умничаю, просто не знаю, как по-русски). Не всякая дата подходит под этот метод, ИМХО.
UFO just landed and posted this here
Плюсы этого алгоритма — скорость работы. Для ответа на вопрос «Нужно ли сохранять следующую точку?» не надо помнить о предыдущих 5-6 точек, как, полагаю, потребуется для построения полинома.
Особенно это условие становиться актуальным если учесть, что нашему Инфоконту надо обрабатывать десятки тысяч параметров в секунду.
Особенно это условие становиться актуальным если учесть, что нашему Инфоконту надо обрабатывать десятки тысяч параметров в секунду.
Moving average, насколько помню из университетского курса, это обработка сигнала для уменьшения помех. Компрессии там нет.
Или я не прав?
Или я не прав?
Устроим конкурс, кто на предоставленных сырых данных может предоставить лучший алгоритм сжатия? :) Во всяком случае, не смотрели, как жмет gzip/bzip2 алгоритм, к примеру? Насколько они будут менее успешны? Подразумевается, что жать данные нужно порциями, чтобы иметь возможность быстрой перемотки.
Ну если только «just for fun» :)
GZIP — сжимает информацию, при этом сохраняет все данные, а SwingingDoor — выполняет компрессию, при этом часть данных «выкидывается».
Как вариант — сначала отфильтровать данные при помощи SwingingDoor, а затем полученный остаток сжать.
Но даже такой вариант для нас не прокатит, поскольку сохраненные данные мы еще в Инфоконте и на мнемосхемах отображаем. Это тогда перед их показом надо будет на лету «разжимать».
GZIP — сжимает информацию, при этом сохраняет все данные, а SwingingDoor — выполняет компрессию, при этом часть данных «выкидывается».
Как вариант — сначала отфильтровать данные при помощи SwingingDoor, а затем полученный остаток сжать.
Но даже такой вариант для нас не прокатит, поскольку сохраненные данные мы еще в Инфоконте и на мнемосхемах отображаем. Это тогда перед их показом надо будет на лету «разжимать».
Именно «just for fun» :) Интересно ведь, насколько специализированные алгоритмы быстрей алгоритмов сжатия общего назначения. Сравнивая SwingingDoor с gzip можно будет сказать, что «сжатие с потерями более чем в 10 раз эффективнее lossless алгоритма». Если же только в полтора, невольно задумаешься, может быть не стоило терять точность результата, тем более специально для этого переводя цифры в плавающую точку.
Боюсь, все же адекватного сравнения не получится, поскольку что бы что-то сравнивать надо установить критерии по которым будет идти сравнение.
Предположим, что это время за которое алгоритм обрабатывает 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), которое за ближайшие несколько дней мы провести не успеем :)
Предположим, что это время за которое алгоритм обрабатывает 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), которое за ближайшие несколько дней мы провести не успеем :)
Этот комментарий сделал статью более понятной. Как-то упустил из вида, что информация о промежуточных точках не сохраняется. Видимо да, тогда алгоритмы сжатия не сравнимы с SwingingDoor в общем случае (лишь в конкретных), поскольку алгоритм скорей относится к фильтрации значений, и в меньшей степени — к компрессии. Все равно статья познавательна. Спасибо :)
Этот алгоритм ещё и уменьшает вычислительную нагрузку при последующей обработке, но при этом позволяет удерживать погрешность в заданном интервале. Его можно и нужно рассматривать не только, как алгоритм компрессии, но и как алгоритм фильтрации.
Это тогда перед их показом надо будет на лету «разжимать».
SwingingDoor тоже требуется декодировать. В зависимости от степени сжатия gzip может оказаться не столь уж и тормозным, по сравнению со SwingingDoor. Хотя думаю, все будет зависеть от самих данных: если меняются скачкообразно и часто, то тут преимущества перед gzip большого не будет. Или как на практике?
SwingingDoor тоже требуется декодировать. В зависимости от степени сжатия gzip может оказаться не столь уж и тормозным, по сравнению со SwingingDoor. Хотя думаю, все будет зависеть от самих данных: если меняются скачкообразно и часто, то тут преимущества перед gzip большого не будет. Или как на практике?
>> SwingingDoor тоже требуется декодировать.
В том то и дело, что декодировать ничего не надо. Мы получаем точку, решаем сохранить ли ее, если да, то укладываем ее в БД.
Далее при просмотре данных на мнемосхеме делаем select из БД.
>>Хотя думаю, все будет зависеть от самих данных: если меняются скачкообразно и часто, то тут преимущества перед gzip большого не будет. Или как на практике?
Сложно сказать, надо проводить опыт над конкретными рядами данных.
В том то и дело, что декодировать ничего не надо. Мы получаем точку, решаем сохранить ли ее, если да, то укладываем ее в БД.
Далее при просмотре данных на мнемосхеме делаем select из БД.
>>Хотя думаю, все будет зависеть от самих данных: если меняются скачкообразно и часто, то тут преимущества перед gzip большого не будет. Или как на практике?
Сложно сказать, надо проводить опыт над конкретными рядами данных.
Добавьте пожалуйста в архив с демоприоложением само приложение .exe :)
Вот тут живет .exe отдельно без исходников.
Всвязи с тем, что есть массовое недопонимание повторюсь.
Этот алгоритм не только и не столько сжатие данных, сколько фильтрация. Он уменьшает вычислительную нагрузку при последующей обработке и при этом позволяет удерживать погрешность в заданном интервале. Например, у вас есть некие данные в огромном количестве и нужно их отфильтровать. Причём в реальном времени. Но так, чтобы с заданной погрешностью? Как? Этот алгоритм позволит это сделать при минимальных вычислительных затратах и без хранения предыстории. Всякого рода «обычные» цифровые фильтры тут проигрывают по причине большого расхода памяти и/или серьёзных вычислений и не достаточно сложно прогнозируются в плане погрешности.
Этот алгоритм не только и не столько сжатие данных, сколько фильтрация. Он уменьшает вычислительную нагрузку при последующей обработке и при этом позволяет удерживать погрешность в заданном интервале. Например, у вас есть некие данные в огромном количестве и нужно их отфильтровать. Причём в реальном времени. Но так, чтобы с заданной погрешностью? Как? Этот алгоритм позволит это сделать при минимальных вычислительных затратах и без хранения предыстории. Всякого рода «обычные» цифровые фильтры тут проигрывают по причине большого расхода памяти и/или серьёзных вычислений и не достаточно сложно прогнозируются в плане погрешности.
В принципе алгоритм полезный. Если бы не вот это самое E. Получается максимальную погрешность я должен знать заранее? А если я ее не знаю? А если нужно проанализировать уже сжатый поток но с меньшим E?
А если нужно сравнить два сжатых потока, а они сжаты с разным E?
В любом случае, наличие такого рода констант — минус алгоритма.
А если нужно сравнить два сжатых потока, а они сжаты с разным E?
В любом случае, наличие такого рода констант — минус алгоритма.
И еще, исходя из картинки с зеленой ломаной, я так понимаю что точки экстремума ломаной не совпадают с точками локального экстремума исходного ряда? Это тоже не есть хорошо.
Да, это минус алгоритма.
Для каждого параметра надо экспертным путем решать допустимое значение погрешности(пример в статье про изменения частоты на 0.01 Гц и изменение мощности на 0.1 МВт). Для реализации алгоритма в Инфоконте задача упрощается тем, что мы заранее имеем информацию о типах параметров, а для каждого типа параметра характерна своя допустимая погрешность.
Теоретически алгоритм можно модифицировать, сделав его адаптивным при помощи пересчета погрешности E для каждого нового коридора. Для этого надо ввести показатели на сколько текущая погрешность удовлетворяет нам, например, можно считать, что погрешность «хорошая» если в коридор попадает 20% точек, а если более этого, то на следующем шаге погрешность можно уменьшить на заданную величину. Но это только теоретически, опыты такие не проводили.
Для каждого параметра надо экспертным путем решать допустимое значение погрешности(пример в статье про изменения частоты на 0.01 Гц и изменение мощности на 0.1 МВт). Для реализации алгоритма в Инфоконте задача упрощается тем, что мы заранее имеем информацию о типах параметров, а для каждого типа параметра характерна своя допустимая погрешность.
Теоретически алгоритм можно модифицировать, сделав его адаптивным при помощи пересчета погрешности E для каждого нового коридора. Для этого надо ввести показатели на сколько текущая погрешность удовлетворяет нам, например, можно считать, что погрешность «хорошая» если в коридор попадает 20% точек, а если более этого, то на следующем шаге погрешность можно уменьшить на заданную величину. Но это только теоретически, опыты такие не проводили.
а чем не устраивают общеизвестные Дугласа-Пекера и Вишванатана-Вата?
Не устраивают скоростью, и объемом информации, которую необходимо держать в памяти(чуть выше рассматривали этот вопрос).
Если рассматривать алгоритм Дугласа-Пекера, то чтобы отсечь «лишние» точки необходимо в памяти держать координаты всех предыдущих точек(по крайней мере на первом шаге), перебирать все точки ломанной, находить наиболее удаленную и т.д А Инфоконт поступают десятки тысяч таких точек каждую секунду.
Прелесть алгоритма SwingingDoor в том, что для принятия решения о записи точки не надо помнить о предыдущих данных. Алгоритм принимает решение в реальном времени, чем существенно экономит ресурсы машины.
Если рассматривать алгоритм Дугласа-Пекера, то чтобы отсечь «лишние» точки необходимо в памяти держать координаты всех предыдущих точек(по крайней мере на первом шаге), перебирать все точки ломанной, находить наиболее удаленную и т.д А Инфоконт поступают десятки тысяч таких точек каждую секунду.
Прелесть алгоритма SwingingDoor в том, что для принятия решения о записи точки не надо помнить о предыдущих данных. Алгоритм принимает решение в реальном времени, чем существенно экономит ресурсы машины.
На топкодер сегодня заканчивается марафон. Задача возможно очень похожа на вашу: community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=24042&rd=15038
На основании чего принимаем решение какую дверь крутить для следующей точки не вошедшей в коридор?
Sign up to leave a comment.
Компрессия данных в системах промышленной автоматизации. Алгоритм SwingingDoor