Здравствуйте,

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

Дано: Набор данных {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) не является хорошим способом с точки зрения эффективности сжатия.

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

задан 29 Мар '18 15:45

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2

задан
29 Мар '18 15:45

показан
234 раза

обновлен
29 Мар '18 15:45

Связанные вопросы

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru