Heuristics

Heuristics

self-organizing lists는 패턴에 기반하여 record를 정렬한다.

 

이때 어떻게 정렬할지에 대하여 Heuristic을 사용하게 된다.

자주 사용하는 item을 앞으로 오게 하는 것이 idea이다.

 

 

Heuristics 예

처음에 ABCDEFGH로 정렬된 record를 가지고 있다고 생각해보자.

Access pattern은 F D F G E G F A D F G E 순으로 왔다고 가정하자.

1. Count Heuristic

historical frequency에 기반하여 정렬한다.

Count Heuristic

 

2. Move-to-front Heuristics

최근 access한 record를 제일 앞에 정렬한다.

Move-to-front Heuristic

 

3. Transpose Heuristic

맨 앞으로 옮기는 것이 아닌 바로 앞에 있는 record와 자리를 바꿔준다.

 

Transpose Heuristic

 

 

Text Compression Example

위의 Heuristic을 사용한 예 중 하나가 Text Compression이다.

Move-to-Front heuristic을 이용하여 table을 관리한다.

 

 

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업