Chapter 06 ~ 10. 생략

강의16. 정수 데이터를 컴팩트하게 가져가기

큰 정수열을 컴팩트하게 만들면

-> 디스크 I/O를 줄일 수 있다. -> 고속처리 가능

-> RDBMS에 저장하면 아무래도 크기가 늘어나는 데이터를 최소한의 크기로 줄여서 다룰 수 있다.

데이터 형의 크기 등에 의식을 갖는다.

VB Code(Variable Byte Code, 가변길이 바이트 부호)를 사용한다.

예시)

수치	고정길이 바이너리 부호	VB Code
5	00000000 00000000 00000000 00000101	10000101
130	00000000 00000000 00000000 10000010	00000001 10000010

 

강의 17~18은 문제 풀어보는 거랑 코드라서 생략

강의20. 하테나 다이어리의 키워드 링크

하테나 다이어리는 블로그다. 라는 문장을

<a href=”…”>하테나 다이어리</a>는 <a href=”…”>블로그</a>다. 이렇게 링크로 치환해주는 방법.

1. 사전 내에 포함된 모든 단어를 OR조건으로 잇는 정규표현을 만들어서 사용하는 것

-> 처음에는 어휘수도 많지 않고, DB에서 그때그때 정규표현을 만들어서 링크를 하는 처리로도 동작했지만, 키워드 수가 많아짐에 따라 문제가 발생

-> 정규표현을 컴파일하는 처리 -> 캐싱을 통해 어떻게든 회피할 수 있었다.

-> 정규표현에서 패턴 매칭하는 처리 -> ?

정규표현 -> Trie

공통 접두사를 정리함으로써 불필요한 것을 배제하고 있는 것이 Trie의 특징

문자열 집합을 트리구조로 해서 효율적으로 저장한다.

탐색대상 데이터의 공통 접두사를 모아 놓은 트리구조가 된다.

AC법

Trie에서의 패턴 매칭으로 매칭이 진행되다가 도중에 실패했을 경우, 되돌아오는 길의 엣지를 다시 Trie에 추가한 데이터 구조를 사용하는 방법

Regexp::List법 등 여러가지 방법을 이용했다.(고 한다.)

 

키워드 링크 구현, 변이 및 고찰

1. 처음부터 최적의 구현을 사용하는 것이 반드시 옳다고는 할 수 없다는 점,

2. 데이터가 작은 동안에는 오히려 결과도 좋을 것 같다는 점,

3. 데이터가 대규모가 될 시기를 대비해서 본질적인 문제의 해결방법을 준비하지 않으면 곤란하다는 점

 

여기서부터 Chapter10(강의28까지는 다 직접 하는 부분이라서 생략)