座標圧縮

概要

大小順序だけに関心のある値の列があるとする. その長さを \(N\) であるとすると, その順序を保ったまま, 要素を \(0\) 以上 \(N\) 未満の自然数に置き換えることが出来る. 特に大きい座標といった値にこれを適用することで小さい値だけを扱うようにするテクニックを 座標圧縮 という.

全順序集合 \((X, \leq)\) の上の任意の列 \(A = \left(A_0, A_1, \ldots, A_{N-1}\right)\) に対して,

\[f(A) = \left(B_0, B_1, \ldots, B_{N-1} \right)\]

ここで \(B_i\) は自然数で \(0 \leq B_i \lt N\) .

列の要素を大小関係に従ってソートした場合に（同じ値は一つに潰すことにして）何番目の要素になるか, を調べることでこのことは達成できる.

例

\(A=[10, 1000, -100, 1000]\) について \(A_2 < A_0 < A_1 = A_3\) を保存し, 出現する値が最小になるような自然数からなる列は

\[[1,2,0,2]\]

である.

実装

/// misc - Coodinate (Index) Compression (座標圧縮)
pub fn coodinate_compression<T: Clone + Ord>(xs: &Vec<T>) -> Vec<usize> {
    let xset: std::collections::BTreeSet<T> = xs.iter().cloned().collect();
    let xmap: std::collections::BTreeMap<&T, usize> =
        xset.iter().enumerate().map(|(i, x)| (x, i)).collect();
    xs.iter().map(|x| xmap[x]).collect()
}

#[cfg(test)]
mod test_coodinate_compression {
    use crate::misc::coodinate_compression::*;
    #[test]
    fn test_coodinate_compression() {
        assert_eq!(
            coodinate_compression(&vec![1_i64, 2, 3]),
            vec![0_usize, 1, 2]
        );
        assert_eq!(
            coodinate_compression(&vec!['z', 's', 'a']),
            vec![2_usize, 1, 0]
        );
        assert_eq!(coodinate_compression(&vec!["A"]), vec![0]);
    }
    #[test]
    fn test_empty() {
        let v: Vec<u8> = vec![];
        let expected: Vec<usize> = vec![];
        assert_eq!(coodinate_compression(&v), expected);
    }
}