2021-11-16 17:13 작성
비손실 압축 방법
대량의 데이터 처리를 위한 알고리즘으로 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현함.
- “aabbaccc”: “2a2ba3c”
- “ababcdcdababcdcd”: “2ababcdcd”
- “abcabcdede”: “2abcdede”
메모
생각 1. 그렇다면 데이터의 길이에 따라 압축 방법이 달라지는 알고리즘을 사용한다면 압축된 데이터를 복구시킬 때 기준도 따로 저장해놓아야 복구가 가능하지 않나?
아래와 같은 이유로 데이터 복구의 기준이 보안의 key가 될 수 있을 것이라고 생각한다.
생각 2. 만약 알파벳이 아닌 숫자로 동일한 압축 방법을 사용한다면?
숫자의 중복 개수 만큼 알파벳으로 단위를 세는 것도 가능하다고 생각한다.
예를 들면,
b0는 숫자 0을 2개 가지고 있는 것으로 계산하는 방식이다.
이것을 이용해 알파벳 방식과 같이 사용하게 되면 예측이 힘든 id 값을 만들 수 있을 것이다.
3ab2cd000c66 = abababcdcd000666666
생각 3. 그렇다면 이 방법을 어디서에서 활용할 수 있을까? 수 십, 수 백만 개의 데이터를 처리한다고 했을 때, 데이터 당 1개의 문자열만 늘어나도 전체 데이터 개수만큼 처리할 분량이 늘어난다.
예를 들어, 최대 1만의 길이를 가진다고 봤을 때, 숫자 혹은 숫자 + 문자로 조합한다고 해도 결국에는
1 <= x <= 10000의 문자열 길이를 그대로 서버에 저장하게 된다. 그러나 문자열로만 지정한다고 하면 위와 같이 나올 수 있는 범위는 같지만 중복 되는 문자열을 압축하므로 서버에 저장되는 값을 상당히 감소시킬 수 있을 것이다.
따라서 이 알고리즘은 간단한 id를 설정하는 것부터 시작해서 데이터를 예측 가능한 범위에서 관리할 수 있게 하는 알고리즘이라고 생각한다.
예시
function solution(s) {
// 2a2ba3c: 7 (1개 단위), 2ababcdcd: 9(8개 단위), 2abcdede: 8(3개 단위)
// 자르는 범위 최소: 1, 최대: 문자열 길이
// 최소 단위부터 최대 단위까지 잘라 가며 그 다음의 값과 비교하고 같은 것을 묶어 "숫자 + 알파벳" 형태로 변환
let answer = slice(s);
console.log(answer); // { optLength: 7, optKey: 1 }
return answer.optLength;
}
const slice = (s) => {
// 자르기 단위로 완성한 문자열 저장
let prev = s;
let post = "";
// 최적 자르기 단위
let key = 0;
// 자르기 단위 정하기
for (let i=1; i<=s.length; i++) {
// 자른 단위로 이전 값과 비교 하기 위한 변수
let compare = "";
let count = 1;
// 자르기 단위 별로 looping
for (let k=0; k < s.length; k+=i) {
// 이전 문자와 같으면 count를 올리고 그렇지 않으면 compare에 새 문자 할당
if (compare === s.slice(k, k+i)) {
count ++;
} else {
post += (count > 1 ? count : "" ) + compare;
count = 1;
compare = s.slice(k, k+i);
}
// 마지막 범위에서 출력
if ((k+i) >= s.length) {
post += (count > 1 ? count : "" ) + compare;
count = 1;
}
}
if (prev.length >= post.length) {
prev = post;
key = i;
post = "";
} else post = "";
}
return { optLength: prev.length, optKey: key };
}