MIT - Introduction to Algorithms
- Lecture 2. Models of Computation, Document Distance
알고리즘 계산량, 문서 간 거리 Review
Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
Algorithm이란 무엇일까
알고리즘 실행시간은 무엇이고 어떻게 측정할까 - 규칙은?
어디서 온 것인지부터 시작
AI-Khwarizmi - "The Compendious Book on Calculation by Completion
& Balancing"이라는 것을 시작으로 알고리즘이 생성
대수학의 시초, 선형과 이차 선형에 대한 내용. 초기 알고리즘
cf) Compendious 모든 필요한 내용을 담은
What's an algorithm? 근본적 해석
- Computational procedure for solving a problem
- input -> algorithm -> output
cf) pseudocode 의사 코드 => 다른 방식으로 표현하면 Structured English
꼭 프로그래밍화시켜도 되지 않아도 되며 수학적으로 서로 이해가 되면 됨
Model of computation specifies
- what operations an algorithm is allowed
- cost (time, space, . . . ) of each operation
- cost of algorithm = sum of operation costs
이 수업에서 특히 신경쓰는 것은 running time
많은 다른 곳과의 유사성을 보게될 것
cf) analog 1. 유사의; 상사형(相似型)의 2. 아날로그의; <컴퓨터가> 아날로그식의
Figure 1.범주로 따지면
Computer에 Random Access Memory가 포함되고
Model of Computation에는 Random Access Machine가 포함된다.
Python Model
1. List = 구현의 관점에서는 array로 구현
python : list $\neq$ linked list
skim : list=linked list
L[i] = L[j] + 5 # In python Constant time O(1) time
python에는 linked list가 없음
2. object with O(1) attributes(including references) → pointer machine
x = x.next → Θ(1) time 우리의 관심은 Scalability(확장성)
L.append(x) → θ(1) time -> via table doubling [Lecture 9]
L = L1 + L2 concat
L=[] #O(1)
for x in L1: L.append(x) #O(L1)
for x in L2: L.append(x) #O(L2)
θ(1+|L1|+|L2|) time
len(L) # 파이썬에는 리스트에 길이가 자동 내장 -> 즉시 처리
L.sort() # O(Llog(L)) 비교하는 시간도 포함하는데 Constant time
Comparison Sort => Lecture 3,4,7
dict: D[key] = val -> O(1) #hash table Lecture 8-10,
with high probability w.h.p -> 6.046
python 2.0 long : Lecture 11
x+y #O(|x|+|y|)
x*y #$O((|x|+|y|)^{log_2 3})$ #$log_2 3$ = 1.6...
단순히 곱하는 것보다 더 빠르다 => 실용적
heap q #Lecture4
Document Distance Problem — compute d(D1,D2)
The document distance problem has applications in finding similar documents
detecting duplicates (Wikipedia mirrors and Google) and plagiarism and also in web search (D2 = query).
Document = sequence of words (ignore space, punctuation, etc.)
Word = sequence of alphanumeric characters
Idea : distance in terms of shared words.
the/cat/dog 3개로 벡터를 나눈다.
Inner product = dot product
$d^{\prime}(D1,D2) = D1 \cdot D2 = \sum_w D1[w] \cdot D2[w]$
공통성만을 측정하고 나머지는 0이되므로 사라짐.
The problem is that this is not scale invariant. This means that long documents with 99%
same words seem farther than short documents with 10% same words.
This can be fixed by normalizing by the number of words:
$d^{\prime}(D1,D2) = {D1 \cdot D2 \over |D1||D2|} = cos(\theta) $
$d(D1, D2) = cos^{-1}(d^{\prime}(D1,D2))$ => 각도 angle
$0^{\circ}$는 동일 $90^{\circ}$는 일치하는 단어가 하나도 없음
the document distance is the angle between the vectors. An angle of 0◦ means the two documents are identical
an angle of 90◦ means there are no common words.
This approach was introduced by [Salton, Wong, Yang 1975].
Document Distance Algorithm
1. split each document into words
2. count word frequencies (document vectors)
3. compute dot product
1) 228.1s 2) 164.7s 3) 123.1s 4) 71.7s 5) 18.3s 6) 11.5s 7) 1.8s 8) 0.2s
양이 많아지면 더 극적으로 변화하게 될 것
2) 문서를 돌며 dict에 넣는다.
1) 정규 표현식을 사용
re.findall(r'\w+',doc) # 지수적 증가, 선형 시간
