자료구조의 정의
- 자료원소들 간의 논리적 관계를 기술
- 자료 값에 대한 연산을 효율적으로 처리할 수 있도록 조직적(체계적)으로 구성한 것
-
자료구조 성능 비교
- 탐색 성능
- 삽입/삭제 성능
- 순회 성능
-
자료구조의 분류
-
배열
- 배열: 순차탐색
- 정렬된 배열: 이진탐색
-
리스트
- 연결리스트(Linked List) : 순차탐색
-
트리
- 이진트리: 이진탐색
-
탐색트리
- B트리: 이진탐색 또는 다중탐색
- B+트리: 이진탐색 또는 다중탐색
- B*트리 : 이진탐색 또는 다중탐색
-
디지털트리
- 이진트라이: 기수탐색
- 패트리샤트리: 기수탐색
-
사전구조(dictionary)
- 해시
- 요약파일
- 집합
-
-
알고리즘
- 어떤 문제를 해결하기 위해 기술해 놓은 명확한 절차, 일련의 명령(instruction 또는 step) 집합을 의미
-
검색 알고리즘
-
검색 알고리즘의 용도
- 텍스트내에 발견되는 질의(정규식 표현)의 최초위치 탐색
- 텍스트내에 발견되는 모든 질의의 위치 또는 회수 탐색
-
-
여과(filtering) 알고리즘
-
여과 알고리즘의 용도
- 색인 알고리즘 전에 사용
- 텍스트를 표준화 시켜 텍스트의 크기를 줄이거나 탐색을 단순화함.
-
여과 알고리즘의 종류
-
불용어목록(stoplist)
- 불용어를 제거함=일반적인 단어만 남김
- 대소문자변환
- 특수기호/연속공백 제거
- 숫자/날짜 표준화
- 스테밍= 접두사(접미사) 제거
-
-
-
색인 알고리즘
-
색인 알고리즘의 용도
- 빠른 탐색을 위한 자료구조를 만드는것.
-
색인 알고리즘의 종류
- 역파일
- 요약파일
- 트리
-
