day 17 ] Document, Lexicon, Posting 구조

1. Selection vs Ranking

1) Selection

- 정확한 분류를 해주는 방법

 

2) Ranking

- 유사도를 분석하고 일정 수치를 기준으로 Ranking을 만들고 상위에 속한 것을 찾아주는 방법

 

2. Lexion 데이터 구조

- lexcion => 사전(해시, 테이블) => 단어: 위치, 단어:위치,
- Posting => 문서:빈도:다음위치, 문서:빈도:다음위치, ...
- Local Indexing => Merge(위치를 조정, linked list)                

 

3. TDM의 진화

- TDM으로 구현하면 Document에 들어있는 각각의 단어에 문서가 매칭되어 저장되기 때문에 중복으로 데이터를 저장하게 된다.

- 량이 너무 많아지게 되면 제곱의 형태로 늘어나기 때문에 메모리에 모두 상주하기가 어렵다.

(ex. [안녕: d1, d2, d5, d7], [의자: d3, d4, d5, d6], [용돈: d1, d4, d7]  => 각각의 단어에 매칭되는 수만큼 저장되기 때문에 중복이 너무많다.)

- Document: 문서 전체를 리스트 형태로 저장한다.

- Posting: 단어에 매칭되는 문서를 Posting으로 링크드리스트 형태로 묶어 해당 문서의 index를 갖도록 저장한다.

- Lexicon: 각 단어와 단어에 매칭되는 Posting의 시작 주소를 쌍으로 저장한다.

 

1) Document

- 문서를 담는 역할 

 

2) Posting

- 단어에 해당하는 문서들을 리스트 형태와 같은 구조로 저장(파이썬에서는 포인터가 없기 때문에 idx로 표현)

- 문서1_idx:빈도:다음위치 -> 문서2_idx:빈도:다음위치 -> ... 마지막문서_idx:빈도:마지막 표시(-1)

 

3) Lexicon

- 단어1:문서 묶음의 시작_idx

- 단어의 묶음을 Lexicon으로 모두 저장해서 가지는 

 

 

4. 실습

1) 테스트 데이터와 각 구조 변수 생성

collection = [

    ("Document1", "this is a simple."),
    ("Document2", "this is another sample."),
    ("Document3", "this is not a sample."),
]

globalLexicon = dict() # 단어: 위치
globalDocument = list()
globalPosting = list()
globalMaxTF = dict()
globalTotalTF = dict()

 

2) Posting, Lexicon, Document 만들기
for docName, docContent in collection:
    docIdx = len(globalDocument) # 0, 1, 2, 3 처럼 숫자 증가( 즉, Document의 순서가 idx가 됨 )
    globalDocument.append(docName) # Document는 그냥 쌓음(name1, name2, name3 ...)
    
    localPosting = dict()
    for term in docContent.lower().split(): # 단어를 전체를 뒤져서 Local로 Posting을 위한 데이터를 만듦(단어1:빈도, 단어2:빈도, ...)
        if term in localPosting.keys():
            localPosting[term] += 1
        else:
            localPosting[term] = 1
            
    for term, freq in localPosting.items(): # 위에서 만든 Local을 돌면서 Posting, Lexicon을 만듦
        if term in globalLexicon.keys():
#            termIdx = list(globalLexicon.keys()).index(term)
            postingIdx = len(globalPosting) # 순차적으로 증가하는 값
            globalPosting.append((docIdx, freq, globalLexicon[term])) # (docIdx:빈도:다음Lexicon위치)
            globalLexicon[term] = postingIdx

        else:
#            termIdx = len(globalLexicon.keys())
            postingIdx = len(globalPosting)  # 순차적으로 증가하는 값
            globalLexicon[term] = postingIdx 
            globalPosting.append((docIdx, freq, -1)) # 최초가 마지막이기 때문에 -1