Making Index

문제

한 권의 책을 입력받아 그 책에 대한 인덱스를 만드는 프로그램을 작성하라.

책은 하나의 텍스트 파일로 주어진다. 인덱스는 책에 등장하는 모든 단어들의 목록이다. 단어들은 사전순으로 정렬되어야 하고, 또한 각각의 단어에 대해 텍스트 파일에서 그 단어가 등장하는 모든 라인 번호들을 함께 보여주어야 한다.

하지만 실제로 모든 단어들을 인덱스에 포함할 필요는 없다. 가령 the, is, this 등과 같은 단어들은 대부분의 책에서 매우 많이 등장하지만 인덱스에 포함할 가치는 없다. 또한 등장 횟수가 매우 작은 단어들도 일반적으로 그다지 중요한 단어가 아니라고 할 수 있으므로 인덱스에서 제외한다.

어떤 단어를 인덱스에 포함할것인지는 다음의 규칙에 따른다.
1. Noise Word : 가령 is, the, this 등과 같이 인덱스에 포함하지 않을 단어들의 리스트가 주어진다.
2. 길이가 2 이하인 단어는 제외한다. (가령 is, a, as 등)
3. 책 전체에 등장 빈도가 5번 이하인 단어들은 제외한다.


방법

모든 단어들에 대해서 등장 빈도를 카운트해야 한다. 따라서 입력 파일에서 한 단어씩 읽어들이면서, 현재까지 등장한 모든 단어들의 목록과 각 단어의 등장 빈도를 적절한 자료구조에 저장해야 한다.

새로운 단어가 들어올 때마다 그 단어가 기존의 목록에 있는지 아니면 처음으로 등장한 단어인지를 검사한다. 기존의 목록에 있는 경우 그 빈도를 1 증가시키고, 아닌 경우 새로 목록에 추가한다. 물론 그 단어가 Noise Word인지 먼저 검사해야 한다.

이러한 목적에 가장 적합한 자료구조 중의 하나가 Red-Black 트리이다. 단어의 목록을 red-black 트리로 저장하라. 또한 Noise Word들은 하나의 배열에 정렬하여 저장하여 이진검색을 이용하여 어떤 단어가 Noise Word인지 검사할수 있게 하라. 모든 단어의 목록이 완성되면 이제 등장 빈도가 5이하인 단어들을 모두 Red-Black 트리에서 제거한다.

그런 다음 화면에 프롬프트를 제공하고 다음과 같은 사용자의 command를 처리하도록 한다.
1. showall : 인덱스에 포함된 모든 단어들과 그 단어가 등장하는 라인번호를 화면에 출력한다.
2. find XXX : 단어 XXX를 red-black트리에서 검색하여 그 단어가 등장하는 라인번호를 화면에 출력한다.
3. exit : 프로그램을 종료한다.


구현

Logic : 확인 안해봄
GUI :

초기 실행화면

파일 불러오기

불러온 화면. 도움말의 색인의 모양을 빌려보았다.

MakingIndex.zip