Microsoft PowerPoint - Chap6 [호환 모드]

Size: px

Start display at page:

Download "Microsoft PowerPoint - Chap6 [호환 모드]"

지효 지
5 years ago
Views:

1 Data Structure (Chapter 6: Graphs) Sprig, 2 Sookmyug Womeʼs Uiv. Departmet of Multimedia Sciece Prof. Youg-Ho Park

2 Graph 관련주요용어 ( 참고 ) Complete graph : a graph i which there is a edge betwee every pair of vertices. Udirected 경우 edge의수 : (-)/2 Directed 경우 edge의수 : (-) Path : graph G의 vertex v i 에서 v j 에이르는 vertex의순서 simple path: 서로다른정점으로구성된경로 ( 처음과끝정점은같아도됨 ) cycle: 처음과끝정점이같은단순경로 Degree : vertex 에연결된 edge 의수 udirected graph 인경우 idegree / outdegree 로구분 Coected Graph : 임의의 vertex v i 와 v j 모두 path 가존재한경우 Youg-Ho Park Sook Myug Wome's Uiv. 2

3 Graph 관련주요용어 ( 참고 ) Adjacecy Matrix ( 인접행렬 ): vertex의수가 인그래프에서 * 의 2차원배열 (A) 로서 (v i, v j ) 가 E(G) 에속하면 A(i,j)=이되고속하지않으면 A(i,j)=인행렬. b a d a c a b c d a b c d b c a b c a b c Youg-Ho Park Sook Myug Wome's Uiv. 3

4 Graphs 6..2 정의 그래프 (graph) G 는 공집합이아닌정점 (vertex) 들의유한집합 (fiite set) 과 공집합도허용하는간선 (edge) 들의유한집합 (fiite set) 이다. V : 유한한정점 (vertex) 들의집합 E : 간선 (edge) 들의집합 : 정점의쌍집합 Youg-Ho Park Sook Myug Wome's Uiv. 4

5 Graphs Graph - G = (V,E) V(G) : 공집합이아닌정점 (vertex) 들의유한집합 E(G) : 간선 (edge) 의집합 ( 정점의쌍 ) - 무방향 (udirected) 그래프 (v, v) = (v, v) : 무순서 à 순서상관안함 방향 (directed) 그래프 : digraph 라부른다. <v, v> <v, v> : 순서 head tail head tail Youg-Ho Park Sook Myug Wome's Uiv. 5

6 Graphs G, G2 : 무방향그래프 G3 : 방향그래프 (a) G (b) G (c) G 2 3 V(G)={,,2,3} E(G)={(,),(,2),(,3),(,2),(,3),(2,3)} V(G2)={,,2,3,4,5,6} E(G2)={(,),(,2),(,3),(,4),(2,5),(2,6)} V(G3)={,,2} E(G3)={<,>,<,>,<,2>} <,>: 번노드에서 번노드로의방향성 edge 표현 Youg-Ho Park Sook Myug Wome's Uiv. 6

7 Graphs 그래프의제한점 - V(G), E(G) = 집합 (a) self loop (edge) 는허용안됨 (a) (b) 간선의중복은안됨 : 만약있으면, 다중그래프 (multi-graph) (a) Graph with a self edge (b) Multigraph Youg-Ho Park Sook Myug Wome's Uiv. 7

8 Graphs - 정점무방향그래프 - 간선의최대수 = (-)/2 완전 (complete) 그래프 - 정점방향그래프 - 간선의최대수 = (-) (v, v) E(G) v 과 v 은인접 (adjacet) (v, v) 정점 v, v 에서로에부속 (icidet o) <v, v> v 은 v 으로부터인접 (adjacet from) v 은 v 에인접 (adjacet to) G 의부분그래프 G' V(G') V(G) E(G') E(G) Youg-Ho Park Sook Myug Wome's Uiv. 8

9 Graphs (a) G (b) G (c) G (i) (ii) (iii) (iv) (a) some of the subgraphs of G (i) (ii) (iii) (iv) (b) some of the subgraphs of G3 Youg-Ho Park Sook Myug Wome's Uiv. 9

10 Graphs 경로 (path) : 정점 ( 간선 ) 들의연속 - 경로의길이 : 경로상의간선수 - 단순경로 (simple path) : 서로다른정점으로구성된경로 ( 처음과끝정점은같아도됨 ) - 사이클 (cycle) : 처음과끝정점이같은단순경로 - directed path, directed cycle ( 방향그래프의경우 ) 연결 (coected) 그래프, G - vi, vj V(G) vi 에서 vj 로의경로존재 연결요소 (coected compoet, 다음페이지그림참고 ) : - 최대연결부분그래프 (maximal coected sub-graph) 트리 : coected 이고, 사이클없이연결된그래프 (acyclic graph) Youg-Ho Park Sook Myug Wome's Uiv.

11 Graphs 강력연결그래프 (strogly coected graph) G - 모든쌍의정점들사이에상호방향경로 ( 양방향모두 ) 존재 vi, vj V(G) 방향경로 vi vj, vj vi 존재 강력연결요소 (strogly coected compoet) - 강하게연결된최대부분그래프 2 연결요소 (coected compoet) : - 최대연결부분그래프 (maximal coected sub-graph) (c) G 3 - 예 : G4는 2개의 coected compoet를가진그래프이다. - 예 : Gs는 2개의 strogly coected compoet를가진그래프이다. H 4 H Gs G4 Youg-Ho Park Sook Myug Wome's Uiv.

12 Graphs 정점의차수 : 정점 (vertex) 에부속한간선 (edge) 의수 - 방향그래프 v 의진입차수 (i-degree) : v 가간선의머리 : V2 으로유입 v 의진출차수 (out-degree) : v 가간선의꼬리 :V 에서나감 V V2 e = ( - å d i ) / 2, d i 는정점i의차수 Youg-Ho Park Sook Myug Wome's Uiv. 2

13 Graphs 그래프표현 : 그래프를 Mai Memory 내에어떻게표현할것인가? (i) 인접행렬 (adjacecy matrix) 배열 : adj_mat adj_mat[i][j] = : (vi, vj) or (vj, vi) E(G), 즉, edge 가있으면 adj_mat[i][j] = : otherwise 즉, edge 가없으면 무방향 : 대칭, 방향 : 비대칭 공간 2 - 무방향그래프 : (-)/2 로감소 ( 상위삼각행렬 ) vi 의차수 ( 무방향 ) : adj_mat[i][j] 방향그래프 - 행 i 의합 = 방향그래프에서 vi 의진출차수 ( 가로로숫자를센다 ) - 열 j 의합 = 방향그래프에서 vj 의진입차수 ( 세로로숫자를센다 ) Youg-Ho Park Sook Myug Wome's Uiv. 3

14 Youg-Ho Park Sook Myug Wome's Uiv (a) G (b) G 3 (c) G 4 Graphs (a) G (c) G 3 2 H H2 G4

15 Graphs 인접리스트 (adjacecy list) list로표현해보자 개의연결리스트 ( 헤드노드 ) v i : v j lik vi 에인접 무방향그래프 (e : 간선의수 ) : 2e개의리스트노드 방향그래프 : e개의리스트노드 Youg-Ho Park Sook Myug Wome's Uiv. 5

16 Graphs - 다음페이지에그림이있음 #defie MAX_VERTICES 5 /* 정점의최대수 */ typedef struct ode * ode_poiter; typedef struct ode { i vertex; struct ode *lik; }; ode_poiter graph [MAX_VERTICES]; it =; /* 현재사용중인정점들 */ 연결리스트노드의순차적저장 : 배열 ode[ ] - ode[i] = 정점 i 에대한리스트의시작지점 - ode[] = + 2e + - 정점와 i 인접한정점 ode[i],, ode[i+]-에저장 ( i<) Youg-Ho Park Sook Myug Wome's Uiv. 6

17 Graphs HeadNodes data lik [] 3 2 [] 2 3 [2] 3 [3] 2 (a) G HeadNodes [] [] 2 [2] (b) G3 HeadNodes [] 2 [] 3 [2] 3 [3] 2 [4] 5 [5] 6 4 [6] [7] weighted graph = etwork (c) G Youg-Ho Park Sook Myug Wome's Uiv. 7

18 Navigatio of graphs 그래프탐색연산 깊이우선탐색 (depth first search, DFS) - 아래로아래로탐색해나간다. - pre-order tree traversal과유사하다. 넓이우선탐색 (bread first search, BFS) - 같은 level에있는옆동료 vertex들을먼저탐색해나간다. - level-order tree traversal과유사하다. 이것을배우는이유 G 의 v 에서도달할수있는모든연결요소를발견해내기위해 Youg-Ho Park Sook Myug Wome's Uiv. 8

19 Graphs 그래프탐색연산 : 깊이우선탐색 (depth first search, DFS) G=(V, E) : 무방향그래프, 노드 v 에연결된모든정점을방문하는방법 자료구조 - visited[max_vertices] : 배열 ( 초기치 = FALSE) - visited[i] = TRUE : 정점 i 방문 - 인접리스트 Youg-Ho Park Sook Myug Wome's Uiv. 9

20 Graphs #defie FALSE #defie TRUE short it visited[max_vertices]; void dfs(it v) { /* 그래프의정점 v에서시작하는깊이우선탐색 */ ode_poiter w; visited[v] = TRUE; pritf("%5d", v); for (w=graph[v]; w; w=w->lik) if (!visited[w->vertex]) dfs(w->vertex); } Youg-Ho Park Sook Myug Wome's Uiv. 2

21 DFS 동작방법 시작 vertex v 방문 V 의 adjacet list 에서방문하지않은 vertex w 를선택한후, w 에대하여 DFS 를 recursive 하게수행한다. Graphs (a) DFS 방문순서 :,, 3, 7, 4, 5, 2, 6 BFS 방문순서 :,, 2, 3, 4, 5, 6, 7 [] [] [2] [3] [4] [5] [6] [7] (b) Youg-Ho Park Sook Myug Wome's Uiv. 2

22 Graphs 넓이우선탐색 (breadth first search, BFS) /* 자료구조는다음과같다 */ typedef struct queue *queue_poiter; typedef struct queue { it vertex; queue_poiter lik; }; void addq(queue_poiter *, queue_poiter *, it); it deleteq(queue_poiter *); Youg-Ho Park Sook Myug Wome's Uiv. 22

23 void bfs(it v) { /* 정점 v 에서시작하는너비우선탐색. 전역배열 visited 는 } 으로초기화됨. 큐연산은 4 장에서기술한것과유사함 */ ode_poiter w; queue_poiter frot, rear; frot = rear = NULL; /* 큐의초기화 */ pritf("%5d", v); visited[v] = TRUE; addq(&frot, &rear, v); while (frot) { } v = deleteq(&frot); for (w=graph[v]; w; w=w->lik) if (!visited[w->vertex]) { } pritf("%5d", w->vertex); addq(&frot, &rear, w->vertex); visited[w->vertex] = TRUE; Graphs BFS 동작방법 Vertex v 에서시작하여 v 의 adjacet list 에있는모든 vertex 들을방문하고, 방문한 vertex 는모두 queue 에넣고, 방문했음을표시함 Queue 에서 vertex 하나를꺼집어내서이 vertex 의 adjacet list 에서방문하지않은모든 vertex 들을방문한다. Queue 가모두빌때까지이과정을계속한다. Youg-Ho Park Sook Myug Wome's Uiv. 23

24 Graphs 연결요소 (coected compoet) G 의모든연결요소를발견 DFS 나 BFS 의사용 void coect(void) { /* 그래프의연결요소결정 */ it i; for (i=; i<; i++) if (!visited[i]) { dfs(i); pritf("\"); } } Youg-Ho Park Sook Myug Wome's Uiv. 24

25 Graphs 신장트리 (spaig tree) G의신장트리 T - 트리 : E(T) E(G) V(T) = V(G) ( E(T) = -) miimal subgraph ( 간선의수가최소 ) ) (a) DFS() spaig tree (b) BFS() spaig tree Youg-Ho Park Sook Myug Wome's Uiv. 25

26 Graphs 이중결합요소와단절점 G : 무방향연결그래프 단절점 (articulatio poit) : v V(G) - 정점 v 와부속간선제거 두연결요소로분리 이중결합그래프 (bi-coected graph) - 단절점을갖지않는연결그래프, 즉, 이미분리된하나의그래프 이중결합요소 (bi-coected compoet) - 최대이중결합부분그래프 (maximal bicoected subgraph) Youg-Ho Park Sook Myug Wome's Uiv. 26

27 Graphs Youg-Ho Park Sook Myug Wome's Uiv. 27

28 Miimum cost spaig tree 최소비용 (miimum cost) 신장트리 간선의비용합이최소인신장트리 - 갈망법 (Greedy algorithm) - 최적의해를단계별로구하고, 각단계에서최상의결정을내림 Kruskal 알고리즘 ( 참고만 ) - 사이클을형성하지않는 - 개의간선을오름차순으로선택 Youg-Ho Park Sook Myug Wome's Uiv. 28

29 ( 참고 ) Kruskal s algorithm T = { }; while (T가 -개미만의간선포함 && E가비어있지않음 ) { E에서최저비용간선 (v, w) 선택 ; E에서 (v, w) 를삭제 ; if ((v, w) 가 T에서사이클을형성하지않음 ) (v, w) 를 T에추가 ; else (v, w) 를거부 ; } if (T가 -개보다적은간선을포함 ) pritf("no spaig tree\"); Youg-Ho Park Sook Myug Wome's Uiv. 29

30 ( 참고 ) Kruskal s algorithm (a) (b) (c) (d) (e) (f) E 의 sort Heap Sort, Quick Sort O(e log e) 연결이되어서 cycle 을이루는가? 두정점이이미동일한집합에있다면 cycle 임 (g) (h) uio-fid 연산이용 Youg-Ho Park Sook Myug Wome's Uiv. 3

31 ( 참고 )Prim s algorithm - 각단계에서선택된간선의집합 = 트리 T = { }; TV = {}; /* 정점 으로시작. 간선은비어있음.*/ while (T의간선수가 -보다적음 ) { u TV이고 v TV인최저비용간선을 (u, v) 라함 ; if ( 그런간선이없음 ) break; v를 TV에추가 ; (u, v) 를 T에추가 ; } if (T의간선수가 -보다적음 ) pritf("no spaig tree\"); Youg-Ho Park Sook Myug Wome's Uiv. 3

32 ( 참고 )Prim s algorithm Youg-Ho Park Sook Myug Wome's Uiv. 32

33 ( 참고 )Shortest Paths 최단경로 (shortest path) - Edsger Dijkstra 가해결알고리즘제안 - Dijkstra algorithm 이란말로유명 단일출발점모든도착지 (sigle source all destiatios) - v(source) 에서다른모든정점 ( 도착지 ) 까지의 최단경로를찾자! - 경로길이의증가순 ( 방향그래프에서 ) Youg-Ho Park Sook Myug Wome's Uiv. 33

34 ( 참고 )Shortest Paths Path Legth ), 3 2), 3, ), 3, 4, 45 4), 2 45 (a) graph (b) shortest paths from Youg-Ho Park Sook Myug Wome's Uiv. 34

35 ( 참고 )Shortest Paths 가중치 (weight) = 양의값 : adjacet : ot adjacet foud[i] : if foud[i]=true vi 까지의최단경로발견 distace[i] : v 에서 S 내의정점만을거친 vi 까지의최단거리 (S= 최단경로가발견된정점의집합 ) - 초기치 : distace[i] = cost[][i] - cost[i][j] : <i, j> 의가중치 그래프 : 비용인접행렬 (cost adjacecy matrix) 로표현 최단경로 i - k = (vi,..., vj, vk) shortest + shortest shortest Youg-Ho Park Sook Myug Wome's Uiv. 35

36 ( 참고 )Shortest Paths Repeat () select i such that foud[i]=false distace[i] = mi{distace[j]} j, foud[i]=false (2) foud[i] TRUE ( S S {vi} ) (3) j, s.t. foud[j] = FALSE distace[j] mi{distace[j], distace[i]+cost[i][j]} ( adjust all distaces i distace, which are ot i S) Youg-Ho Park Sook Myug Wome's Uiv. 36

37 ( 참고 )Shortest Paths #defie INT_MAX void shorestpath(it v, it weight[][max_no_vertices], it distace[], it, short it foud[]) { it i, mipos, w, mi; for (i=;i<;i++) { foud[i]=false; distace[i]=cost[v][i]; } foud[v] = TRUE; distace[v] = ; for (i=; i<-2; i++) { mi = INT_MAX; mipos = -; for (w=;w<;w++) if (distace[w] < mi &&!foud[w]) { mi = distace[w]; mipos = w; } foud[mipos] = TRUE; for (w=;w<;w++) if (!foud[w]) if (distace[mipos]+cost[mipos][w] < distace[w]) distace[w] = distace[mipos]+cost[mipos][w]; } } Youg-Ho Park Sook Myug Wome's Uiv. 37

38 Data Structure (Chapter 8: Hashig) Sprig, 2 Sookmyug Womeʼs Uiversity Departmet of Multimedia Sciece Prof. Youg-Ho Park

39 빠른저장및검색데이터구조 지금까지, 배운것은무엇인가? 데이터 () 저장방법및 (2) 검색구조에대해배웠다 순차성을극복한, tree 구조등이빠르고좋다고배웠다 그럼, tree보다더빠르고효과적인구조는없는가? 있다! à Hash Structure! (Hashig 하자!) Youg-Ho Park Sook Myug Wome's Uiv. 2

40 우리주변에는이런큰건물들을자주볼수있다. 멋진건물이구나 그런데, 여기서사람을찾기가여간힘든것이아니다. 어떻게하면, 그이를빨리찾을수있을까 Youg-Ho Park Sook Myug Wome's Uiv. 3

41 앗, 관리인아저씨다 ~! 그렇다. 우리는이분의힘을빌려야한다. 그런데, 가끔이분이제역할을못하면, 헛수고다. Youg-Ho Park Sook Myug Wome's Uiv. 4

42 박종칠 (A 군 ) A 군과 B 군의숙박기 매니져 박질주 (B 군 ) 방있나요?? 이분이매니져슈퍼맨아저씨다! 힘쎄고, 아직쓸만하다. 매니져가이들에게어떤방을결정할까? 결정을기다려보자. Youg-Ho Park Sook Myug Wome's Uiv. 5

43 매니져의방배정결과 Youg-Ho Park Sook Myug Wome's Uiv. 6

44 숨겨진그이를찾고싶다 요기 ~ 음 나만이 B 를찾을수있어 ~ 박질주 (B) 씨는어디있나요? 잠깐기다려봐요아가씨 ~ f (B) à 층 2 호실 층을가서찾아보면 2 호를찾을수있습니다. 거기에 B 의실체가있다! Youg-Ho Park Sook Myug Wome's Uiv. 7

45 본예제등장인물의역할분석 Bucket: 이것은 slot 이 3 개짜리임 박종칠데이터의 key 값 (A) 해쉬함수 (Hash Fuctio) 박질주데이터의 key 값 (B) 질의 ( 검색요청 ) Bucket 을가진 Hash 구조 Youg-Ho Park Sook Myug Wome's Uiv. 8

46 내옷이랑똑같은옷이어디있나요? 7 번복도를찾아보세요 우리주위에는 Hash 의개념이많이있다. 이때, 역시필요한것은현명한 guider 이다. Youg-Ho Park Sook Myug Wome's Uiv. 9

47 Hash Structure! (Hashig 하자!) 란? Hash? 사전 : 다진고기요리, 다지다, 잘게썰다 Hashig? 데이터를잘게나누어보관하고, 보관한방법대로찾는기법 Three Major Factors i Hashig?. Hash Structure ( 기본 Hash 구조를어떻게잡을까?) 2. Hashig Fuctios ( 똑똑한함수 : 골고루분산 ) 3. Overflow Solutios ( 넘치는문제를현명하게해결하는법 ) 4. à We lear the key features havig woderful efficiecy! Youg-Ho Park Sook Myug Wome's Uiv.

48 해싱 (Hashig) 레코드 : 주소 애트리뷰트 ( 기본키를가지고 ) à 파일내의레코드를찾아냄가능한주소공간 >> 실제주소공간 > 레코드의수논리적 - 물리적독립성 키값들은주소공간에독립적키값은그대로두고해쉬함수만조정 해싱함수 (hashig fuctio) 키공간을주소공간으로사상 (mappig) 주소 ß hash( 키 ) 주소 유효키공간 Sook Myug Wome's Uiv.

49 Hash i Mai Memory? Hard Disk? Hash 는 Mai Memory Hard Disk à 모두에서사용되는구조이다. 그러므로, Hash Structure i Mai Memory Hash File i Hard Disks 라는용어를쓴다. 본내용에서는특별한경우에만파일을언급한다. Sook Myug Wome's Uiv. 2

50 해싱의특성 해싱 (hashig) 키에서변환되어나온주소에레코드를저장하는과정 ( 기법 ) 해싱에서의레코드검색방법 키 ( 를가지고 ) à 주소 ( 를찾아감 ) à 레코드접근 ( 해서 data 를얻어냄 ) 순차화일 : 레코드수가많으면, 수에비례해서탐색시간많이걸림해싱 : 반드시그런것만은아님 해쉬구조설계시고려해야하는사항들 버켓크기 : 화일에서같은주소에포함될수있는레코드수 적재율 : ( 저장된화일의레코드수 / 버켓의총용량 ) 해싱함수 : 주소생성을위한변환절차 오버플로해결기법 : 버켓의오버플로우 Sook Myug Wome's Uiv. 3

51 버켓 (bucket) 크기 버켓 (bucket) 이란? 어떤 key를가지고함수를통과한, 같은해싱주소를가지는파일의한구역한버켓에는여러개의하나레코드가들어갈수있음 하나의물리적레코드 : 한번의접근으로채취가능한레코드개수 충돌 (Collisio) 이란? 2개의레코드가동일버켓으로해슁될때, (2번째를포함해서 ) 2번째이후의레코드가버켓으로삽입됨으로인해발생하는기본현상을말함동거자 (syoym) - 동일주소로해싱된 2개이상의키는서로동거자임오버플로우 (overflow) 한버켓이 syoym으로가득찬현상을말함 버켓크기를증가시키면 à 즉, 버켓크기를크게키우면 오버플로우가발생할확률이감소됨그러나, 버켓내에레코드가많아지므로, 레코드탐색시간이증가됨 Sook Myug Wome's Uiv. 4

52 적재밀도 (loadig desity) () 파일을 full 로유지 ( 밀도높이면 )? à 논리적접근 ( 비교 ) 수가증가 빈공간을증가시키면 ( 밀도낮추면 )? à 기억장소의비효율을가져옴 홈버켓 (home bucket) 해싱함수에주소생성됨 이주소에있는것을홈버켓이라고함 적재밀도 (loadig desity) ( 파일의레코드수 ) / ( 홈버켓의총용량 ) 7% 이상이면충돌급증 à 홈버켓을다채우지말고, 7% 이하로데이터를채워야충돌이적다! Sook Myug Wome's Uiv. 5

53 적재밀도 (loadig desity) (2) 예상오버플로우확률? N : 홈버켓의개수 C : 각버켓의용량 K : 화일에저장된레코드수 K 적재밀도 = < C N 예 : 3% 를빈공간으로목표하고자한다면 K: 레코드수 : 6, 개 C: 버켓크기 ( 용량 ) : 2 (2개의 record가들어갈수있도록함 ) N: 홈버켓수 = (6,/2) x.7 = 7,43 개 à 오버플로우비율 : 2.3 % ( 뒤 page 표참조 ),278 오버플로우레코드에대한예비 Sook Myug Wome's Uiv. 6

54 예상파일오버플로비율 버켓크기 적재밀도 (%) = 버켓이레코드로얼마나채워져있는지의비율 % 개 % Sook Myug Wome's Uiv. 7

55 해쉬주요사항 (Three Major Factors) 해쉬테이블 ( 구조 ) 해쉬함수 오버플로우해결책 Youg-Ho Park Sook Myug Wome's Uiv. 8

56 정적 (Static) Hashig Idetifiers: 저장할것들 x f(x) = a hash fuctio hash table a Bucket 주소 bucket X 를여기에저장하면됨 X 같은것이한 bucket 에여러개들어갈수있음 ( slots) Youg-Ho Park Sook Myug Wome's Uiv. 9

57 해쉬테이블 Hash tables - store the idetifiers i a fixed size table called a hash table 2 s- 2 b buckets, ad s slots i each bucket b- Youg-Ho Park Sook Myug Wome's Uiv. 2

58 ( 참고 ) 해쉬테이블 Def) - Idetifier desity of a hash table: /T where : umber of idetifiers i table T: total umber of possible idetifiers - Loadig desity or loadig factor of a hash table: a = /(s b) where s: umber of slots i each bucket b: umber of bucket Youg-Ho Park Sook Myug Wome's Uiv. 2

59 ( 참고 ) 해쉬테이블 - Two idetifiers i ad i2 are syoyms with respect to f, if f(i) = f(i2) where i ¹ i2 - A overflow occurs whe we hash a ew idetifier, i, ito a full bucket - A collisio occurs whe we hash two o-idetical idetifiers ito the same bucket - Collisios ad overflows occur simultaeously iff bucket size is Youg-Ho Park Sook Myug Wome's Uiv. 22

60 ( 참고 ) 해쉬테이블 예 ) hash table ht with b=26, s=2, = hash 함수 f - st character of idetifier slot slot acos ata 2 char ceil 3 defie 4 exp 5 float floor 6 25 Idetifiers acos defie float exp char ata ceil floor clock ctime hash table with 26 bucket ad two slots per bucket Youg-Ho Park Sook Myug Wome's Uiv. 23

61 해쉬함수 requiremets for a hash fuctio - easy to compute - miimizes the umber of collisio (but, we ca ot avoid collisios) uiform hash fuctio ( 목표 ) - for radomly chose x from the idetifier space, P[f(x)=i] = /b, for all buckets i - a radom x has a equal chace of hashig ito ay of the b buckets Youg-Ho Park Sook Myug Wome's Uiv. 24

62 해싱함수 변환함수 : 키 à 버켓주소해싱함수계산시간 << 보조기억장치의버켓접근시간모든주소에대한균일한분포 주소변환과정 키가숫자가아닌경우정수값 (A) 으로변환키 A 2 3 변환된정수값 (A) 을주소공간의자리수만큼의정수값 (B) 으로변환 A B ( 균일분포, 예 : 4자리 ) 해싱함수 얻어진정수값 (B) 을주소공간의실제범위에맞게조정 B 주소 ( 주소공간의크기, 예 : 7 번지까지 ) Sook Myug Wome's Uiv. 25

63 펭귄 의 Hashig 핵심정리 - 제산잔여 원 : 레코드 Key x, y, z, 등을가진레코드전체집합 ( 실세계 ) z z: key y F (x) à 통과시 bucket 주소생성 à 생성주소는우측 ~4 이내 à 주소로해당레코드이동 - 중간제곱 - 중첩 - 숫자분석 - 숫자이동변환 - 진수변환 - ( 참고 ) Exclusive-OR 법 ㅠ 넘침 x 7% 채움 Memory 연속주소공간 ( 이걸나눠서 bucket 으로 ) 채움의목표 : 골고루분산 개방주소법 : 기본및이차집중현상을해결하는 static 공간 rehashig 법 폐쇄주소법 : 넘치는레코드를동적 chaiig, 동적 rehashig 하는법 채움의주체 : 해쉬함수 몰려넘치면 : 개방, 폐쇄주소법 Sook Myug Wome's Uiv. 26

