어제 전철 타고 집에 돌아오는 길에 문득 생각난 알고리즘입니다.

제가 지난번에 쓴 글에 이어지는 '대용량 멀티 미디어 데이터의 추가 압축'에 대한 것입니다.

자세한 내용...

제가 요즘 고민하고 있는 것은, 어떻게 하면 비슷한 패턴들이 반복적으로 발생하는 것을 알아 낼 수 있을까? 하는 것입니다. 흔히 사용되는 zip, rar 같은 압축 알고리즘들은 '반복되는 패턴을 찾아내서 반복을 줄이는' 방법을 사용해서 압축을 하고 있습니다. 이 경우, 정확하게 똑같은 값이 반복되지 않으면 반복으로 인식하지 않는 다는 점을 좀 개선해서, '비슷한 것이 반복되는 것'을 인식해서 반복 패턴은 더 많이 찾아내자 라는 것이 기본 아이디어입니다.

그래서 고민의 촛점은, '비슷하다'라는 것에 대한 정의 문제와, 비슷한지 아닌지를 계산 해내는데에는 천문학적인 계산 시간이 소요되기 때문에 속도를 개선해야한다는 문제입니다.

우선, 아래 그림을 봐주세요. 두 그림이 서로 다른 부분이 있뎁니다.
어디가 틀린지는 포토샵에 넣고 비교해보니까 몇군데 발견됩니다.

근데, 한눈에 어디가 다른지 알아볼 수 없는 이유는, 그림 사이즈가 너무 크기 때문입니다.

아래와 같이 사이즈를 줄여서 보면,
차이점이 안보이기는 마찬가지입니다만;;;;; ㅋㅋ

컴퓨터의 입장에서 보면, 두가지는 매우 다른 상황이 연출됩니다.

즉, 커다란 그림을 대상으로 두 그림이 비슷한지 여부를 확인하려하면, 천문학적인 계산 시간이 소요되지만, 그 그림을 적당히 오차를 무시하면서 강제로 축소 시켜서 비교하면, 연산 시간이 매우 단축된다는 것입니다. (게임에서 '충돌'을 검출할때 사용하는 트릭과 비슷하다고 할 수 있겠습니다.)

게다가, 제가 찾는 반복 패턴은 '오차'를 어느 정도 무시하는 '비슷한 패턴'을 찾는 것에 촛점이 있는 것이기 때문에, 그림 사이즈를 축소하는데서 발생하는 오차가 오히려 제가 원하는 '비슷한' 것의 효과를 낸다는 장점이 있습니다.

아직은 여기까지가 제가 얻은 아이디어라서, 좀 더 생각을 해보면 뭐가 더 나올것 같습니다.

근데, 이렇게 생각을 자꾸 하니까, 구현이 엄청 하고 싶은데, 3월달에는 시간이 안나네요...ㅋㅋ