�ݺ�ߣ

영남대학교 전자공학과 21611
engine
DongdongE
영남대학교 전자공학과 21611591 김난희
영남대학교 전자공학과 21611663 이주형

1. 검색 알고리즘 & 자료구조
trial
2. 검색 알고리즘
choice
3. 순서도
4. 전체 함수 구성
5. 파일 입출력
목차
6. 사용한 자료 구조
choice
map1 / map2 / map3
7. 각 단계별 소요 시간
8. Result
9. 추가적으로 보충한 것, 해야할 것
DongdongE

검색 알고리즘 trial (worst case를 생각해봅시다)
1. 검색한 단어의 순서가 중요할까?
→ 처음 나온 단어가 중요할수록 더 좋은 검색 결과를 나타낼 수 있을까?
“동성로 맛집”검색 → 동성로………햄버거 폐업 (X)
2. 검색한 단어가 많이 나올 수록 좋을까?
“동성로 맛집”검색 → 경대병원역 맛집……동성로 노래방 (이전보단 결과가 좋아졌다)
3. 검색한 단어의 순서가 앞에 있을 수록 and 많이 나올 수록 좋을까?
“동성로 맛집”검색 → 동성로…(무슨?..경대병원역)맛집…배달 (이전보단 결과가 좋아졌다)
DongdongE

검색 알고리즘 trial 정리
“동성로 맛집” 검색하면
의미: 동성로에 있는 맛집을 검색
1. 동성로에서 놀다가 다른 지역 맛집을 들렸다.
2. 동성로의 방탈출 카페를 검색
3. 칠곡 3지구의 맛집을 검색
“컴퓨터 포맷” 검색하면
의미: 컴퓨터를 포맷하는 방법이 궁금하다
(직접 포맷>수리점 포맷) 직접 포맷 방법이 어렵거나 번거로우면
수리점 포맷을 알고 싶다.
1. 컴퓨터 직접 포맷하는 방법은 ………이다.
2. 컴퓨터가 바이러스가 생겨……… 수리점에 맡겨 포맷했다.
ex 1
ex 2
DongdongE

자료 구조 trial
Doc 3
Seq 5
Doc 5
Seq 11
Doc 9
Seq 15
Doc 1 Doc 4
Doc 5
가게 가까워지다 가입자
Doc 2
Seq 11
Doc 3
Seq 15
Doc 6
1. Sublist Merge
3 1 4
1 3 4
2. 배열 정렬 삽입
1 2 3 3 4 5 5 6 9
Doc 3
Seq 5
Doc 5
Seq 11
Doc 9
Seq 15
Doc 1 Doc 4
Doc 5
Doc 2
Seq 11
Doc 3
Seq 15
Doc 6
3. 가중치 합 분산 고려
Doc 3
Seq 5
Doc 5
Seq 11
Doc 9
Seq 15
Doc 1 Doc 4
Doc 5
Doc 2
Seq 11
Doc 3
Seq 15
Doc 6
3 2 1
DongdongE

✓ 1순위: 한 문서에 검색 키워드가 많은 순
✓ 2순위: 분산이 적은 순
✓ 3순위: 단어 입력 순서 고려
우리가 선택한 검색 알고리즘
“동성로 맛집” 검색하면
의미: 동성로에 있는 맛집을 검색
1. 동성로 맛집을 들렸다. 맛집의 이름은…
2. 칠곡 3지구에서 동성로 맛집을 가는 길이다.
…
15. 동성로와서 영화보고…칠곡 3지구의 맛집에 가는 길이다.
…
30. …동성로 카페…
31. …맛집…
Q. 분산이 적다는 것은?
하나의 문서안에서
단어가 멀리 떨어진 정도가 적다
worst case
ex 1
DongdongE

순서도 및 전체 함수 구성
Textinput()
Document.txt 입력
StringEngine()
SearchEngine();
semi_scoring();
dd_engine();
map 1 구성
검색
map 2 ~ map 3
구성
결과 출력
insert()
var_seq()
insert_scoring()
textprint()
map1에 단어(댕글댕글 멤버: doc 번호, seq 번호) 삽입 함수
text파일에서 읽어와 단어, doc,
doc 내부의 순서(Sequence)를 삽입하는 함수
검색기에 입력한 문자열을 처리하는 함수
단어 존재 여부를 따져 map2에 댕글댕글 달기
map2(doc 번호가 map, seq가 댕글댕글 벡터)에 달린 벡터들을
참조해서 분산을 계산하고, map3로 넘겨주는 역할
document 내부에 있는 검색한 단어들의 분산 조사
map3, 구조체(링크드리스트)에 삽입
searching 최종 결과 출력 함수 text로 부터 doc 번호와 단어를 알 경우 위치를 찾아
line을 출력하는 함수
DongdongE

