Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Сжатие набора данных путем линейной интерполяции
СообщениеДобавлено: 29 мар 2018, 14:12 
Не в сети
Начинающий
Зарегистрирован:
29 мар 2018, 13:48
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте,

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

Дано:
Набор данных {X, Y} , где Х – временные точки, Y – значения в этих временных точках. Так же дано значение погрешности, которая допустима при сжатии данных.

Задача:
Сжать исходный набор данных «выкинув» из него значения, которые могут быть в последствии (при распаковке сжатых данных) получены из оставшихся значений с помощью линейной интерполяции.

Сейчас задача решается таким образом:
Берутся начальное и конечное значения в исходном наборе и анализируются все промежуточные значения между этими двумя точками (выполняется линейная интерполяция отностительно начальной и конечной точек), если хотя бы одно значение не удовлетворяет допустимой погрешности, то набор делится на две части и берутся уже новое начальное и конечное значения (анализируемый набор уменьшается в два раза) и снова производится анализ, если какое-то из значений снова не удовлетворяет погрешности, то опять делим набор на 2 и так далее, пока не найдем набор значений удовлетворяющий погрешности, тогда оставляем только начальную и конечную точки из этого набора. Далее таким же образом анализируем набор оставшихся значений (которые остались после деления на 2) и так далее пока полностью не будет проанализирован весь исходный набор данных.

Для более подробного понимания ниже приведен код реализованной функции на С++ для сжатия буфера с данными.
Входные параметры:
Times - вектор временных точек
Values - вектор значений в этих точках
Результирующий набор данных формируется в структуре resultBuf и в конце переписывается в Times и Values соответственно.
void CompressBuffer(std::vector<double>& Times, std::vector<double>& Values)
{
struct Buffer
{
std::vector<double> Time;
std::vector<double> Value;
};
Buffer resultBuf; // buffer for saving results

size_t SizeOfBuf = Times.size(); // number of elements in input buffer
bool IsOk = true; // true if interpolated values are located in tolerances
int LeftIndex = 0; // index of the left value
int RightIndex = SizeOfBuf - 1; // index of the right value

while (LeftIndex < SizeOfBuf - 1)
{
for (int i = LeftIndex; i <= RightIndex; i++)
{
double InterpolatedValue = Interpolate(Values[LeftIndex], Values[RightIndex], Times[LeftIndex], Times[RightIndex], Times[i]);
if (abs(InterpolatedValue - Values[i]) > abs(Values[i]) * RelativeTolerance + AbsoluteTolerance)
{
IsOk = false;
break;
}
}
if (IsOk == false)
{
RightIndex = (LeftIndex + RightIndex) / 2; // nRightIndex = centre
IsOk = true;
}
else
{
resultBuf.Time.push_back(Times[LeftIndex]);
resultBuf.Value.push_back(Values[LeftIndex]);
LeftIndex = RightIndex;
RightIndex = static_cast<int>(SizeOfBuf) - 1;
if (LeftIndex >= SizeOfBuf - 1)
{
resultBuf.Time.push_back(Times[RightIndex]);
resultBuf.Value.push_back(Values[RightIndex]);
}
}
}
// return results
Times = resultBuf.Time;
Values = resultBuf.Value;
}

double Interpolate(const double LeftVal, const double RightVal, const double TimeLeft, const double TimeRight, const double RequiredTime)
{
return (LeftVal + (RequiredTime - TimeLeft) * (RightVal - LeftVal) / (TimeRight - TimeLeft));
}

Очевидно, что такой подход (с постоянным делением исходного набора на 2) не является хорошим способом с точки зрения эффективности сжатия.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ 1 сообщение ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Погрешность линейной интерполяции

в форуме Численные методы

Semilar

0

701

25 ноя 2014, 10:54

Гарантированная точность при линейной интерполяции

в форуме Численные методы

Jexio

1

361

13 фев 2018, 19:12

Аппроксимация экспер. данных дробно-линейной функцией МНК

в форуме Математическая статистика и Эконометрика

Rinat_88

7

915

17 окт 2014, 07:55

Сдвиг,сжатие,поворот

в форуме Комплексный анализ и Операционное исчисление

ExzoTikFruiT

7

693

03 июн 2014, 19:56

Кодирование и сжатие чисел в контексте

в форуме Информатика и Компьютерные науки

vancivelik

0

638

28 май 2014, 00:46

Сжатие множества натуральных чисел

в форуме Дискретная математика, Теория множеств и Логика

granit201z

7

537

05 июн 2017, 20:38

Расчет ступенчатого бруса на растяжение и сжатие

в форуме Специальные разделы

Sigma

1

461

23 янв 2018, 12:55

Вероятность набора цифр

в форуме Комбинаторика и Теория вероятностей

Alexey759

3

342

04 май 2017, 18:33

Найти ДНФ путем равносильных преобразований

в форуме Дискретная математика, Теория множеств и Логика

Ukiro

2

874

27 фев 2015, 00:46

Найти вероятность правильного набора

в форуме Комбинаторика и Теория вероятностей

kaktus2003

2

148

10 дек 2021, 21:13


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved