14. Symbol Table Applications

1) Sets - Exception filter

 

수학적으로 set은 집합이란 뜻으로, distinct key의 모음이다.

set의 API는 다음과 같다.

 

void add(Key key)
boolean contains(Key key)
void remove(Key key)
int size()
Iterator<Key> iterator()

 

이것을 이용하면, Exception filter를 구현할 수 있다.

먼저 파일의 White list의 모든 단어들을 읽어서 모든 단어를 Symbol Table에 집어넣는다. 

이 때 삽입은, Hash function으로 구현하면 constant time, Red-black BST로 구현하면 logarithmic time이 걸린다.

다음로 우리가 검사하고자 하는 파일에서 한단어씩 꺼내서 set.contains(Key) 함수로 포함여부를 체크한다.

검사 또한 삽입과 같은 수준의 시간이 걸리고, Black list는 포함하지 않는 단어를 찾으면 된다.

 

2) Dictionary clients

 

예를 들어 다음과 같은 CSV형태의 Dictionary 파일이 있다고 생각해보자.

 

// schoolInfo.csv

1, student, math, merry

2, student, science, merry

3, teacher, math, cole

4, student, math, james

5, , science, jones

 

우리의 LoopupCSV 프로그램은 java로 개발되었고 3개의 parameter를 받고, 사용자 입력을 받는 프로그램이다.

커맨더창에 아래와 같이 입력하면 프로그램이 실행된다.

 

java LoopupCSV schoolInfo.csv 0 2

 

첫번째 parameter는 dictionary파일이고, 0은 검색을 위한 Key의 열번호,  2 찾고자하는 값의 열 번호이다.

프로그램 실행 후 입력창에 다음과 같이 입력하면 다음과 같이 출력된다.

1

math 

5

Not found

2

science

 

한가지 주의점은 우리가 찾고자 하는 파일 내 모든 데이터에 대해 동일 Key에 대해 value값이 동일하지 않으면, 파일에서 한줄씩 읽어들일때 뒤에 나오는 값으로 update되기 때문에 앞에 나오는 값은 사라진다.

 

3) Indexing clients - File indexing

 

여러 파일들이 주어지고, 특정 문자열을 포함하는 파일을 모두 찾고 싶을 경우 FileIndex 프로그램을 구현하면 된다.

예를 들어, 파일들이 다음과 같을 때

디렉토리내 .txt파일이 여러개 있을 때 다음과 같이 해당 디렉토리로 이동해 프로그램을 실행한다.

 

java FileIndes *.txt //프로그램 실행

 

freedom //input

magna.txt moby.txt //output

whale

moby.txt

 

Key값을 파일 내 단어들로 하고, Value값을 파일 목록으로 하여 Symbol Table을 구현하면 된다.

 

4. Sparse matrix-vector

 

N*N 행렬과 N*1행렬의 곱셈을 수행했을 때, 수행시간은 N^2으로 quadratic time이 걸린다.

나도 기계공학전공이라 익숙하지만... 많은 상황에서 행렬의 공간은 0으로 비워져 있다.

사실은 0으로 이루어진 곳에서는 어떠한 값을 곱해도 0이기 때문에 연산의 의미가 없고, 시간만 잡아먹게 된다.

따라서, 애초에 Sparse matrix-vector를 2차원 배열로 구현하는 것이 아닌, 행번호를 배열의Index로 하고, 해당 행에서 0이 아닌 열들의 값들을 linked-list로 연결하여 Symbol table을 구현하면 훨씬 나은 수행결과를 얻을 수 있다. 이 때, linked-list의 노드는 (column Index, value)를 값으로 갖는다. 예를들자면 아래와 같다.

출처 : Coursera, Algorithm part1 lecture

 

만약, sparse matrix-vectord의 곱셈의 실행시간은 각 배열의 Index들에 접근하여 행렬에 존재하는 0이 아닌 요소들을 탐색하는 시간에 비례하는데,  0이 아닌 요소가 상수개 존재할 때 collision은 상수 횟수이므로 결국 배열Index 접근시간에 비례하여 linear time인 N이 된다.