64 ( 참고 ) 해쉬함수 : mid-square 방법 ( 중간제곱해싱 ) - middle of square hash fuctio - frequetly used i symbol table applicatios hash fuctio fm )squarig the idetifier 2)obtai the bucket address by usig a appropriate umber of bits from the middle of the square 3)if we use r bits, 2 r buckets are ecessary Youg-Ho Park Sook Myug Wome's Uiv. 27

65 해싱함수 중간제곱해싱 (Mid square hashig) 키값을제곱하여중간에서 개의숫자를취함 주소범위 ( ) 에맞춤 *.7 = 6588 ( < 주소 7 ) Sook Myug Wome's Uiv. 28

66 중간제곱해싱예 키값 키제곱 상대주소 ** 충돌 ** 6 Sook Myug Wome's Uiv. 29

67 해쉬함수 : Divisio(modular) 방법 ( 제산잔여해싱 ) - use the modulus(%) operator fd(x) = x % M where M: table size - rage of bucket address: ~ M- - the choice of M is critical - choose M as a prime umber such that M does ot divide r k ±a for small k ad a - choose M such that it has o prime divisors less tha 2 Youg-Ho Park Sook Myug Wome's Uiv. 3

68 해싱함수 - 제산잔여해싱 주소 = 키값 mod 제수 제수 - 제수 예 ) 제수가 2 일경우, 53 % 2 = ( 번지 ) 직접주소공간의크기를결정 ( 제수 -) 제수 > 파일의크기 충돌가능성이가장적은것으로선택 소수 2보다작은소수를인수로갖지않는, 비소수 Sook Myug Wome's Uiv. 3

