ݺߣ

ݺߣShare a Scribd company logo
CH6. 압축 프로그래밍
왜 압축인가..?
- 압축과 I/O의 고속화
- VB Code(Variable Byte Code)알고리즘
정수 데이터를 컴팩트하게 가져가기
[과제] 정수열이 기록된 CSV를 바이너리로 해서
컴팩트하게 가져가기
정수 데이터를 컴팩트하게 가져가기
- 디스크 I/O를 줄일 수 있다.
- RDBMS의 늘어나는 데이터 크기를 줄일 수 있
다.
- 거대한 정수열을 다룰 때 용이
다룰 데이터 파일
Google adsense 5406393,11616303
issue tracking 541878
정수열을 압축하는 알고리즘
- Unary code
- Gamma (g) code
- Delta (d) code
- VB Code (Variable Byte Code)
*문자열은 Huffman
Gap의 활용
[3, 5, 20, 21, 23, 76, 77, 78]
=>
*오름 차순 정렬
Gap의 활용
[3, 5, 20, 21, 23, 76, 77, 78]
=> [3, 2, 15, 1, 2, 53, 1, 1 ]
- 작은 값이 많아지고 큰값이 적어짐
- 치우친 정도에 따라 압축효과가 다르다
일반적인 숫자의 표현(4bytes)
일반적인 숫자의 표현(4bytes)
VB Code로 바꿔보면..?
VB Code로 바꿔보면..?
0 ≤ x < 128 : 1byte (2^(8-1))
128 ≤ x < 16384 : 2bytes (2^(2(8-1)))
16384 ≤ x < 2097152 : 3bytes (2^(3(8-1)))
대규모 서비스를 지탱하는 기술 ch6
대규모 서비스를 지탱하는 기술 ch6
인코딩
def vb_encode(number):
bytes = []
while True:
bytes.insert(0, number % 128)
if number < 128:
break
number /= 128
bytes[-1] += 128
return pack('%dB' % len(bytes), *bytes)
디코딩
def vb_decode(bytestream):
n = 0
numbers = []
bytestream = unpack('%dB' % len(bytestream), bytestream)
for byte in bytestream:
if byte < 128:
n = 128 * n + byte
else:
n = 128 * n + (byte - 128)
numbers.append(n)
n = 0
return numbers
다른 압축 알고리즘들
- Unary code
- Gamma (g) code
- Delta (d) code
- Unary code
- n을 인코딩을 한다면 (n-1)만큼의 1과 0이 따라
온다.
- Unary code
n / n-1 0
n=1, 0
n=3, 110
n=9, 111111110
- Unary code
n / n-1 0
n=1, 0
n=3, 110
n=9, 111111110
- 간단하고 빠르다.
- n이 크다면..? 글쎄?...
ref
https://gist.github.com/utahta/747472
Ad

Recommended

