'Study'에 해당되는 글 21건

5.1 정보검색에서 용어의 통계적 특성

• ∆%
• 이전의 열로부터 크기의 감소
• T%
• 전체 누적된 감소
• 30 규칙(Rule of 30)
• 30개의 가장 일반적인 용어들이 문헌 내 색인어의 30%를 차지함
• Heap 법칙(Heap’s law): 용어의 수 추정

• 컬렉션 크기 함수로 어휘의 크기를 추정함
• T는 컬렉션에 있는 색인어의 수
• k는 30 ≦ k ≦ 100 이고, b ≈ 0.5 임
• Heap의 법칙은 컬렉션의 크기와 어휘의 크기 간의 가능한 가장 단순한 관계가 로그-로그 공간 상의 직선이라는 가정에 기반함
• Zipf 법칙(Zipf’s law): 용어 분포 모델링
• 문헌 전체에 걸쳐 어떻게 용어가 분포하는지를 알기 위한 방법

• i번째 일반적인 용어의 컬렉션 빈도 cf_i는 1/i에 비례함

5.2 사전 압축

• 스트링 구조의 사전
• 사전을 위한 가장 간단한 자료 구조는 사전 편찬 순으로 어휘를 정렬하고 고정 길이의 배열로 저장하는 것임
• 블록 저장소
• 스트링의 용어들을 크기 k의 블록에 넣어 묶어주고, 각 블록의 첫 용어에 단 하나의 용어 포인터만을 배당해 사전을 좀 더 압축시킬 수 있음
• 압축률을 증가시키면 최소값과 근접한 압축된 사전의 크기를 얻을 수 있지만, k의 큰 값 때문에 용어 검색이 매우 느려짐

5.3 포스팅 파일 압축

• 가변 바이트 부호화(Variable byte(VB) encoding)
• 포스팅 간의 간격을 부호화하기 위해 정수 바이트를 사용함
• 한 바이트의 뒷부분 7비트는 값을 가지며 간격을 부호화하고, 이 바이트의 첫 번째 비트는 연속 비트(Continuation bit)임
• ४ 코드
• VB 코드는 간격의 크기에 따라 바이트의 수를 결정하고 비트 수준 코드는 미세한 비트 수준에서 코드의 길이를 결정함
• 가장 간단한 비트 수준 코드는 유너리 코드(Unary code)임
• 엔트로피(Entropy) H(P)
• 코드가 최적인가를 포함하여 코딩의 속성을 결정하는 이산확률 분포의 특성
• 엔트로피는 x_i가 다음에 나타날 불확실성이 가장 클 때인 0.5에서 H(P) = 1로 최대가 되고, 절대적 확실성이 있을 때는 H(P) = 0으로 최소가 됨
• 보편적 코드(Universal code)
• 임의의 분포 P에 대해 최적의 차수 안에 존재하는 속성을 가진 ४ 코드와 같은 코드
• ४ 코드의 속성
• ४ 코드는 접두사 무겹침 코드(Prefix-free code)임
• ४ 코드는 다른 코드의 접두사가 아님 -> 유일한 복호화
• ४ 코드는 무인수 코드(Parameter-free code)임
• 다른 코드들이 간격 분포에 대한 모델에서 인수를 맞추어야하는 반면 ४ 코드는 필요 없음