座標圧縮備忘録 - おはやし日記

座標圧縮、なるアルゴリズムに出会いました。どうにかわかったつもりになったので記録しておきます。自分用メモ的な精度。

座標圧縮とは

詳しくは参考のサイトを見てください。

簡単に言うと、「座標の広い範囲に散らばっている点について、その相対的な位置を変えずに狭い範囲に集める」という技です。

さらに自己流に解釈すると、「注目したい点をリスト化する」という感じだと思いました。

例えば、座標軸にいくつか（$ N $個）の点を載せたいとします。点が乗っている時true、無い時falseとしましょう。$ 0 \le \rm{座標} < 10000 $ とします。

int N;cin>>N;
vector<bool> z(10000, false);
for(int i=0; i<N; i++){
  int a;cin>>a;
  z[a] = true;
}
......

//input
5
3 19 11 24 13

範囲が小さければこれで済みますが、$-10^{9} \le \rm{座標} \le 10^{9}$ とかになるとどうしようもありません。

//input
5
24680 515 -12345678 3 12345678

このとき、

value = {-12345678, 3, 515, 24680, 12345678};
index = {3, 2, 0, 1, 4};

とすれば $i$ 番目の入力はvalue[index[i]]とやって求められます。

1次元だとあんまりありがたみがないような気がしますが、2次元の領域を扱うととても嬉しくなれます。

メモリ上で実際に触る範囲が要素数オーダーに減る！

実装

とりあえず1つの配列について。

template<class T>
vector<T> compress(vector<T> &V){
  //Vを圧縮後の値にする 元の値を得るために重複削除ソート列であるSを返す
  vector<T> S = V;
  sort(S.begin(), S.end());
  S.erase( unique(S.begin(), S.end()), S.end() );
  for(int i=0; i<V.size(); i++){
    V[i] = lower_bound(S.begin(), S.end(), V[i]) - S.begin();
  }
  return S;
}

vector S = V;
入力されたVはインデックスに変換してしまうので、もともとの値を（ソートして）保存しておく配列が必要
sort(S.begin(), S.end());
バラバラに入力された数字をソートする
S.erase( unique(S.begin(), S.end()), S.end() );
uniqueは、配列の中で重複するものの2つ目以降を配列の後ろに押しやり、その「余り物」の先頭のイテレータを返す
eraseは、指定された範囲の要素を削除する
結果として、重複している要素が削除される
V[i] = lower_bound(S.begin(), S.end(), V[i]) - S.begin();
lower_boundで、「ソート&重複削除」された配列の中でV[i]を指すイテレータを返す
それから先頭のイテレータを引き算することで、「何番目か」がわかる

使用例1

#include <bits/stdc++.h>
using namespace std;

/**
 * 座標圧縮
 * */

namespace /* ZahyoComp.cpp */ {
  template<class T>
  vector<T> compress(vector<T> &V){
    //Vを圧縮後の値にする 元の値を得るために重複削除ソート列であるSを返す
    vector<T> S = V;
    sort(S.begin(), S.end());
    S.erase( unique(S.begin(), S.end()), S.end() );
    for(int i=0; i<V.size(); i++){
      V[i] = lower_bound(S.begin(), S.end(), V[i]) - S.begin();
    }
    return S;
  }
}

#define rep(i, n) for(int i=0; i<(int)n; i++)

int main(){
  int N;cin>>N;
  vector<int> input(N);
  rep(i,N)cin>>input[i];
  
  vector<int> S = compress(input);

  cout<<"compressed : RawData"<<endl;
  for(int i: input){
    cout<<i<<" : "<<S[i]<<endl;
  }
}

//input
7
100 120 120 130 115 115 150

//output
compressed : RawData
0 : 100
2 : 120
2 : 120
3 : 130
1 : 115
1 : 115
4 : 150

*/

[追記] もともと入力が入っていたinputが、「その入力が（重複削除ソートの）何番目か」を表す配列に化けていることに注意！その代わりS[input[i]]で元々の値を復元できている。

使用例2

詳細は座標圧縮の解説（1次元から2次元の圧縮まで） | アルゴリズムロジックを参考に。

ここでは、同じ軸に乗った複数の座標をまとめて圧縮する

template<class T>
vector<T> compress(vector<T> &V1, vector<T> &V2){
  //2つのVを一緒くたにして各々圧縮する 重複削除ソート列Sを返す
  vector<T> S;
  int N = V1.size();
  copy(V1.begin(), V1.end(), back_inserter(S));
  copy(V2.begin(), V2.end(), back_inserter(S));

  sort(S.begin(), S.end());
  S.erase( unique(S.begin(), S.end()), S.end() );
  for(int i=0; i<N; i++){
    V1[i] = lower_bound(S.begin(), S.end(), V1[i]) - S.begin();
    V2[i] = lower_bound(S.begin(), S.end(), V2[i]) - S.begin();
  }
  return S;
}