빈스톡 첫인상 with Git
빈스톡 첫인상 with Git
AWSKRUG - AWS한국사용자모임
UX스튜디오_ 1 인터랙션디자인
UX스튜디오_ 1 인터랙션디자인
jiiiy
비디오 코덱
비디오 코덱
greenday96
Android media codec 사용하기
Android media codec 사용하기
Taehwan kwon
First Impression Rehab: Design Physiology Tips to Boost Conversion
First Impression Rehab: Design Physiology Tips to Boost Conversion
Angie Schottmuller
인터랙션 디자인 사례
인터랙션 디자인 사례
soeun park
1415893 미래세상
1415893 미래세상
Hye Bin Bae
Design Principles: The Philopsohy of UX –- Higher Ed Edition
Design Principles: The Philopsohy of UX –- Higher Ed Edition
Whitney Hess
고급䶥로그래밍_깶윤곤정구찬_로젝트.ٳ
고급䶥로그래밍_깶윤곤정구찬_로젝트.ٳ
RichardJeong2
파이썬 숫자,변수,문자열
파이썬 숫자,변수,문자열
HoYong Na
System+os study 2
System+os study 2
J J
자바 스터디(6기) 1
자바 스터디(6기) 1
Jina Lee
Python 스터디
Python 스터디
sanghyuck Na
파이썬 파일처리 이해하기
파이썬 파일처리 이해하기
Yong Joon Moon
빠르게 활용하는 파이썬3 스터디(ch1~4)
빠르게 활용하는 파이썬3 스터디(ch1~4)
SeongHyun Ahn
Python
Python
J J
이산치수학 Project7
이산치수학 Project7
KoChungWook
01. c and time complexity
01. c and time complexity
승혁 조
022볶수와연산자
022볶수와연산자
Changwon National University
[2009 CodeEngn Conference 03] hkpco - DEFCON CTF 2009 Binary Leetness 100-500...
[2009 CodeEngn Conference 03] hkpco - DEFCON CTF 2009 Binary Leetness 100-500...
GangSeok Lee
문과생 대상 파이썬을 활용한 데이터 분석 강의
문과생 대상 파이썬을 활용한 데이터 분석 강의
Kwangyoun Jung
HTTP 완벽가이드 - ch15. 엔터티, 인코딩 (Entities and Encoding)
HTTP 완벽가이드 - ch15. 엔터티, 인코딩 (Entities and Encoding)
Mungyu Choi
HTTP 완벽가이드 - ch5. web server
HTTP 완벽가이드 - ch5. web server
Mungyu Choi
learning spark - Chatper8. Tuning and Debugging
learning spark - Chatper8. Tuning and Debugging
Mungyu Choi
Chapter3 - learning spark
Chapter3 - learning spark
Mungyu Choi
Elasticsearch server Chapter5
Elasticsearch server Chapter5
Mungyu Choi
JVM과 톰캣 튜닝
JVM과 톰캣 튜닝
Mungyu Choi
조대협의 서버 사이드 - 대용량 아키텍처와 성능튜닝
조대협의 서버 사이드 - 대용량 아키텍처와 성능튜닝
Mungyu Choi
Nodejs 트래픽 라우팅, 파일 서비스, 미들웨어
Nodejs 트래픽 라우팅, 파일 서비스, 미들웨어
Mungyu Choi
nodejs websocket & SOCKET.IO
nodejs websocket & SOCKET.IO
Mungyu Choi

More Related Content

Similar to 대규모 서비스를 지탱하는 기술 ch6 (13)

고급䶥로그래밍_깶윤곤정구찬_로젝트.ٳ
고급䶥로그래밍_깶윤곤정구찬_로젝트.ٳ
RichardJeong2
파이썬 숫자,변수,문자열
파이썬 숫자,변수,문자열
HoYong Na
System+os study 2
System+os study 2
J J
자바 스터디(6기) 1
자바 스터디(6기) 1
Jina Lee
Python 스터디
Python 스터디
sanghyuck Na
파이썬 파일처리 이해하기
파이썬 파일처리 이해하기
Yong Joon Moon
빠르게 활용하는 파이썬3 스터디(ch1~4)
빠르게 활용하는 파이썬3 스터디(ch1~4)
SeongHyun Ahn
Python
Python
J J
이산치수학 Project7
이산치수학 Project7
KoChungWook
01. c and time complexity
01. c and time complexity
승혁 조
022볶수와연산자
022볶수와연산자
Changwon National University
[2009 CodeEngn Conference 03] hkpco - DEFCON CTF 2009 Binary Leetness 100-500...
[2009 CodeEngn Conference 03] hkpco - DEFCON CTF 2009 Binary Leetness 100-500...
GangSeok Lee
문과생 대상 파이썬을 활용한 데이터 분석 강의
문과생 대상 파이썬을 활용한 데이터 분석 강의
Kwangyoun Jung
고급䶥로그래밍_깶윤곤정구찬_로젝트.ٳ
고급䶥로그래밍_깶윤곤정구찬_로젝트.ٳ
RichardJeong2
파이썬 숫자,변수,문자열
파이썬 숫자,변수,문자열
HoYong Na
System+os study 2
System+os study 2
J J
자바 스터디(6기) 1
자바 스터디(6기) 1
Jina Lee
파이썬 파일처리 이해하기
파이썬 파일처리 이해하기
Yong Joon Moon
빠르게 활용하는 파이썬3 스터디(ch1~4)
빠르게 활용하는 파이썬3 스터디(ch1~4)
SeongHyun Ahn
Python
Python
J J
이산치수학 Project7
이산치수학 Project7
KoChungWook
01. c and time complexity
01. c and time complexity
승혁 조
[2009 CodeEngn Conference 03] hkpco - DEFCON CTF 2009 Binary Leetness 100-500...
[2009 CodeEngn Conference 03] hkpco - DEFCON CTF 2009 Binary Leetness 100-500...
GangSeok Lee
문과생 대상 파이썬을 활용한 데이터 분석 강의
문과생 대상 파이썬을 활용한 데이터 분석 강의
Kwangyoun Jung