파일 입출력
팩03 간판02 기념일 임시02 자04 서투르다 멍멍01 방법 노래01 줄다 필요성 규칙적 돼지고기 한
복 의외로 종업원 운반02 닭 도자기 조깅 육체적 아버님 유교02 닫히다 광주 품01
벽06 이상05 머리01 자다01 종이컵 담임 갈다01 얘기 한층 수입품02 차06 보도하다02 생산되다
대책03 전통적 굉장히 짙다02 불평등하다 종교적 인사02 팀01
seq+1 seq+1
doc+1
DongdongE

텍스트파일로부터 정리한
단어 map
(멤버: doc 번호,
doc안에서 단어의 순서 seq)
map 1
사용한 자료 구조
map 2 map 3
검색한 단어에 대해 정리한
doc 번호 map
seq 8 seq 1 seq 2
(멤버: seq 번호)
마지막으로 doc 최종 정렬을
구현한 doc 개수 map
(멤버: doc 번호, var 분산)
doc1 doc3 doc4
seq8 seq1 seq2
var1 var3 var4
doc8 doc1 doc2
map
1
map
2
map
3
DongdongE

NULL
NULL
NULL
NULL
NULL
map 1 자료구조
가게 가까워지다 가입자 가을01 가지다
Doc 3
Seq 5
Doc 4
Seq 11
Doc 11
Seq 15
Doc 7 Doc 9
map 1
int:
doc번호, seq 순서
구조체
링크드
리스트
string: 단어명
관련 함수: textinput(): text파일에서 읽어와 단어, doc, doc 내부의 순서(Sequence)를 삽입하는 함수
insert(): map1에 단어(댕글댕글 멤버: doc 번호, seq 번호) 삽입 함수
DongdongE

map 2 자료구조
Doc 3 Doc 4 Doc 7 Doc 8 Doc 11
Seq 5
Seq 11
Seq 15
Seq 7 Seq 9
map 2
관련 함수: var_seq(): document 내부에 있는 검색한 단어들의 분산 조사
semi_scoring(): map2(doc 번호가 map, seq가 댕글댕글 벡터)에 달린 벡터들을 참조해서
분산을 계산하고 map3로 넘겨주는 역할(map3와 구조체(링크드리스트)에 삽입)
int: seq 순서
int: doc 번호
Int형
벡터
이유: map2는 seq만 댕글 달림--> 이건 seq 개수로 doc 개
수를 세아릴 수 있고, 여러 seq로 부터 분산도 계산할 수 있음
DongdongE

NULL
NULL
NULL
NULL
NULL
map 3 자료구조
검색 알고리즘
분산이용
1 2 3 4 5
var 13
var 90
var 92
var 44
var 9
Doc 90
var 14
var 8
Doc 99
var 14
Doc 48
var 88
Doc 23
var 2
Doc 3
map 3
구조체
링크드
리스트
int: doc 개수
관련 함수:insert_scoring(): map3, 구조체에 삽입
dd_engine(): searching 최종 결과 출력 함수
int
doc 번호, var 분산
DongdongE

각 단계별 소요시간
Textinput()
Document.txt 입력
StringEngine()
SearchEngine();
semi_scoring();
dd_engine();
Textprint()
검색결과 출력
검색 단어
걷다03
설악산
걷다03 설악산
걷다03
설악산
걷다03 설악산
line 출력 여부 O X
(1) map 1 구성시간 36.617 36.329 36.433 36.953 36.373 36.626
(2) 검색 문자열 처리 0.000 0.000 0.000 0.000 0.000 0.001
(3) 단어 존재 여부 따져
map2~map3 구성시간
0.007 0.003 0.004 0.007 0.003 0.003
(4) 결과 출력 시간
(15개 DOC 출력 기준)
18.233 2.393 1.322 0.021 0.021 0.023
(초단위(sec))
1
2
4
3
DongdongE

Result
햄버거 단어 하나 검색
걷다03 설악산 검색
설악산 걷다03 검색
→ 순서도 고려함
1
2
3
DongdongE

추가적으로 보충한 것
단어 15개씩만 출력하고
더 검색할지 결정하기
없는 단어와 있는 단어를
함께 검색할 경우
없는 단어와 유사한 단어를
있는 단어의 doc에서 검색
(no!)
없는 단어와 있는 단어를
함께 검색할 경우
없는 단어와 유사한 단어를
있는 단어의 doc에서 검색
(yes!)
4
5
6
DongdongE

추가적으로 더 하면 좋을 것
UI1
C++에서
원래 하려고 했던 것
네이버나 구글 이미지를 띄우고
그 위에 글자를 출력하기
C++ → Python 로해서
web 프레임워크 사용하기
2 시간 단축 방법
line을 print할때 오래걸림
메모리를 적게 사용하는 대신 시간을 소요함
python은 자체적으로 메모리를 잡아주나,
c++을 동적할당도 결국은 직접 잡아줘야함
동적할당은 데이터영역에 선언된 배열 변수보다 느림
이에 절충안으로 메모리를 적게 사용하며 시간을 적게
소요하는 방법 더 고려
DongdongE

�ݺ�ߣ

Searching algorithm(nanheekim)

Recommended

More Related Content

Similar to Searching algorithm(nanheekim) (20)

More from Nanhee Kim (15)

Searching algorithm(nanheekim)