Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element
[cite]10.1.1.85.6173[/cite]
1. Introduction
Running Maximum-minimum (MAX-MIN) filter 문제라는 것이 있습니다. $ a_1, \dots, a_n $ 의 배열이 주어질 경우, 크기 w를 갖는 모든 창에 대하여, 창 내에서의 최대값과 최소값을 찾는 문제입니다. 이러한 Max-MIN filter는 신호 처리나 패턴 인식에서 유용하게 쓰이는 알고리즘입니다.
2. Related Work
3. Lower Bounds on the Number of Comparisons
4. The Novel Streaming Algorithm
Running MAX-MIN filter를 계산하기 위해서 monotonic wedge라는 것을 이용합니다. monotonic wedge란 현재 창 범위내에서의 최소값과 최대값의 위치로 구성된 범위를 이야기합니다. 이 monotonic wedge를 창 이동에 따라 계속 갱신시켜주면 현재 위치에서의 최대/최소값을 쉽게 구할 수 있게 됩니다.
monotonic wedge는 두개의 리스트 $ U, L $의 원소들에 의하여 구성됩니다. 이 리스트는 double-ended queue로, 계산 과정에서 앞, 뒤로 원소를 추가하고 제거하면서 갱신하게 됩니다. 하지만 다음과 같은 규칙성을 갖습니다. 만약 $ U, L $의 첫번째 원소 $ U_1, L_1 $가 전체 배열에서의 최대/최소값의 위치라고 한다면, 이어 다음에 올 원소 $ U_2, L_2 $는 위치 이후로부터의 최대/최소 값의 위치, 즉 $ (U1, \inf), (L1, \inf) $ 범위에서의 최대/최소값의 위치를 그 값으로 갖습니다. 나머지 이어지는 원소들 또한 동일한 규칙을 갖습니다.
그리고 갱신은 다음과 같은 규칙성을 갖습니다.
- $ a_2, \dots, a_n $ 의 monotonic wedge를 계산하려고 할 때, $ U_1, L_1 $이 1이라면 해당 원소는 해당 원소는 U와 L에서 제거한다.
- $ a_1, \dots, a_{n+1} $ 의 monotonic wedge를 구하려고 할 때, $ a_{n+1} \gt a_n $ 이라면 $ a_{n+1} $보다 큰 값을 만날 때 까지 U의 원소를 제거한다. 또는 $ a_{n+1} \lt a_n $이라면 $ a_{n+1} $보다 작은 값을 만날 때 까지 L의 원소를 제거한다. 위의 과정을 거치고 나면 U와 L의 끝에 n+1을 추가한다.
설명으로 풀어놓으니 복잡한 것 같지만 알고리즘을 뜯어보면 생각보다 단순합니다.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
INPUT: an array a indexed from 1 to n INPUT: window width > 2 U, L = emtpy double-ended queues, we append to back append 1 to U and L for i in [2, ..., n]: if i >= w + 1 then OUTPUT: a_front(U) as maximum of range [i-w, i) OUTPUT: a_front(L) as minimum of range [i-w, i) if a_i > a_i-1: pop U from back while a_i > a_back(U): pop U from back else: pop L from back while a_i < a_back(L): pop L from back append i to U and L if i == w + front(U) then pop U from front else if i == w + front(L) then pop L from front |
첫번째 부분은 시작 지점을 넘어서면 monotonic wedge의 첫번째 원소들을 MAX, MIN 값으로 리턴하는 부분입니다.
그 다음에는 위의 규칙에 대한 내용입니다. 배열을 탐색하면서 직전보다 큰 숫자를 만나면 U에서 그보다 작은 숫자는 빼 버립니다. 작은 숫자를 만나면 마찬가지로 L에서 그보다 큰 숫자는 빼버립니다. 그리고 U, L 양쪽에 숫자를 집어넣습니다. 이런 과정을 통하여 현재 윈도내에서의 큰/작은 값이 두 리스트 U/L의 맨 앞에 오도록 유지가 될 수 있습니다.
마지막으로 윈도의 크기를 벗어난 원소들은 제거를 해버립니다.
이렇게 과정을 거치기 때문에 첫번째 원소를 선택하면 무조건 윈도에서 큰 원소를 선택할 수 있습니다. 저자는 최악의 경우에도 3n의 계산을 넘지 않는다고 이야기하고 있습니다. 자세한 증명은 논문에 나와있으니 참고하시기 바랍니다.
5. Implementation and Experimental Results
C++의 STL에는 deque를 제공하기 때문에 비교적 쉽게 구현이 가능합니다. 필요한 deque의 크기는 윈도의 크기 w를 넘지 않습니다.