알고리즘 특론(과제 4)
- 최초 등록일
- 2012.01.17
- 최종 저작일
- 2010.09
- 9페이지/ 한컴오피스
- 가격 3,000원
소개글
0000대학교 컴퓨터 전공 관련 과목 수강시 작성한 보고서입니다.
알고리즘 특론 과제 중 하나입니다.
세부내용은 목차를 참조 바랍니다.
목차
1. 다음 텍스트 T에 대하여 접미사 나무와 접미사 배열을 각각 그리시오.
2. 다음 텍스트 T를 동적 허프만 코딩으로 압축하시오.
3. 다음 텍스트 T를 LZ78 알고리즘으로 압축하시오.
본문내용
1. 다음 텍스트 T에 대하여 접미사 나무와 접미사 배열을 각각 그리시오.
T = ababcbc
* 접미사 나무 T$=ababcbc$ - Naive 알고리즘
1. T$의 모든 접미사로 이루어진 단어 나무 생성
2. 자식이 하나 밖에 없는 노드를 지우고 합쳐지는 두 간선의 레이블을 합한다.
* 접미사 나무 T$=ababcbc$ - McCreight 알고리즘
- 접미사링크 : 첫 글자를 제외한 스트링을 레이블로 가지는 노드를 의미한다.
- fastfind : 간선의 첫 번째 글자만 일치하면 이후 글자들은 비교하지 않는다.
- slowfind : 나무에 이미 존재하는지 알 수 없을 때 간선의 모든 글자를 비교한다.
- 더 이상 간선을 따라갈 수 없는 위치를 찾으면 이 위치가 headi가 된다.
- 이 위치가 간선의 중간이라면 분할하여 headi에 해당하는 노드를 생성한다.
1. ababcbc$추가
전체 스트링 T에 해당하는 노드 두 개로 시작
2. babcbc$추가
부모 노드가 루트 노드이므로 바로 slow find로 접미사 추가
3. abcbc$추가
a까지 fastfind로 따라간 다음 더 따라갈 수 없으므로 slowfind로 새로운 노드를 추가
4. bcbc$추가
b까지 fastfind로 따라간 다음 더 따라갈 수 없으므로 slowfind로 새로운 노드를 추가
참고 자료
없음