Binary Search Tree 이진탐색과 연결리스트를 결합한 자료구조이다. 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값만 있어야한다. 각 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값만 있어야한다. operation : SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE average case : O(log n) (평균 높이 : log n) worst case : O(n) Search 루트에서 시작. k를 찾을 때 key[x]>k 이면 x의 왼쪽 subtree에서 search key[x] 그냥 삭제 Case2: 삭제할 노드에 자식노드가 1개 있을 때 -> 해당 노드를 지우고 해당 노드의 자식과 부모를 연결 Case3: 자식노드가..
hashing dictionary (key, value)를 implementing insert, search, delete 연산의 average-case : O(1) find minimum과 같은 sort연산은 비효율적이다. dictionary dynamic-set data structure. 동적으로 크기가 변한다. operation : insert, search, delete hash table key : hash function의 input. U : universe of keys. 모든 가능한 키의 집합 K : actual keys. 딕셔너리에 매칭된 실제 키 Hash Table을 만들 때 U를 저장할 필요 없다. |k|=n의 사이즈를 테이블로 만든다. 하지만 좁은 장소에 여러개를 저장해야하므로 h..
NER? NE(개체명) 을 R(인식) 하는 작업. 문자열 안에서 NE의 위치를 알아내고 사전정의한 카테고리에 따라 알맞게 분류하는 작업 즉, NE를 인물, 장소, 시간 이라 하면 문장 안에서 인물, 장소, 시간을 나타내는 명사를 찾아내는 것이다. input : 문자열, output : 단어별로 해당되는 태그 -> multi class 분류 작업 NE 태깅 시스템 1. BIESO 개체명이 시작할 때 : B 토큰이 개체명 중간에 있을 때 : I 토큰이 개체명의 마지막에 있을 때 : E 하나의 토큰이 하나의 개체명 : S 토큰이 개체명이 아님 : O 2. BIO 1번에서 E와I 통합, S와 B통합 NER 접근법 1. 규칙 기반 접근 2. 사전 기반 접근 3. 기계학습 접근 More Info https://gi..
Markov Property → A → B → C → 연쇄해서 사건이 일어나므로 특정 상태의 발생 확률은 그 전 상태의 확률값으로 구할 수 있다. 단어 등장확률 계산하면 P(나는 오늘 커피를 마셨다) = P(나는) X p(오늘 | 나는 ) X P(커피를 | 나는, 오늘 ) X P(마셨다 | 나는, 오늘, 커피를) 뒤로 갈 수록 확률을 계산하기 어려워짐 → 마르코프 특성 적용 P(나는 오늘 커피를 마셨다) = P(나는) X p(오늘 | 나는 ) X P(커피를 | 오늘) X P(마셨다 | 커피를) → P(현재|이전) : bigram but, 특정 상태의 확률값을 구하기 쉽지 않음 이전의 모든 확률을 구하는것은 불가능. → 미래의 상태는 오직 현재 상태의 영향만 받는다 라고 가정 Markov Chain Mar..