69 제산잔여해싱의적재율과성능 적재율 실제레코드의수 = 적재할수있는최대레코드의수 적당한성능 최대허용치 :.7.8의적재율 레코드 à (.25 * ) 의주소공간을가지고있어야 à bucket.7.8의적재율을유지할수있다. Sook Myug Wome's Uiv. 32

70 제산잔여해싱예 키값 상대주소 *** 충돌 *** 제수 =53 Sook Myug Wome's Uiv. 33

71 해쉬함수 : Foldig 방법 ( 중첩해싱 ) )shift foldig ex) idetifier x = x x2 x3 x x )foldig at the boudaries x x = 897 Youg-Ho Park Sook Myug Wome's Uiv. 34

72 해싱함수 - 중첩 (Foldig) 중첩 (foldig) 해싱 키값을주소와같은자리수를가지는몇개의부분으로나눔접어서합을구함경우에따라제일높은자릿수버림 예 ) 키값 ( ), 주소크기 (4) 버림 Sook Myug Wome's Uiv. 35

73 중첩해싱예 키값 상대주소 ** 충돌 ** 274 ** 충돌 ** Sook Myug Wome's Uiv. 36

74 해쉬함수 : Digit Aalysis 방법 ( 숫자분석 ) - used i case all the idetifiers are kow i advace - examie the digits of each idetifier - delete those digits that have skewed distributios - select the digit positios to be used to calculate the hash address Youg-Ho Park Sook Myug Wome's Uiv. 37

75 해싱함수 - 숫자분석 키값이되는숫자의분포이용 키의모든자리수에대한빈도테이블 주소로사용될숫자의위치들을선택 균일한분포 ( 같은빈도수 ) Sook Myug Wome's Uiv. 38

76 ( 참고 ) 해싱함수 - Exclusive-OR 변환 키의길이가길때 제산잔여방법을적용하기전에수행한키를두세그먼트로나눔두세그먼트를입력으로비트레벨 Exclusive-OR 수행 EX-OR : procedure (arg, arg2) Retue((arg OR arg2) AND (NOT(arg AND arg2))); END EX-OR; Addr = EX-OR(Keypart, Keypart2); Ex-OR('RA', 'MA') = Ex-OR('MA', 'RA') 장점 : 빠른연산 ( 연산을하드웨어적으로수행 ) Sook Myug Wome's Uiv. 39

77 해싱함수 - 숫자이동변환 중앙을양분 2 안쪽으로 shift 3 주소범위에맞도록조정 ( 조정상수 ) 키 : 주소길이 d d2 d3 d4 d5 d6 d7 d8 주소공간 : *.5 = 3456 실제주소 예키 : 주소 : Sook Myug Wome's Uiv. 4

78 해싱함수 - 진수변환. 키값의진수를다른진수로변환 2. 초과하는높은자리수를절단 예 ) 7248 : 키값 주소공간 : 7 진수 : 변환 = 보정 : 6373 *.7 = 446 Sook Myug Wome's Uiv. 4

