목표 : 질문에 대한 답변(X). 정보 요구에 관련된 Documents 찾아줌(O) ex) 가장 높은 산이 어디야?

• 정보검색 : 나무위키-가장높은산에 관한 document
• Q/A(IBM Watson) : 에베레스트 | | Evaluation Model 평가모델 | 검색된 document가 얼마나 정확한가를 측정하는 모델 Precision(정확도) : 모델이 True로 예측한 것 중에 실제 True의 비율 Recall(재현율) : 실제 True인 것 중에 모델이 True라고 예측한 비율 | | Closed World vs Open World | Closed World Assumption : 존재하지 않는 정보는 틀렸다고 가정 Open World Assumption : 존재하지 않는 정보는 모른다고 가정 | | Problem | Brutus 와 Caesar은 포함하면서 Calpurnia는 포함하지 않는 작품은?

ex) : Brutus, Caesar 작품에서 Calpurnia가 있는 작품을 뺀다.

• 느리고 다른 operation 적용못하고 ranking도 못한다. | | term-document Incidence Vector term-doc 빈도벡터 | term - document에 대한 table을 만들고 포함되면 1. 아니면 0을 입력. Query가 들어오면 그에 따라 term끼리 연산을 진행한다. ex) Brutus(110100) & Caesar(110111) & NOT Calpurnia(101111) ⇒ 100100 ⇒ Antony and Cleopatra, Hamlet | | Information Retrieval Model | Boolean 모델 Vector 모델 Probability 모델 | | Inverted index | Term T를 포함하고 있는 documents들을 미리 저장해놓는 것. ex) Caesar를 포함하고 있는 책들 : 1,2,4,5,6번 | | Inverted index Struct | Terms → Posting List
• posting list는 linked list
• size/ease of insertion 간 트레이드 오프가 존재 - Terms는 사전순으로, Posting은 docID 순으로 정렬 | | Inverted index construction 생성 | 1. 토큰화 (Tokenization)

2. 언어모델 (일반화, stemming)
3. Indexer (인덱싱 진행) | | Text Processing | Tokenization : 문자들을 단어로 잘라 Token으로 변환 Normalization : text와 query term이 같은 형태를 가지도록 변환 - Depluralization(단수화) : Friends → friend - Case-folding(대소문자) : Roman → roman Stemming : 같은 원형의 파생어들도 함께 매치 (worked, working) Stop words : 너무 많거나 너무 적은 common word(a, the, to, ..)는 제거 | | Indexing | 1. 언어모델을 거치면 (I-1, did-1, ..., told-2) 이렇게 나온다.
4. Term을 lexical order로 sorting한다.
5. 같은 Term끼리 모아서 딕셔너리-포스팅으로 만든다. | | Query Inverted Index | Query : Brutus AND Caesar

• Brutus : 2,4,8,16,32,64,128
• Caesar : 1,2,3,5,8,13,21,34 (2,1) → (2,2) → ADD(2) → (4,3) → (4,5) → (8,5) → (8,8) → ADD(8) → ... Brutus와 Caesar의 posting list를 비교같은 값(docID)이 나오면 ADD. Tirme complextity : O(X+Y) | | Indexing Time vs Query Time | Indexing Time : 크롤러가 크롤링하고 인덱싱 할 때의 시간 Query Time : 사용자가 검색(쿼리)하고 결과가 나오는데 까지의 시간 | | Boolean Retrieval Model | 단어가 있는지 없는지만 판단하는 모델 (regex느낌) Boolean Query : AND, OR, NOT Operator으로 수행한다. 판례나 특허 등 하나만 있어도 치명적인 곳에서 사용한다. ex) LIMIT! /3 STATUTE ACTION /S FEDERAL /2 TORT /3 CLAIM | | Boolean Query merge | ??????????????????????? | | | | | Query Optimization | Document freq가 가장 작은 두개부터 차례대로 AND를 하면 더 빠름 Brutus : 7, Caesar : 8, Calpurnia : 2 (Brutus AND Caesar) AND Calpurnia : 16 (Brutus AND Calpurnia) AND Caesar : 12 OR 연산은 AND연산과 다르게 모두 traverse해야 하므로 먼저 한다. (madding OR crowd) AND (ignoable OR strife) **OR size는 최대한 보수적으로 잡자 (**A+B-A∩B → A+B) | | Query Optimization Practice | Query : (tangerine OR trees) AND (kaleidoscope OR eyes) AND (marmalade OR skies)
• eyes : 213312
• kaleidoscope : 87009
• marmalade : 107913
• skies : 271658
• tangerine : 46653
• trees : 316812

(46653+316812) AND (107913+271658) AND (87009+213312) → 363,465 ∩ 379,571 ∩ 300,321 (OR은 +연산) → (363,465 ∩ 300,321) ∩ 379,571 (AND는 작은거부터) | | Frequency | term freq : 어떤 word가 어떤 docs에서 몇 번 발생했는가 document freq : 어떤 term이 나타나는 document의 개수 collection freq : 어떤 term이 전체 collection에 나타나는 개수 | | Phrase Query (Advanced searching) | Inverted Index와 다르게 여러개 단어를 매칭시키기 위한 고급 기법. Phrase를 매칭함 (몇 단어 안에 나와야 한다)

• Stanford University ≠ University at Stanford
• Stanform 다음에 University가 나온다는 위치가 필요함 | | Biword Indexes | 연속되는(consecutive) 두 개의 단어(pair)를 사전의 entry로 넣자.
• A B C D → A, B, C, D, AB, BC, CD 단점 : False Positive (정답이 아닌데 정답인 것 처럼 찾아줌), 자원낭비 | | Positional Index | Term이 나타날 때 마다 Position을 표시. struct { term : “be” doc.freq : 993427 (총 빈도수) doc[1] = [7,18,33,...] (Positional Index list. 위치들의 리스트) doc[2] = [3,149] doc[3] = [17,191,291,...] } | | Positional Index Pros | 일치하는 단어를 찾는 것 이상으로 많은 가능성을 내포함
• ****“to be or not to be” 이런것도 찾을 수 있음
• Proximity search가 가능해짐 LIMIT! /3 STATUTE /3 FEDERAL /2 TORT 이런것도 할 수 있음
• Biword Index는 못함 | | Positional Index Cons | posting storage 비용이 너무 많이 든다
• Compression해서 사용한다.
• 영어계열의 Emprical result(경험적 결과)라서 정확하진 않음 | | Combination Scheme 절충안 | 고유명사는 Mini Biword index로, 나머지는 Positional로 처리하자. ex) Michael Jackson은 Biword index, jumped into는 Positional로 처리. | | | | | Clustering, Classification, Ranking | Clustering : documents의 set에서 내용에 따라 group으로 나눈 것 Classification : Topic의 set에서 새로운 Doc이 어디 topic으로 갈 지 Ranking : 검색 결과가 얼마나 best한지에 따라 ordering | | Token | 문장을 자른 최소 단위. Processing을 거쳐 사전의 entry(Key)에 들어갈 후보가 된다. Issue : 특수문자, 띄어쓰기, 숫자, 메타 데이터, 언어적 특성 등등 | | Stop words | semantic content(의미있는 내용)가 없는 the, a 같은 것들을 버림. | | Normalization | 일반화시켜서 쿼리된 단어가 똑같은 폼으로 변환함. 일반화에 있어서 가장 중요한 기준 : 유저가 어떻게 치고 싶어하는가 Case folding : 대문자 ↔ 소문자 | | Thesauri | 의미를 검색하면 관련된 vocabulary가 나오는 것 ex) 그 질량은 있지만 존재하지 않는거 → 여자친구

종류

• Broader Term(BT : 상위개념 출력)
• Narrow Term(NT : 하위개념 출력)
• Relative Term(RT : 관련개념 출력)

synonymy : 동의어 관계 (car=automobile) homonymy : 동음이의어 관계(can: plastic can, be able to) : 의미 다름 polysemy : 다의어 관계 (man: humankind, male) : 의미적으로 유사함 Hyponymy : 하의 관계 (flower-rese) Antomymy : 반의어 관계

정확한 결과가 나오지 않았을 때 유사한 결과라도 출력해주기 위함 ex) Thesauri에 개 검색 BT : 포유류, NT : 골드 리트리버, RT : 고양이 | | soundex | soundex : 발음이 유사한 관계 (Jonson, Jonston) | | Lemmatization 표제어 추출 | Lemma : 표제어(기본 사전형 단어) Lemmatization : 단어들로부터 표제어를 찾아가는 과정 ex) are, am, is의 표제어는 be 표제어가 한정되어있고 고유명사는 아예 표제어가 존재하지 않는다. | | Stemming 형태소 분석 | Indexing을 하기 전에 morpheme(형태소)에서 stem(어간)을 찾는 것. stem : 어간. 활용 시 모습이 변하지 않는 부분. (hunting, hunter → hunt) affix : 접사. prefix + suffix morpheme : 형태소. 뜻을 가진 가장 작은 말의 단위. = prefix + stem + suffix ex) recooked : re(prefix) + cook(stem) + ed(suffix) | | Derivation Inflection Reduction | Derivation(파생) : 접사(affix)가 덧붙어 다른 의미(품사)가 됨 ex) im+possible, possile+ity Inflection(굴절) : 접미사(suffix)에 의한 어휘의 변화. (품사는 안바뀜) ex) be → am/is/was, apple → apples, fast → faster Reduction(삭제) : 접사를 삭제해서 단어의 원형으로 바꿈 | | Stemming work | Crude affix chopping (무자비하게 affix 자르기) : prefix랑 suffix를 다 잘라버림 ex) automate, automatic, automation → automat | | Korean Stemming 한국어 형태소 분석 | 새 봄 → 새(prefix) + 봄(Noun) 새 정치가 → 새(prefix) + 정치(Noun) + 가(suffix) 봄 꽃 → 봄(Compound Noun) + 꽃(Noun) (prefix : 혼자서 단어를 이룰 수 없는 것. Compound Noun : 복합명사) | | Stemming features | recall은 좋은데 precision은 나쁨

• Recall(재현율) : TP / (TP+FN) == 정답 / 정확하게 예측
• Precision(정밀도) : TP / (TP+FP) == 정답 / 정답이라고 예측
• bad precision : False인데 True라고 한다.
• ex) operative (치과) → oper operative(의학) → oper operational(산업공학) → oper operating(컴퓨터공학) → oper 다 똑같이 oper임 | | Porter’s algorithm | Conventions(관용적) + 5단계 reduction

ex) 관용적 : (은, 는, 이, 가, 에서, ...) → longest suffix를 제거 → 에서 1단계 : sses → ss, ies → i 2단계 : ational → ate, tional → tion ... 이렇게 각 단계에 맞는 변화가 있어서 순서대로 바꾼다. (참고로 빈칸 = 지우라는 뜻 ement → `` (replacement → replac)) | | Skip Pointer | 쿼리 시간(response time)을 빠르게 하기 위해 점프해서 AND 연산. 한쪽이 지나치게 높으면 그 갑에 비슷한 값까지 skip을 타고 이동함. trade-off : 속도 증가 but, pointer를 넣을 메모리가 필요함|