More from Mungyu Choi (18)

HTTP 완벽가이드 - ch15. 엔터티, 인코딩 (Entities and Encoding)
HTTP 완벽가이드 - ch15. 엔터티, 인코딩 (Entities and Encoding)
Mungyu Choi
HTTP 완벽가이드 - ch5. web server
HTTP 완벽가이드 - ch5. web server
Mungyu Choi
learning spark - Chatper8. Tuning and Debugging
learning spark - Chatper8. Tuning and Debugging
Mungyu Choi
Chapter3 - learning spark
Chapter3 - learning spark
Mungyu Choi
Elasticsearch server Chapter5
Elasticsearch server Chapter5
Mungyu Choi
JVM과 톰캣 튜닝
JVM과 톰캣 튜닝
Mungyu Choi
조대협의 서버 사이드 - 대용량 아키텍처와 성능튜닝
조대협의 서버 사이드 - 대용량 아키텍처와 성능튜닝
Mungyu Choi
Nodejs 트래픽 라우팅, 파일 서비스, 미들웨어
Nodejs 트래픽 라우팅, 파일 서비스, 미들웨어
Mungyu Choi
nodejs websocket & SOCKET.IO
nodejs websocket & SOCKET.IO
Mungyu Choi
정렬(버블정렬,선택정렬,삽입정렬)
정렬(버블정렬,선택정렬,삽입정렬)
Mungyu Choi
c++ API디자인 ch9. 발표자료
c++ API디자인 ch9. 발표자료
Mungyu Choi
b+tree
b+tree
Mungyu Choi
Hdfs
Hdfs
Mungyu Choi
hadoop ch1
hadoop ch1
Mungyu Choi
A tour of go
A tour of go
Mungyu Choi
Ch11. server infra
Ch11. server infra
Mungyu Choi
4.1 단일호스트의 부하
4.1 단일호스트의 부하
Mungyu Choi
Chap4_2
Chap4_2
Mungyu Choi
HTTP 완벽가이드 - ch15. 엔터티, 인코딩 (Entities and Encoding)
HTTP 완벽가이드 - ch15. 엔터티, 인코딩 (Entities and Encoding)
Mungyu Choi
HTTP 완벽가이드 - ch5. web server
HTTP 완벽가이드 - ch5. web server
Mungyu Choi
learning spark - Chatper8. Tuning and Debugging
learning spark - Chatper8. Tuning and Debugging
Mungyu Choi
Chapter3 - learning spark
Chapter3 - learning spark
Mungyu Choi
Elasticsearch server Chapter5
Elasticsearch server Chapter5
Mungyu Choi
조대협의 서버 사이드 - 대용량 아키텍처와 성능튜닝
조대협의 서버 사이드 - 대용량 아키텍처와 성능튜닝
Mungyu Choi
Nodejs 트래픽 라우팅, 파일 서비스, 미들웨어
Nodejs 트래픽 라우팅, 파일 서비스, 미들웨어
Mungyu Choi
nodejs websocket & SOCKET.IO
nodejs websocket & SOCKET.IO
Mungyu Choi
정렬(버블정렬,선택정렬,삽입정렬)
정렬(버블정렬,선택정렬,삽입정렬)
Mungyu Choi
c++ API디자인 ch9. 발표자료
c++ API디자인 ch9. 발표자료
Mungyu Choi
4.1 단일호스트의 부하
4.1 단일호스트의 부하
Mungyu Choi
Ad

대규모 서비스를 지탱하는 기술 ch6