observe_db

2. CompressionWhy?적은 디스크 용량=>비용 절약메모리 절약=>속도 향상디스크->메모리간 데이터 전송 속도 향상단, 압축해제 알고리즘도 꽤 속도가 있어야함.(이게 느리면 의미가 없다) 왜 정보 검색에서?dictionary 고려- 메인메모리 사용을 줄일 수 있음posting-디스크 필요 공간 줄이고, 디스크를 읽는 시간도 줄임. Lossy와 lossless- Lossy는 손실이 있지만 많이 압축됨- lossless는 손실이 없음.  3. Term statisticsterm vocabulary의 크기는 얼마?(모든 웹페이지를 인덱싱하려 할 때에 collection의 크기는?)length 20에 최소 70^20(약 10의 37승)개의 다른 words가 존재.Heap's law: M = kT^bM:..

2. Introduction정보 검색은 HW의 제약조건에 기반한다.메모리가 디스크(HDD)보다 빠르지만(10^3~10^6정도), 용량이 작다.때문에 페이징 등의 기법으로 디스크에서 정보를 가져와야하는데,Disk는 회전/탐색에 시간이 걸리지만, Block 단위로 한번에 큰 범위를 가져오는게 가능하다.(8KB~256KB) RCV1 collection로이터 통신 collection기사 제목과 짤막한 내용으로 구성된다.기사 개수:800K기사당 토큰 수 200term 수 400K(보통 큰 범위는 500K정도)토큰당 바이트 6(공백 등 포함)/4.5(공백 등 제외)term 당 바이트 7.5(*토큰에서 짧고 자주 나오는 단어로 인해 평균이 내려감)non-positional posting 100M 3. BSBI alg..

구문 문법구문 문법은 문장에 대한 구조 정보를 정의한 것문장을 구성 요소들로 분석/구성 요소들을 문장으로 생성구문의 모호성 해소ex. 구구조 문법, 의존 문법 구문 중의성(Syntax Ambiguity)자연어 문장의 구문 구조가 여러가지 방법으로 분석 될 경우중의성 해결을 위해 의미, 문맥 등의 추가적 정보가 필요구문 분석 결과가 잘못되면 이후 단계에 오류 전파 대표적 구문 문법구구조 문법(Phrase Structure Grammar, PSG)노암 촘스키 제안구성소 관계에 기반하여 문장 구조 분석단어->구->더 큰 구, 이 계층 관계에 따라 문장 구성문장 전체를 트리구조로 분석할 떄 단어와 구는 각 노드or부분 트리로 표현의존 문법(Dependency Grammar)뤼시엥 테니에르 제안의존 관계에 기반하..

2. Dictionariesdictionary는 term vocabulary를 저장하는 자료 구조(term voca. = data, dictionary = data structure) 대표적인 자료구조 클래스-hash와 tree(정보검색도 둘다 사용.) Hashes각 vocabulary term은 배열의 행번호인 정수로 해싱됨.쿼리 시간: 고정길이 array에 위치장점: 빠르다.(상수 시간)단점: 마이너한 용어 찾기 어려움/prefix 찾을 수 없음/voca.가 커지면 모든걸 rehash Treesprefix 문제 해결가장 간단한 트리는 이진 트리O(log M)이라 느리긴 함(M이 voca.의 크기)그러나 최적상태는 B-tree(Balanced tree)로만 가능.Rebalancing 문제도 완화 가능...