• pointer가 많으면 : comparision 연산 多. 스킵하기 쉬움
• pointer가 적으면 : 연산은 적은데 다시 back 하기 쉬움 최적의 skip 개수 : L개의 posting에서 $\sqrt{L}$ 만큼 | | | | | Tolerant retrieval 관용적 검색 | 정확하게 검색하는게 아니라 대충 검색해도 정답 찾아주는 거 Wild-card queries, Spelling Correction, Soundex | | Naïve dictionary | term이 일정이상 커지면 매우 방대한 크기를 가진다. 어떻게 크기를 줄이면서 query time도 줄일 수 있을까? | | how to struct : Hashtable | 각 vocabulary term에 hash function을 거쳐 hash table을 만들자. 장점 : Tree보다 빠르다 = O(1) 단점
• minor한 변형은 잡아내기 힘들다. (관계가 없으니까)
• prefix search를 못한다. (co-education, co-habitation에서 co- 검색 X)
• 새로운 vocabulary가 많아지면 re-hash하기가 expensive하다. | | how to struct : Binary Tree | 장점 : 쉽다. 우리에게 익숙한 모양이다. 단점 : Re-blancing 문제 (한쪽에만 tree가 생성되는걸 방지하는게 비용이 비쌈) | | how to struct : B-Tree | 자식의 범위가 정해져 있는 Tree 구조. Standard ordering을 요구함 (정렬을 유지) ex : root → (a~hu, hy~m, n~z) 장점 : prefix를 할 수 있음 (hyp로 시작하는 단어) 단점 : 비교적 느림 O(log M). 여전히 rebalancing을 해줘야함 (Binary tree보단 나음) | | | | | Wild-card queries : * | 뭐든지 될 수 있는 카드(조커). | | query processing with Wild-card | mon* : mon을 포함하는 모든 단어(forward) = mon≤term<moo mon : nom을 포함하는 모든 단어(backward) = non>term≥nom procent : pro와 tnec를 포함 = pro≤term<prp AND tned≥term>tnec *마지막 처럼 중간에있는 경우, 를 뒤로 보내 premuterms를 하자. | | Permuterm Index 순열 색인 | 검색하기 전에 query값에 순열을 써서 특별한 모양으로 색인하는것. hello는 hello$, ello$h, llo$he, lo$hel, o$hell, $hello으로 indexing한다. $ : term의 끝. hello$이면 뒤에 term X. $hello는 앞에 term이 X.

기본principal : * 가 뒤쪽에 있도록 rotation을 계속 돌리자.

1. X ➡ X$ 검색 # X로 시작하고 끝나는 모든 단어
2. X* ➡ $X* 검색 # X로 시작하는 모든 단어.
3. *X ➡ X$* 검색 # *X → *X$ → X$* : X로 끝나는 모든 단어
4. *X* ➡ X* 검색 # *X* → X** → X* : X를 포함하는 모든 단어
5. X*Y ➡ Y$X* 검색

X*Y → X*Y$ → Y$X* : Y로 끝나고 X로 시작하는 모든 단어

6. X*Y*Z ➡ *Y* AND Z$X* 검색

X*Y*Z → Y*Z$X* → Z$X*Y* → Z$X* AND *Y*

: Z로 끝나고 X로 시작하는 모든 단어 중에서 Y가 포함된 단어 Z$X* 한번 찾고 난 뒤에 그 중에서 *Y* 찾자. (Post filtering) | | Permuterm exercise | Query : hel*o Lookup : hel*o$ → o$hel* 를 검색 | | Bigram(k-gram) Index | K 문자들의 연속으로 집합을 구성함 ex) mon(K=2) ⇒ $m, mo, on, n$ ex) mon*(K=2) ⇒ $m AND mo AND on but moon이나 mormon 같은것도 찾아지는 경우가 있음. | | Processing wild-card queries | 원래 와일드카드는 expensive query execution임. Disjunctions(OR operation) 작업을 해야함 그래서 serach engine이 잘 지원하지 않는다. | | Index lists | 1. Inverted Index : term을 보고 document를 찾아줌 2. Wildcard index : term을 찾아줌

• Permuterm index
• K-gram Index | | token, type, term | token : a, the, want, wants, wanted, the (띄어쓰기로 자른거) type : a, the, want, wants, wanted (중복제거) term : a, the, want (비슷한의미 제거) | | Spell correction 철자 교정 | 원인 : doc의 spell이 틀린 경우, user가 잘못 typing한 경우 종류
• Isolated word : wrong spell. ex) from → frmo
• Context-sensitive : 문맥. ex) I flew form Heathrow to Narita | | Document correction | OCR(문자인식) 등에서 쓰임
• rn이랑 m이랑 비교
• 도메인 지식 필요 (OCR은 O랑 D, 키보드는 O랑 I가 헷갈리기 쉬움) | | Query mis-spelling | alternative queries를 return 해준다. (Did you mean I flew from?) | | Isolated word correction | 기준

