Сжатие набора данных методом линейной интерполяции

[Neuling94]

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

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

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

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

[Dmitriy40]

Я похожее делал по другому: брал первые две точки точно, далее для каждой проверял условие попадает ли интерполяция по реально закодированным значениям предыдущих точек в заданные границы и если попадает, то сжимал, если нет, то писал точное значение. Ну и цикл до конца массива точек.
Точность тоже не идеальна, но мне поточный алгоритм был удобнее.

[mihaild]

Я правильно понимаю, что нужно выбрать набор точек такой, чтобы точки между двумя выбранными лежали близко к соединяющему эти две выбранные точки отрезку?
Если да - это вроде делается несложной динамикой (найти минимальное число опорных точек, достаточных для покрытия первых $k$ точек).

[Dmitriy40]

Ещё вариант: фиксировать первую точку точно, потом идти по массиву точек и проверять что все промежуточные (назад от текущей до ближайшей точной) укладываются в ошибку. Как только обнаружим что не укладываются - пишем предыдущую точку точно (а до неё все укладываются в ошибку) и повторяем цикл поиска следующей точки. Последнюю точку тоже пишем точно.
Процесс можно запустить с двух сторон, и с начала и с конца, до момента встречи.
Это уже совсем близко к оптимуму.

[mihaild]

На последовательности скажем $(0, 0), (1, 1), (2, 0), (3, 1)$ и требовании к погрешности "не больше $\frac{3}{4}$" ваш алгоритм возьмет все точки, хотя достаточно взять первую и последнюю.

[Neuling94]

Dmitriy40 в сообщении #1300371 писал(а):

Ещё вариант: фиксировать первую точку точно, потом идти по массиву точек и проверять что все промежуточные (назад от текущей до ближайшей точной) укладываются в ошибку. Как только обнаружим что не укладываются - пишем предыдущую точку точно (а до неё все укладываются в ошибку) и повторяем цикл поиска следующей точки. Последнюю точку тоже пишем точно.
Процесс можно запустить с двух сторон, и с начала и с конца, до момента встречи.
Это уже совсем близко к оптимуму.

Спасибо за идеи, нужно реализовать и потестировать эффективность.

-- 29.03.2018, 15:49 --

mihaild в сообщении #1300370 писал(а):

Я правильно понимаю, что нужно выбрать набор точек такой, чтобы точки между двумя выбранными лежали близко к соединяющему эти две выбранные точки отрезку?
Если да - это вроде делается несложной динамикой (найти минимальное число опорных точек, достаточных для покрытия первых $k$ точек).

Да, правильно, точки между двумя выбранными должны лежать близко к прямой, которая получается в результате интерполяции между выбранными точками.
Подскажите где почитать можно подробнее про "несложную динамику"?

[mihaild]

Динамическое программирование

[Dmitriy40]

mihaild
Хороший контрпример, спасибо. Да, всё так. Но и для динамического программирования можно подобрать плохой пример. Альтернативой с гарантированным оптимальным результатом вижу лишь полный перебор всех вариантов разбиений отрезка на подотрезки и минимизация количества разбиений. Если не ошибаюсь это уже NP полная задача.

[mihaild]

Dmitriy40 в сообщении #1300383 писал(а):

Но и для динамического программирования можно подобрать плохой пример

Если я нигде не обсчитался, то можно за что-то типа $O(N^3)$ находить гарантированно оптимальное (по числу отрезков) решение.
(скорее всего можно и быстрее, но я за две минуты не придумал)

[Neuling94]

mihaild в сообщении #1300385 писал(а):

Dmitriy40 в сообщении #1300383 писал(а):

Но и для динамического программирования можно подобрать плохой пример

Если я нигде не обсчитался, то можно за что-то типа $O(N^3)$ находить гарантированно оптимальное (по числу отрезков) решение.
(скорее всего можно и быстрее, но я за две минуты не придумал)

Можете подробнее описать Вашу идею?)

[mihaild]

Отсортируем точки по абсциссе.
Пусть $f(k)$ - оптимальное число отрезков, покрывающих первые $k$ точек, причем $k$-я точка является концом последнего из этих отрезков. Как вычислить $f(k + 1)$, зная $f(1), f(2), \ldots, f(k)$?
(подсказка: сделав некоторые предварительные вычисления для всех точек, занимающие суммарно $O(N^2)$ времени, можно этот переход научиться делать за $O(k)$)
Как, зная все $f(k)$, найти ответ на задачу? (вот здесь мне $N^2$ не хватает, нужно $N^3$, но сильно сомневаюсь, что это правда необходимо)