79 오버플로해결방법 오버플로 삽입할레코드가꽉찬버켓에해싱될때 해결방법 개방주소법폐쇄주소법 개방주소법 계산접근법탐색할버켓의주소를동적으로계산 폐쇄주소법 ( 체인법 ) 자료구조접근법오버플로버켓을체인으로홈버켓에연결 Sook Myug Wome's Uiv. 42

80 오버플로해결기법 - () 개방주소법 (ope addressig) 선형조사 (liear probe) 다음의빈공간을순차적으로탐색 A i = f(i, 키 ) i =,,2,... ex) A i = (i step + hash( 키 )) mod N 삽입방법 : A i 버켓이만원이면 A i+ 고려 빈자리가있는버켓일때까지반복 탐색방법 : 찾는레코드가 A i 에없으면 A i+ 탐색 레코드를찾거나빈버켓일때까지반복 문제점 : 집중 (clusterig) 레코드가전체버켓에골고루분산되지않고특정지역에집중됨 두가지종류의집중 (clusterig) 기본집중 (primary clusterig) 이차집중 (secodary clusterig) Sook Myug Wome's Uiv. 43

81 기본집중 (primary clusterig) 정의 처음어떤버켓에해시된레코드를처리하기위해조사하는버켓들이똑같은순서에따라두번째버켓에해시된레코드들에의해서도사용됨 예 : 홈버켓의수 N=3 경우 A i = (i*3 + hash(key)) mod 3 여러키에대한버켓들의주소 sequece Hash(key) 값이 25, 28, 인키들은같은 sequece 가짐 버켓 25 에오버플로나면버켓 28 조사 ; 버켓 28 이오버플로될확률증가 Hash(key) 값이 7,, 3인키들은같은 sequece 가짐한키에대한주소 sequece 에서같은 A i 가나오면같은 A i+ 나옴 Sook Myug Wome's Uiv. 44