1. standard lexicon (표준 사전)을 기준으로 (사전 단어, 정확 but 적음)
2. 인덱싱 corpus의 lexicon을 기준으로 (모든 단어, 부정확 but 많음)

방법 lexicon과 문자 시퀀스 Q가 있을 때, Q에 가까운 lexicon의 word를 반환

가까운의 기준

1. edit distance (Levenshtein distance)
2. weighted edit distance
3. n-gram overlap | | Edit distance | 두 개의 문자열 A, B가 같아지기 위해서 연산을 수행해야하는 횟수 Operation(Insert, Delete, Replace)은 character level에서 이뤄져야함 • dof → dog의 edit distance는 1이다. • cat → act의 edit distance는 2이다. (cat → aat → act) • cat → dog의 edit distance는 3이다. (cat → dat → dot → dog) ⬇ : 삭제, ➡ : 추가, ↘ : 대체(수정) | | Weighted edit distance | OCR인지 Keyboard인지 domain 따라 weight matrix를 작성한다. 키보드의 경우, d랑 f를 헷갈릴 확률이 높기 때문에 계수를 높게 준다. 그리고 d→f replace를 할 때 weight만큼 곱해줌 | | Edit distance Use | 1. Query을 받으면 characters들로 나눈다 list(Query)
4. preset edit distance에 나열한다. edit_distance[0][] = list(Query)
5. Correct word와 intersect한다. edit_distance[correct][query]
6. Suggestion( Do you mean? )

• 모든 possible한 correction을 inverted index에 넣어서 document를 찾아 보여준다. signle most likely correction
• 유저한테 계속 물어본다. (interaction) | | | | | 모든 terms와 edit distance? | 모든 terms와 edit distance 계산하려면 비용이 너무 많이 든다. n-gram overlap을 써서 후보들을 날려버리자. 이거 그 가체만으로도 spelling correction에도 쓸 수 있다. | | n-gram overlap | Bigram : 두 개의 character를 합쳐서 indexing하는거 Trigram : 세 개의 character를 합쳐서 indexing하는거 n-gram : n 개의 character를 합쳐서 indexing하는거

ex) november : nov, ove, vem, emb, mbe, ber december : dec, ece, cem, emb, mbe, ber 겹치는게 많다 == edit distance가 가깝다 | | Jaccard coefficient 자카드 거리 | noverber의 trigram 집합 X : (nov, ove, vem, emb, mbe, ber) december의 trigram 집합 Y : (dec, ece, cem, emb, mbe, ber)

$J\cdot C=\frac{\left| X \cap Y \right|}{\left| X \cup Y \right|}$

• disjoint면 JC는 0
• 값은 0에서 1사이
• Threashhold가 넘으면 match 한다고 볼 수 잇다. | | Matching bigram exercise | Query : lord Bigrams : lo, or, rd threshold = 1 postings lo → alone, lore, sloth or → border, lore, morbid rd → ardent, border, card

처리과정 (alone, border, ardent) JC(”alone”,”border”), JC(”alone”,”ardent”), JC(”border”,”ardent”) → (lore, border, ardent) JC(”lore”,”border”)=3/7, JC(”lore”,”ardent”)=2/8 → (lore, border, border) JC(”lore”,”border”)=3/7, JC(”border”,”border”)=1 | | Context-sensitive spell correction | 1. Query term 중 하나는 틀렸다고 가정, closed한 term을 찾아주자. ex) flew form Heathrow가 다 틀렸다고 하면 경우의 수가 너무 많음 하나만 틀렸다고 가정하고 더하자. flew + form + Heathrow 2. Query term의 closed term을 다 뽑아서 그 중에 Hit 한거만 추천해주자. Hit-based spelling correction courpus : 코퍼스에서 많이 나온걸 맞다고 하자. query log : 사람들이 많이 검색하는게 맞다고 하자. | | | | | Soundex | 1. 첫번째 글자는 남겨둔다. 2. 모든 모음의 count를 0으로 만든다. 3. 자음은 다음과 같이 바꾼다.

• B, F, P, V → 1
• C, G, J, K, Q, S, X, Z → 2
• D, T → 3
• L → 4
• M, N → 5
• R → 6

4. 연속된 digit은 지운다.
5. 결과에서 0이 나오면 다 지운다.
6. <대문자><숫자><숫자><숫자> 형식이 되도록 남으면 앞에서부터 4개 자르고 부족하면 뒤에 0을 붙이자

ex1 • Herman → H06505 → H655 • Hermann → H065055 → H655

ex2 • Beijing → B002052 → B252 • Peking → P02052 → P252

ex3) • PARKSEYOUNG → P0622000052 → P6252 → P625 • KIMSEONGROK → K0520052602 → K525262 → K525

high recall 같은 업무 (인터폴)에서 쓰인다. 이름이 특정 국가에 bias되는 경우 | | Process Assemble | 프로세스 기법들을 하이브리드로 사용할 수 있다. • Positional inverted index with skip pointers • Wild-card index • Spell-correction • Soundex ex) (SPELL(moriset) /3 toron*to) OR SOUNDEX(chaikofski) : moriset 스펠링 체크를 하고 toron*to 형식이 3개 word 안에 나오거나 chaikofski와 발음이 비슷한 거를 찾아라. | | | | | seek time, latency and Transfer time | Seek time : 디스크가 track에 있는 data를 찾는 시간 Latency : 디스크가 sector를 찾는 시간 Transfer Time : 전송시간 Access Time(seek time + latency) + Transfer time | | RCV1 Collection | 셰익스피어 작품들 말고 연구용으로 공개된 Collection(set of docs) ex) a, the, wish, wishes, a, the token avg : 그냥 slicing한거 갈아/개수 : (1+3+4+6+1+3)/6 term avg : 언어모델 거친거 길이/개수 : (1+3+4)/3 | | Saving problem | Inverted Indexing 하는 과정은 다음과 같은데, Docs → 토큰화 → 일반화 → Sort → 딕셔너리, 포스팅으로 나누기 여기서, 너무 많은 Docs를 한번에 Sorting 시키려면 문제가 발생. | | BSBI 정렬 기반 블록화 색인 | Blocked sort-based Indexing. Sorting에 최적화된 인덱싱 기법. 최소한의 disk seek을 이용해서 sorting을 구현함. | | BSBI basic idea | **1. record를 memory 안에 들어갈 수 있을 정도로 block으로 나눔 2. posting들을 쌓아서 → sorting하고 → 다시 disk에 넣음 3. 모두 merge함 ***record : (term, docID)

block ← ParseNextBlock() #parsing해서 block에 넣기 BSBI_INVERT(block) # sorted된 block을 생성(메모리 안에서) WriteBlockToDist(block,fn) #block을 disk에 저장함 MergeBlocks(f1,f2,...,fn) #Disk에 저장된 block들을 다시 합침

마지막에 MergeBlock 할 때 priority queue를 써서 각 block에서 A로 시작하는거부터 차례대로 쌓고 B로 시작하는거 차례대로 쌓고... 하는거임 block1 : a, the, want block2 : a, a, th block3 : an, of the, of block4 : an → priority queue : [a,a,an,an] 에서 빠른 순서대로 큐에 넣는 방법 | | SPIMI 단일 패스 메모리 색인 | BSBI는 크기 조정에는 뛰어난데 term-termID hash table이 있어야함 대용량 collection에서 기억장치에 올리기가 적합하지 않음. SPIMI(Single-pass in-memory indexing) : termID 대신 term을 그대로 사용하여 각 block의 dictionary를 disk에 기록하는 방식. | | SPIMI basic idea | 각 block마다 complete inverted index를 생성하고 나중에 합치자. 일단 sorting하지말고 posting을 accumulate한다.

doc1 : a, the, write, an, a doc2 : a, hash, want, wall

