[알고리즘 프로젝트] 단어 유사도 검색기 최종보고서

소개

해시 알고리즘 과 단어파편분석 알고리즘을 이용한
단어유사성 검색기입니다.
파일입출력 기능도 포함되어있습니다.


프로젝트 파일은 따로 업로드되어있습니다.

목차

1. 연구내용 및 추진체계
1) 수행계획서와 실제구현의 차이점
2) 일정표

2. 사용된 알고리즘과 기능
1) 2차원 Hasing을 통한, DataBase 삽입과 검색.
2) 파편화비교 Algorithm을 통한 유사도산출
3) 유사도 순위 선정 Algorithm
4) 문자열 검색 예외처리
5) Gotoxy함수를 이용한 직관적 UI
6) 색상효과로 인한 명확한 정보전달

3. 구현내용
1) 2차원 Hasing을 통한 삽입
2) 2차원 Hasing을 통한, 검색.
3) 단어를 파편화한 후, 파변배열에 저장하는 Algorithm
4) 파편비교 유사도 산출 Algorithm
5) 유사도 순위 설정
6) Gotoxy함수를 이용한 직관적 UI
7) 명확한 정보출력을 위한 색상헤더
8) 검색어 예외처리 기능

4. 실행결과
1) 초기화면
2) 설정화면
3) 검색화면(초기화면)
4) 종료화면( 종료 탭 선택시 )

5. 분석
1) hash_table 삽입
2) hash_table 검색
3) 문자열 파편화 & 저장
4) 단어 유사도 산출
5) 단어유사도 순위결정
6) 입력값 예외처리

6. 결론

본문내용

본 팀은 유사도비교 Algorithm을 구상하는 가장 많은 노력을 하였다. 일반적으로 문자열을 구성하는 문자의 순서와 동일성을 비교한다면 가장 높은 정확성을 지닐 것이다.하지만, 그럴 경우 시간복잡도가 너무 높아진다는 단점이 있다. 만약, 문자의 순서를 무시하고 구성문자의 동일성만 비교한다면, 가령 “Love(사랑)” 이라는 단어와 “vole(들쥐)” 라는 단어를 같은 단어라고 인식하는 문제가 발생하게 된다.본 팀은 유사도비교의 정확성과 시간복잡도라는 두 마리 토끼를 잡기위하여, “단어파편화 비교“라는 방식의 Algorithm을 설계 및 구현하였다. 이 알고리즘은 해단 문자열을 구성하는 단어들을 파현화시켜 동일한 파편이 존재하는지에 대한 비교를 통해, 유사도를 산출하는 Algorithm이다.

<중 략>

검색과정은 1-1에서 설명한 Hashing 과정의 역순이다. 다만, 검색 알고리즘에 있어서본 팀의 알고리즘이 효율적인 시간복잡도를 지니는 이유는, Null값 참조 유무에 따라,해당 검색어가 존재하는 지 없는지를 빠르게 판단할 수 있다는 점이다.해당 검색어의 아스키코드에 Collision이 k번 발생하였을 경우, K+1 번의 조사과정 후반드시 검색을 완료하게 된다.(본 팀의 프로그램에서 평균 Collision은 100미만이다.)

<중 략>

상기 코드는 문자열비교 시, 산출된 유사도를 가지고 유사도 순위를 Update 시키Algorithm이다. Algorithm 설계는 항상 일반적인 경우를 고려해야한다는 점을 생각하여, 순위의 최대 MAX는 5이하이지만, 따로 MAX변수로 설정하여, MAX의 수에 의존 하지 않고 모든 경우에 순위가 유동적으로 변동되는 알고리즘을 설계하게 되었다.함수가 시작되면, 유사도와 문자열을 가진 노드를 생성한다. 그 뒤, 생성한 노드를 포인터 배열에 접근시켜 배열이 Null 경우 삽입, 배열에 있는 노드의 유사도와 비교 후, 포인터 지시를 변경시키는 과정을 가진다.공간복잡도의 효율성을 고려하여, 순위에 포함되지 않거나, 밀려나는 노드를 메모리 반환해주는 기능도 포함되어있다.

참고자료

· 천인국, (C언어로 쉽게 풀어 쓴)자료구조= Data structures in C(생능출판사, 2005)
· 이상진, (열혈강의)자료구조: C로 만드는 자료구조와 적용 알고리즘 해설서(프리렉, 2010)
· 윤성우, 열혈 C 프로그래밍(오렌지미디어, 2010)
· 윤성우, 난 정말 C PROGRAMMING을 공부한 적이 없다구요(오렌지미디어, 2010)
· http://www.c-language.wo.to/ ( C언어 길라잡이, 네이버 카페 )
· http://cafe.naver.com/cafec ( C언어를 배우자, 네이버 카페 )