82 선형조사 (liear probe) 의문제점 선형함수를사용하기때문에같은 sequece 나옴 해결책 : 비선형조사 (o-liear probe) A i = (i * 3 + i 2 * 5 + hash(key)) mod 3 조사순서 ( 표 8.6) 선형의경우와다른점 여러키에대해서같은 A i 가나오더라도 A i+ 은다름 한키에대한주소 sequece 에서같은 A i 가나오더라도다른 A i+ 나옴 Sook Myug Wome's Uiv. 45

83 제 2 차집중 (secodary clusterig) 비선형조사의문제점 여러키가일단같은홈버켓에사상되면그이후는같은 sequece 가지게됨 è 이차집중예 : 여러키가 25에해싱이집중되는경우 à 2, 2, 7, 24 등이빨리만원이될가능성 해결책 : 이중해싱 (double hashig) A = hash(key) A i = (A i- + hash2(key)) mod N (i>) 예 ( 표 8.7) A = hash(key) hash(key) = key mod 3 A i = (A i- + hash2(key)) mod N hash2(key) = + ëkey/3û mod 29 Sook Myug Wome's Uiv. 46

84 개방주소법의문제 레코드의삭제 삭제된레코드를공간으로처리이후의오버플로검색실패 해결방법 레코드의논리적삭제 삭제표시 재해싱 (rehashig) 이후의레코드를삭제후재삽입 Sook Myug Wome's Uiv. 47

85 개방주소법에서레코드의삭제 Remid: 개방주소법에서레코드의검색 버켓에빈공간이발견되면해당레코드없는것으로간주 개방주소법에서레코드가삭제된후검색에서문제가됨 삭제된레코드를공간으로처리 à 이후의오버플러검색실패 예 : 그림 선형조사법 (Liear probe) 사용 : step= A, B, C, D는 2에해싱됨 W, X, Y는 22에해싱됨 이때만약, A, B, C, W, D, X, Y 순서로삽입되면, W가삭제된후 D, X, Y를검색하고자하면 해결방법 검색성공못함 레코드의논리적삭제 - 삭제표시재해싱 (rehashig) 이후의레코드를삭제후재삽입 Sook Myug Wome's Uiv. 48

86 삭제표시 검색때는레코드있는것으로취급 새레코드삽입때는빈공간취급 문제점 : 한공간을레코드가차지하면추후로는다시빈공간안됨 빈공간 à 사용 ; 삭제표시 à 사용 ; 사용 à 삭제표시 검색에시간이오래걸리게됨해결책 : 재구성 구파일을신파일로대체삭제표시없는레코드신파일로해싱 Sook Myug Wome's Uiv. 49

87 재해싱 (rehashig) 레코드삭제하여빈공간만들고나머지레코드를재해싱 나머지레코드가어떤레코드들인지는어떤오버플로기법을사용했는지에따라다름 선형조사에 step 을사용했을경우 재해싱레코드 : 삭제된레코드다음부터빈공간이전까지의레코드들 예 : 그림 W 삭제후 D, X, Y 재해싱 재해싱의단점 선형조사가아닌복잡한개방주소법에서재해싱레코드를찾는것이쉽지않음 시간이많이걸림 Sook Myug Wome's Uiv. 5

88 오버플로해결기법 - (2) 폐쇄주소법 (closed addressig) 폐쇄주소법 체인법 (chaiig) 오버플로레코드들을오버플로구간이나만원이안된임의의버켓에저장. 별도의리스트유지, 홈버켓에서연결 포인터공간문제 2. 연합리스트 홈버켓의여분의공간에저장 포인터공간감소 검색비용증가 3. 디렉토리방법 오버플로레코드의키 / 포인터저장 Sook Myug Wome's Uiv. 5

Chap 6: Graphs

Chap 6: Graphs 그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]