1. Query를 token_stream으로 만든다.
2. token_stream을 하나씩 iterate하면서 term에 대한 dict를 만든다.
3. dict에는 term:posting_list가 존재한다.
4. posting_list가 꽉 차면 linked list로 새로 연결한다.
5. memory가 가능할 때 까지 반복하다가 꽉 차면 block으로 만든다.
6. dict를 key값(term)에 대해 sorting한다.
7. block을 disk에 저장한다. | | | | | Distributed Computing | GRID computing : heterogenous computer (슈퍼 컴퓨터를 엮은 것) Cluster computing : 연산장치를을 묶어서 슈퍼 컴퓨터로 만드는것 commodity : 분산 컴퓨팅을 범용적으로 쓸 수 있게 만든 상품들. 하둡. | | Distributed Indexing 분산 인덱싱 | 사실 인덱싱은 함수형 프로그래밍으로 봐야함 document → parse → pairing(term,docID) → sort() → reduce() | | MapReduce 맵리듀스 | 1. document를 parser에 넣어서 term을 추출한다.
8. term-docID로 pair를 만든다**(MAP)**
9. term을 기준으로 sorting한다**(Shuffle)**
10. 똑같은 term끼리 모으고 docID는 posting list로 만든다**(Reduce)**
11. 저장한다. | | MapReduce Parellel 맵리듀스 병렬처리 | 맵리듀스는 단어 하나만 보고 독립적으로 진행돼서 병렬처리가 가능함.
12. term-partitioned : 각 머신들에게 term을 나눠서 줌
13. document-partitioned : 각 머신들에게 document를 나눠서 줌(most) | | MapReduce exercise | doc1 : C came, C c’ed doc2 : C died

Map → <C,d1>, <came,d1>, <C,d1>, <c’ed,d1>, <C, d2>, <died, d2> Sort and Shuffle → (<C,(d1,d2,d1)>, <came,(d1)>, <c’ed,(d1)>, <died,(d2)>,) Reduce → (<C,(d1:2,d2:1)>, <came,(d1:1)>, <c’ed,(d1:1)>, <dies,(d2:1)>) | | at Exam | Map Function이 word count면? Map → <C,1>, <came,1>, <C,2>, <c’ed,1>, <C, 3>, <died, 1> Reduce → (<C,3>, <came,1>, <c’ed,1>, <dies,1>) Map Function이 Stemming이라면? Map → <C,고유명사>, <came,동사>, ... | | Static indexing | 딕셔너리와 posting list는 항상 바뀐다. static document : 셰익스피어 dynamic document : 웹 문서 | | Dynamic indexing | 1. big **main index(주 인덱스)**는 disk에 유지 2. small **auxiliary index(보조 인덱스)**는 메모리에 유지 Invalidation bit vector : 무효 비트 제거 | | main + auxiliary index | 두 개 동시에 쓰려니까 merge할 때 stiff함. 느림. 메모리에서 쌓다가 꽉 차면 disk에 저장하자.

• main index : big file에 계속 append하는 방법
• aux index : posting list당 하나씩 small file들을 만드는 방법 | | Logarithmic merge | 적당한 크기의 file을 만들자

1. memory 안에 aux list의 크기를 $z_0$이라고 하자.
2. 지정크기 n을 초과하면 $i_0$만큼 디스크에 저장.
3. 근데 $z_0$==$i_0$가 이미 있으면 $z_0$랑 $i_0$를 합쳐서 $i_1$을 만든다.
4. 근데 $i_1$도 이미 있으면 $z_1$랑 $i_1$를 합쳐서 $i_2$을 만든다.
5. $i_2$ 다 만들면 저장. $i_1$은 삭제 Binorminal (2배씩 증가하는 수열. 앞에꺼의 2배) 처럼 생겼다.

ex) index i2 i1 i0 1 → 1 : i0 2 → 1 0 : i1 3 → 1 1 : i1,i0 4 → 1 0 0 : i2 5 → 1 0 1 : i2,i0Logarithmic merge Pros | | | merge를 꼭 안해도 된다. (i0가 없으면 걍 거기에 넣으면 됨). main index를 디스크에 하나만 유지하려면 할 때마다 append하면서 merge해줘야함.

index construction time • Aux index, main index : O(T^2) • Logarithmic merge : posting마다 O(logT)라서 전체는 O(TlogT) Query time • Aux index, main index : O(1) • Logarithmic merge : O(logT) - 파일 개수만큼 |

| --- | --- |

| --- | --- |