[Java] pattern matching (AVL tree, Hash, etc)

소개

자바에서 AVL-tree 및 hash, Linked list를 사용한 pattern matching 프로그램입니다.
프로그램 소스코드와 보고서를 포함합니다.
A+를 받은 과제입니다.

컴파일 실행환경

자바 컴파일러/
보고서에 포함

본문내용

hash table과 AVL tree, Linked-list를 이용하여 string의 pattern matching을 수행한다. 우선 data file 및 pattern file 그리고 output file의 file name을 argument로 입력받아 data file을 각 sub-string 단위로 parsing 하여 hash table에 삽입한 후 patter file의 string과 matching 되는 string이 존재하는 data file 상의 위치를 찾아, output file에 출력한다. 여기에서 sub-string은 data file의 각 line의 sub-string으로 size가 K인 string이다. Hash table의 각 slot은 AVL Tree의 구조로 구성되어 있으며, AVL Tree의 node 구조는 Linked list의 형태로 되어 있다. 같은 sub-string이 반복되어 출현할 수 있으므로 AVL Tree의 Node를 linked list 형태로 설계하며 이때 linked list 상의 각 node들은 같은 string 값을 소유하고 있으나 출현한 위치가 서로 달라 각각의 node로 구분된 형태이다.
이렇게 구성된 hash table을 통해, pattern file에서 입력된 string이 존재하는 위치를 모두 retrieval하는 것이 이 과제의 목적으로, pattern file에서 입력된 string 역시 K-sized sub-string으로 쪼개어 각각의 sub-string들이 모두 hash table의 key와 matching되는 경우를 찾아야 한다. 과제의 spec에서는 K의 값을 6으로 하였으나, 좀더 scalable한 형태로 구현하기 위해 K를 final로 선언하여 K값을 변환하여 사용할 수 있게 하였다.

참고자료

· 없음