7. 텍스트 연산 7.1 소개 7.2 문헌 전처리 7.3 문헌 클러스터링 7.4 텍스트 압축 7.5 텍스트 압축 기법의 비교

Presentation on theme: "7. 텍스트 연산 7.1 소개 7.2 문헌 전처리 7.3 문헌 클러스터링 7.4 텍스트 압축 7.5 텍스트 압축 기법의 비교"— Presentation transcript:

1 7. 텍스트 연산 7.1 소개 7.2 문헌 전처리 7.3 문헌 클러스터링 7.4 텍스트 압축 7.5 텍스트 압축 기법의 비교
7.6 연구 동향 및 쟁점 Chapter 7

2 7.1 소개 검색의 정확률 향상 기법 검색 과정의 효율 향상 기법 문헌 전처리(preprocessing) 텍스트 정규화
시소러스(thesaurus) 구축 클러스터링(clustering) 검색 과정의 효율 향상 기법 텍스트 압축 Chapter 7

3 7.2 문헌 전처리 문헌 전처리 과정의 텍스트 연산 어휘 분석(lexical analysis)
숫자, 하이픈, 문장 부호, 대소문자 처리 불용어(stopword) 제거 변별력이 낮은 단어 제거 스테밍(stemming) 접사(접두사와 접미사) 제거 목적: 구문적 변형을 포함하는 문헌 검색 예) connect, connecting, connected 색인어 선정 색인어로 사용할 단어/스템(stem) 혹은 단어 집단 선정 시소러스 구축 용어 분류 구조 구축 목적: 본래의 질의를 관련 용어로 확장 Chapter 7

4 7.2 문헌 전처리(계속) 텍스트 전처리 과정에 따른 문헌의 논리적 상(view)의 변화 Chapter 7

5 7.2.1 텍스트 어휘 분석 어휘 분석 숫자 하이픈 문자열(텍스트)  단어열(색인어 후보) 다음 특별한 경우의 처리에는 주의
숫자, 하이픈, 문장 부호, 대소문자 숫자 보통 좋은 색인어가 아님: 무시하는 것이 바람직 특별한 경우에는 색인어로 간주할 필요가 있음 예) 신용 카드 번호, 510B.C. 하이픈 보통 개별 단어를 분리하는 것이 바람직: 용어 통일 예) state-of-the-art, state of the art 하이픈이 필수적인 경우도 존재 – 예) gilt-edge, B-49 일반적인 규칙 채택과 예외 처리 도입이 바람직 Chapter 7

6 7.2.1 텍스트 어휘 분석(계속) 문장 부호 대소문자 구분 어휘 분석으로 인해 사용자의 색인 전략 파악이 어려우면 곤란
보통 제거 필수적인 경우도 존재 – 예) 510B.C. 제거해도 보통 검색 성능에 별 영향이 없음 특별한 경우에는 예외 처리 필요 예) 변수 x.id와 xid 대소문자 구분 보통 대문자/소문자로 통일 예) 유닉스의 명령어, Bank와 bank 어휘 분석으로 인해 사용자의 색인 전략 파악이 어려우면 곤란 일부 웹 검색 엔진은 텍스트 연산을 전혀 수행하지 않음 Chapter 7

7 7.2.2 불용어 제거 불용어 제거 문헌 컬렉션에서 빈도가 너무 높은 단어는 변별력이 없음
80%이상의 문헌에서 공통적으로 출현하는 단어는 불필요 잠정적인 색인어에서 배제 불용어 후보: 관사, 전치사, 접속사 색인 구조(예: 역리스트) 크기 감소 일반적으로 40% 이상 감소 이를 위해 일부 동사/형용사/부사도 불용어로 취급 가능 단점: 재현률 감소 예) to be or not to be  be 일부 웹 검색 엔진은 전문(full-text) 검색 방법을 취함 Chapter 7

8 7.2.3 스테밍 스테밍 스테밍 전략(by Frakes)
구문적 변형: 질의어와 문헌간의 완전 정합(exact match) 저해 예) 복수형, 동명사형, 과거형 스템: 접사를 제거하고 남은 부분 예) connected, connectin, connection  connect 검색 성능 향상: 스템이 동일한 변형을 공통 개념으로 변환 색인 구조 크기 감소: 색인어 수 감소 스테밍의 효과는 불분명 일부 웹 검색 엔진은 전혀 스테밍 알고리즘을 적용하지 않음 스테밍 전략(by Frakes) 테이블 참조(table lookup) 테이블에서 스템을 발견 데이터 구축/이용이 어려움, 많은 저장 공간 요구 Chapter 7

9 7.2.3 스테밍(계속) 스테밍 전략(계속) 후속자 변형(successor variety)
형태소 경계 결정에 기반, 구조 언어학적 지식 이용 접사 제거 방법보다 복잡 n-그램(n-gram) 다이그램(digram)/트라이그램(trigram) 식별에 기반 용어 클러스터링 과정에 가까움 접사 제거(affix removal) 접미사 제거가 중요 Porter의 알고리즘: 널리 사용되는 접사 제거 방법 일련의 접미사 제거 규칙 적용 예) sses  ss, s   최장 정합 규칙 우선 적용 예) stresses  stress (stresse가 아님) 실행 속도가 빠르면서도 효과적 Chapter 7

10 7.2.4 색인어 선정 전문 색인: 모든 단어를 색인어로 사용 색인어 선정: 색인에 사용할 용어 집합 선정
수동 선정: 전문가가 선정 – 예) 서지학 분야 자동 선정 대부분의 의미는 명사에 의해 전달 2~3개의 명사가 결합하여 단일 개념을 나타내는 경우가 많음 예) computer science 명사 집단(noun group) 선정 명사 집단: 텍스트에서 일정 구문 거리(예: 3단어) 내의 명사 집합 단일 용어 대신 용어 집단의 집합으로 문헌의 논리적 상을 표현 Chapter 7

11 7.2.5 시소러스 시소러스(thesaurus): 단어의 보고(寶庫) 단순한 시소러스의 구성
특정 지식 영역에서 미리 수집하여 구성한 중요 단어의 목록 목록의 각 단어에 대해 관련성 있는 단어의 집합 Roget 시소러스(by Peter Roget) 범용성: 특정 지식 영역에 한정된 것이 아님 단어와 구(phrase) 를 범주와 하위 범주로 조직 특정 지식 영역에만 한정 가능 Thesaurus of Engineering and Scientific Terms: 공학, 과학 분야 Chapter 7

12 7.2.5 시소러스(계속) 시소러스의 목적(Foskett) 시소러스 구축 동기
색인/검색에서 표준 어휘(혹은 참조 시스템) 제공 사용자의 질의 구성시 용어 파악 보조 현재 질의 확장/축소에 필요한 계층 분류 제공 시소러스 구축 동기 통제 어휘(controlled vocabulary) 사용 통제 어휘 색인 개념의 정규화, 잡음 감소, 의미적으로 명확한 색인어 식별 단어보다는 개념에 기초한 검색 대량의 지식이 축적된 특정 분야에서 유리 – 예) 의학 일반적인 분야는 아직 지식 체계가 존재하지 않을지도 모름 (새로운 분야, 너무 넓은 분야, 매우 동적인 분야 – 예) 웹 웹 환경에서 시소러스의 유용성은 불확실 하지만 용어의 계층적 분류를 제공하는 Yahoo!는 성공적 Chapter 7

13 7.2.5 시소러스(계속) 시소러스의 주요 구성 요소: 시소러스 색인어 - 색인어, 용어 관계, 배치 설계
- 색인어, 용어 관계, 배치 설계 용어 관계에 대한 배치(layout): 리스트나 2차원 표현 시소러스 색인어 용어(term): 시소러스의 색인 요소 사고를 전달하는 기본 의미 단위인 개념을 표현 단일 단어, 단어 집단, 구 대부분은 단일 단어, 기본적으로 명사 명사 구실을 하는 동명사형도 포함 – 예) acting, teaching 단일 단어로 개념을 표현할 수 없는 경우 단어 집단 사용 형용사를 결합하여 표현하기도 함 – 예) ballistic missiles 이 경우 배치 순서를 고려해 missiles, ballistic으로 변경 가능 보통 복수형 사용: 시소러스가 대상체의 클래스를 표현 문맥에 따른 정확한 의미 명시를 위해 항목 보충 필요 정의와 설명을 사용 – 예) seal(marine animals), seal(documents) Chapter 7

14 7.2.5 시소러스(계속) 시소러스 용어 관계 IR에서 시소러스의 활용 대부분 동의어/유의어 관계
계층적 관계: 상위어(broader term, BT), 하위어(narrower term, NT) 자동 식별 가능 방계/비계층적 관계: 관련 용어(related term, RT) 특정 문맥과 사용자의 요구에 의존적이므로 자동 식별이 어려움 IR에서 시소러스의 활용 사용자의 검색 절차 찾고자 하는 것에 대한 개념을 세움 이러한 개념화를 정보 요구(information need)라 함 자신의 정보 요구를 질의로 번역: 색인어 선택 질의 구성 과정을 보조하는 데 시소러스가 유용 초기 용어 선택이 부적절한 경우가 아주 일반적임 원래의 질의를 재구성할 때, 관련 용어를 사용하여 확장 Chapter 7

15 7.3 문헌 클러스터링 문헌 클러스터링 문헌 클러스터링 연산의 유형 문헌 클러스터링의 활용
유사한(관련이 있는) 문헌을 모아 집단화하는 연산 사실상 텍스트 연산이 아니라 문헌 컬렉션에 대한 연산임 문헌 클러스터링 연산의 유형 전역적 클러스터링 전체 컬렉션에 대해 문헌 출현을 고려하여 집단화 지역적 클러스터링 현재 질의 문맥과 검색된 지역적 문헌 집합에 의해 집단화가 영향을 받음 문헌 클러스터링의 활용 사용자의 정보 요구를 더 잘 표현하기 위해 원래의 질의를 변형할 수 있도록 보조 클러스터링은 문헌의 텍스트를 변형하는 것보다는 사용자 질의를 변형하는 데 관련이 더 많은 연산임 Chapter 7

16 7.4 텍스트 압축 동기 기본 개념 통계 방법 사전 방법 역파일(inverted file) 압축 모델링 코딩 허프만 코딩
바이트 지향 허프만 코딩 사전 방법 역파일(inverted file) 압축 Chapter 7

17 7.4.1 동기 텍스트 압축 동기 텍스트 압축시 고려 사항 정보의 양이 폭발적으로 증가
저장 공간, 입출력 부담, 전송 지연 감소 지불 대가: 코딩/디코딩 시간 텍스트 압축시 고려 사항 임의 접근 IR에서는 압축 텍스트에 대해 임의(직접) 접근 요구 압축률, 압축/해제 속도 압축 텍스트에 대한 패턴 정합 역파일 압축 대규모 텍스트 컬렉션에서 유용 Chapter 7

18 7.4.2 기본 개념 텍스트 압축 접근법 통계적 방법 통계적(statistical) 방법 사전(dictionary) 방법
심볼에 대한 좋은 확률 평가의 생성이 토대 심볼(symbol): 문자, 단어 혹은 고정된 수의 문자열 알파벳(alphabet): 텍스트의 가능한 모든 심볼 집합 모델링(modeling): 심볼의 확률 평가 작업 모델(model): 확률 분포의 모임 코딩(coding): 심볼  숫자 디코딩(decoding): 숫자  본래의 심볼 인코더(encoder), 디코더(decoder): 같은 모델 사용 Chapter 7

19 7.4.2 기본 개념(계속) 통계적 코딩 방법 허프만 코딩(Huffman coding)
각 심볼에 대해 고정 길이의 비트 인코딩을 한꺼번에 미리 할당 확률이 높은 심볼에 대해 작은 수의 비트 할당 50년대 초에 제안, 70년대 후반까지 가장 중요한 압축 방법 문자 기반 허프만 코딩: 영어를 문자당 5비트로 압축 가능 단어 기반 허프만 코딩: 영어를 문자당 2비트 가까이 압축 가능 임의 접근 허용, 엔트로피에 가까운 압축률 산술 코딩(arithmetic coding) 점진적 코딩: 한 번에 한 심볼씩 점진적으로 코드 계산 영어를 문자당 2비트 가까이 압축 가능 임의 접근 불허 해당 단어가 나타날 때까지 전체 텍스트를 처음부터 디코딩해야 함 느린 압축/해제 속도 IR 환경에서는 부적합 Chapter 7

20 7.4.2 기본 개념(계속) 사전 방법 용어 정의 압축률: 원래 파일에 대한 압축 파일의 크기 비율
일련의 심볼을 이전에 나타난 것에 대한 포인터로 대치 사전: 심볼의 리스트(구)로 구성 포인터: 사전에서 해당 항목을 가리킴 포인터가 대치할 구보다 작은 공간을 차지하면 압축 달성 모델링과 코딩 사이의 구분이 없음 구와 관련된 명시적인 확률이 부재 Ziv-Lempel 계열: 대표적 사전 압축 방법 영어를 문자당 4비트 정도로 압축 가능 용어 정의 압축률: 원래 파일에 대한 압축 파일의 크기 비율 Chapter 7

21 7.4.3 통계 방법 Claude Shannon의 소스 코드 이론 (source code theorem)
확률과 코드 사이의 관계 정립 최적 인코딩 조건 발생 기대 확률이 p인 심볼의 코드 길이를 log21/p비트로 할당 최적 코딩시의 비트 수가 해당 심볼의 정보 내용(information content)을 나타냄 엔트로피(entropy): 전체 알파벳에서 심볼당 평균적인 정보의 양 확률 분포 pi에 기반을 둔 코딩 방법의 압축 하한 확률로부터 계산되므로 모델의 특성임 Chapter 7

22 7.4.3 통계 방법 – 모델링 압축 모델의 종류 적응 모델(adaptive models), 정적 모델(static models), 준정적 모델(semi-static models) 문자 기반 모델, 단어 기반 모델 적응 모델 압축이 진행되면서 통계 분포를 점진적으로 학습 텍스트를 한번만 처리 압축 텍스트 말고는 부가적인 정보 저장 불필요 충분히 긴 텍스트의 경우, 실제 통계 분포로 수렴 파일의 처음부터 압축을 해제해야 함 데이터의 분포 정보가 파일에 점진적으로 저장되기 때문 텍스트의 전문 검색에는 부적합 일반적인 압축 프로그램에서는 적합 Chapter 7

23 7.4.3 통계 방법 – 모델링(계속) 정적 모델 준정적 모델 모든 입력 텍스트에 대해 평균적인 분포 가정
모델링 과정은 모든 텍스트에 대해 단 한 번만 수행 데이터가 초기 통계적 가정에서 벗어나면 압축률 저하 예) 문학 분야에서 모델링 후 재정 분야에 적용 준정적 모델 두 단계로 처리 첫번째 단계: 데이터 분포 학습 두번째 단계: 학습한 분포를 이용하여 압축 압축 해제시 데이터 분포 정보 필요 속도/공간적 측면에서 불리 대화식 데이터 통신이 개입된 상황에서는 실용적이지 못함 직접 접근 가능 압축 파일의 모든 지점에서 동일한 코드 사용 Chapter 7

24 7.4.3 통계 방법 – 모델링(계속) 단어 기반 모델 단어 기반 모델에서 고려 사항 문자 대신 단어를 심볼로 취급
IR에서 단어 기반 모델을 사용하는 이유 높은 압축률 달성 가능 개별 문자보다 단어의 분포가 텍스트의 의미 구조와 더 밀접 대부분의 IR 시스템에서는 색인을 위해 단어를 저장 응답에서는 단어의 빈도가 유용 빈도가 가장 낮은 단어부터 시작하는 것이 좋은 전략 단어 기반 모델에서 고려 사항 구분자 처리 단어와 구분자는 번갈아 나타남 일반 단어와 구분자를 위해 별도의 알파벳 사용 예) each rose, a rose is a rose. 알파벳 심볼 집합: {a, each, is, rose} 구분자의 집합: {‘,U’, U} (U: 공백을 표시) Chapter 7

25 7.4.3 통계 방법 – 모델링(계속) 단어 기반 모델에서 고려 사항(계속) 구분자 처리(계속) 하나의 알파벳 사용
대부분의 경우 단어 다음에는 하나의 공백만 위치 TREC-3 컬렉션의 경우 70-80%의 구분자는 단일 공백 단어 다음에 오는 단일 공백을 그 단어의 일부로 포함 *단어 다음에 공백이 오면 그 단어를 그대로 인코딩 *그렇지 않으면 단어와 다음에 오는 구분자를 별도로 인코딩 *압축을 해제시에는 단어의 다음 심볼이 구분자가 아니라면, 그 단어를 디코딩하고, 공백이 다음에 오는 것으로 간주 이러한 경우의 단어를 공백 부재 단어(spaceless word)라고 함 예) each rose, a rose is a rose. 알파벳: {‘,U’, a, each, is, rose} Chapter 7

26 7.4.3 통계 방법 – 모델링(계속) 단어 기반 모델에서 고려 사항(계속) 숫자 처리 숫자를 단어로 취급하였을 때의 문제점
예) 백만 개의 문헌이 문헌 번호를 포함하고 있는 경우 순전히 숫자로 구성된 단어만 해도 백만 개 생성 긴 숫자를 공(null, 혹은 암시적) 문장 부호를 사용하여 짧게 분리하는 방안 도입 가능 알파벳의 크기 텍스트가 증가해도 압축률이 떨어지지 않음 Heaps의 법칙, Zipf의 법칙 고려 텍스트의 크기 일정 크기 이상의 텍스트인 경우에만 압축 효과 유발 IR의 관심사는 아님 텍스트가 크고, 색인/질의 등을 위해 어휘가 필요 Chapter 7

27 7.4.3 통계 방법 – 코딩 코딩 통계 압축 방법 모델의 확률 분포에 근거하여 심볼의 표현(코드)을 만드는 작업
목표: 출현 가능성이 높은 심볼에 짧은 코드 할당 확률 분포의 엔트로피는 평균적인 코드 길이의 하한 다른 중요 고려 사항: 코더와 디코더 속도 압축/해제 시간 감소를 위해 압축률 희생 필요 존재 통계 압축 방법 허프만 코딩 정적 허프만 압축 방법: 한 단계로 처리 준정적 허프만 압축 방법: 두 단계로 처리 적응 허프만 압축 방법: 한 단계로 처리 코딩 트리를 점진적으로 수정하면서 동시에 인코딩 진행 주된 문제점: 코딩 트리 수정 비용 Chapter 7

28 7.4.3 통계 방법 – 코딩(계속) 통계 압축 방법(계속) 산술 코딩 정적, 준정적, 적응 알고리즘에 기반 장점
항상 엔트로피에 가까운 코드 생성 가능 코딩 트리를 명시적으로 저장할 필요가 없음 적응 알고리즘은 산술 코딩이 허프만 코딩보다 적은 공간 차지 정적/준정적 알고리즘의 경우, 정규(canonical) 허프만 코드를 사용하면 이러한 공간 문제 극복 가능 입력 텍스트를 0과 1 사이의 실수 구간으로 표현 단점 허프만 코딩에 비해 많이 느림 정적/준정적 알고리즘의 경우 특히 심함 임의 접근 불가 단어 기반 허프만 코딩의 압축률은 산술 코딩만큼 좋음 임의 접근이 중요한 텍스트 전문 검색에서는 허프만 코딩이 적합 Chapter 7

29 7.4.3 통계 방법 – 허프만 코딩 허프만 코딩 개요 허프만 코딩 트리의 예 각 심볼에 길이가 다른 비트 코드를 할당
빈도가 높은 심볼에 짧은 코드를 할당함으로써 압축 달성 코드의 앞 부분이 서로 구분됨: 압축 해제의 유일성 보장 허프만 코딩 트리의 예 공백 부재 단어 사용 심볼 집합 {‘,U’, a, each, for, is, rose} 심볼의 빈도 1, 2, 1, 1, 1, 3 일종의 이진 트라이(trei) Chapter 7

30 7.4.3 통계 방법 – 허프만 코딩(계속) 압축 해제 과정 허프만 트리 구성 과정
압축 파일의 비트열을 좌측에서 우측으로 판독 허프만 압축 트리를 루트부터 탐색 단말 노드에 도달하면 해당 단어 출력 예) 0110  for 허프만 트리 구성 과정 알파벳을 구성할 심볼 및 이의 확률 분포 수집 트리 구성 알고리즘은 상향식으로 동작 각 심볼에 대해 해당 심볼과 그 확률을 포함한 노드부터 구성 이때, 각 트리의 노드는 한 개로 구성, 전체 트리의 확률 합계는 1 확률이 가장 낮은 두 노드를 자녀 노드로 하는 부모 노드 구성 부모 노드의 확률은 두 자녀 노드 확률의 합 하나의 루트 노드가 구성될 때까지 이 과정을 반복 시간 복잡도: O(slogs) (s: 심볼의 수) Chapter 7

31 7.4.3 통계 방법 – 허프만 코딩(계속) 정규 트리(canonical tree)
한 확률 분포에 대한 허프만 트리의 수는 매우 많이 존재 좌측과 우측 하위 트리를 바꾸면 트리가 달라짐 코딩 비트를 특정 순서로 유지하는 정규 트리 사용이 바람직 Chapter 7

32 7.4.3 통계 방법 – 허프만 코딩(계속) 정규 코드 (xi, yi) 쌍으로 구성된 순서열(ordered sequence) S로 표현 가능 1il, l: 트리의 깊이, xi/yi: 레벨 i에서의 심볼 수와 첫번째 코드 값 예) S=<(1,1),(1,1),(0,∞),(4,0)> (4,0): 레벨 4, 첫째 코드 값 0(코드워드(codeword) 0000에 해당) 코드 값을 테이블의 색인으로 사용 가능 길이가 같은 코드의 집합은 연속된 정수의 이진 표현 약간의 추가적인 부담으로도 효율적인 코딩과 디코딩 가능 메모리도 훨씬 적게 요구됨 Chapter 7

33 7.4.3 통계 방법 – 바이트 지향 허프만 코드 바이트 지향 허프만 코딩 트리 전체 바이트열로써 각 심볼에 할당할 코드 구성
허프만 트리의 분기 계수가 2 대신 256이 됨 각 심볼의 코드는 전형적으로 1~5바이트 바이트 코드의 예) – 3바이트 코드 트리의 첫 레벨이 빈 노드를 포함하면 최적이 아닐 수 있음 최적 바이트 허프만 트리 구성 방법 빈 노드와 함께 구성될 심볼의 수가 다음과 같이 되도록 선택 1+((v-256) mod 255) (v: 전체 심볼 수) 예) 그림 7.4의 경우, 빈 노드와 함께 구성될 심볼의 수는 2 1+(( ) mod 255) = 2 나머지는 이진 허프만 트리 구성과 유사 Chapter 7

34 7.4.3 통계 방법 – 바이트 지향 허프만 코드(계속) Chapter 7

35 7.4.3 통계 방법 – 바이트 지향 허프만 코드(계속) 바이트 지향 허프만 코딩의 효과 압축 패턴 정합 가능
압축 텍스트의 직접 탐색 가능 현재까지 알려진 어떤 순차적 패턴 정합 알고리즘을 사용해서도 압축 텍스트에 대해 완전 정합 탐색 수행 가능 순차 탐색의 속도 향상 근사 탐색 처리 가능 구 탐색, 범위 탐색, 여집합 탐색, 대표문자를 사용하는 와일드 카드 탐색, 임의의 정규 표현 탐색 어휘를 사용하기 때문에 압축 텍스트를 이용하면 8배 더 빠름 역파일과 순차 탐색이 결합된 색인 체계를 개선하는 데도 사용 가능 Chapter 7

36 7.4.4 사전 방법 사전 방법 개요 정적 사전 체계 준정적 사전 체계 심볼 집단(혹은 구)을 사전 항목의 포인터로 대치
설계의 중심 결정 사항: 사전 항목의 선정 구의 선택: 정적/준정적/적응 알고리즘으로 가능 정적 사전 체계 작은 양을 압축할 경우 빠름 다이그램(digram) 코딩: 문자의 쌍을 코드워드로 대치 적응성 결여 사전이 어떤 텍스트에는 적합하지만 다른 경우에는 부적합 준정적 사전 체계를 사용하여 극복 가능 사전에 수록할 구를 정하는 것이 어려움 준정적 사전 체계 압축할 각 텍스트마다 사전을 새로 구성 Chapter 7

37 7.4.4 사전 방법(계속) 적응 사전 체계 경향 Ziv-Lempel 계열 압축 방법
현재 문자열을 이전에 출현한 문자열에 대한 참조 정보로 대치 시간/공간의 경제성 때문에 일반적인 용도에서 널리 사용 직접 접근 불가능 경향 통계 방법이 IR 환경에서는 더 좋은 방안으로 부상 일반적 용도에서도 통계 방법이 적합하게 될 것으로 예상 계산 기술의 발달 사전 방법에 대한 관심은 점차 줄어들 것으로 예상 Chapter 7

38 7.4.5 역파일 압축 역파일 압축 개요 역파일의 전형적인 구성 텍스트 컬렉션에 나타난 단어(어휘)을 포함하는 벡터
해당 단어가 출현한 문헌의 리스트로 대규모 텍스트 파일을 색인하기 위해 널리 사용 압축 원리: 역리스트(inverted list)를 압축 역리스트의 문헌 번호 리스트: 오름차순 문헌 번호 사이의 격차(gap) 순서열로 표현 가능 보통 역리스트의 시작부터 순차적으로 처리 격차의 합을 통해 원래의 문헌 번호 계산 가능 격차는 빈도가 높은 단어의 경우 작음 작은 격차 값을 짧은 코드로 인코딩하면 압축 달성 가능 코드 체계: 일진 코드, Elias-, Elias- , Golomb Chapter 7

39 7.4.5 역파일 압축(계속) 일진 코드(unary code)
정수 x를 (x–1)개의 1-비트와 마지막 0-비트를 사용하여 코딩 예) 3  110 Chapter 7

40 7.4.5 역파일 압축(계속) Elias- 코드 Elias- 코드
정수 x를 1+log x의 일진 코드와 log x 비트인 x-2 log x의 이진수 결합으로 표현 예) 5  1+log 5 = 3(110), 5-2 log 5 = 1(2비트로 표현시 01) Elias- 코드 Elias- 코드에서 첫 부분을 이진수인 코드 길이로 대치 예) 5  Elias- 코드의 길이 : 5(101) 작은 수는 Elias- 코드가 유리 큰 수는 Elias- 코드가 유리 Chapter 7

41 7.4.5 역파일 압축(계속) Golomb 코드 양의 정수에 대한 run-length 코딩 방법
확률 분포가 기하적일 때 매우 효과적 역파일에서 단어가 확률 p로 출현할 경우, 크기가 x인 격차의 확률은 다음 기하 분포를 따름 문헌이 어떤 용어를 포함할 확률 p는 다음과 같이 계산 가능 p = (포인터의 수) / (N  V) 포인터의 수: 색인의 크기, N: 문헌 수, V: 어휘 크기 Chapter 7

42 7.4.5 역파일 압축(계속) Golomb 코드(계속) 격차 x>0를 q+1의 일진 코드와 r의 이진수 결합으로 표현
q = (x – 1)/b (b : 모형 매개 변수) r = (x – 1) – q  b 이진 코드에 필요한 비트의 수 r < 2 log b - 1 : log b 비트 아니면 log b 비트로 표현 이 경우 첫 비트는 1, 나머지는 r – 2 log b - 1을 log b 비트로 코딩 예) b = 3인 경우, r = 0, 10, 11로 코딩 x = 9인 경우, q = 2, r = 2(9 – 1 = 2  3 + 2), 코드 워드: 역리스트의 격차 압축에서는 b  0.69 (N / ft)가 적당 N: 전체 문헌 수, ft : 용어 t를 포함한 문헌 수 실험 결과 Elias-나 Elias-보다 좋은 압축 결과를 보임 단점: ft를 알아야 하므로 두 단계로 압축 Chapter 7

43 7.4.5 역파일 압축(계속) TREC-3 컬렉션에 대한 실험 결과 TREC-3 컬렉션 포인터 수: 162,187,989개
어휘 수: 894,406개 크기: 2GB Golomb 코딩의 색인 크기: 132MB 포인터당 평균 비트 수 Golomb: 5.73 Elias-: 6.19 Elias-: 6.43 Chapter 7

44 7.5 텍스트 압축 기법의 비교 압축 기법 비교 압축률: 매우 좋음(30% 이하), 좋음(30~45%), 나쁨(45% 이상)
Chapter 7

45 7.5 텍스트 압축 기법의 비교(계속) Ziv-Lempel 방법과 직접 탐색
하지만, 이론적인 기초만 제시 완전한 알고리즘 구현은 이루어지지 않았음 최근 직접 탐색 알고리즘의 실험적 구현이 어느 정도 제시됨 Navarro와 Raffinot 압축 해제와 탐색 시간이 두 배 빠름 압축 해제된 텍스트를 탐색하는 것보다는 느림 압축 텍스트의 중간에서 데이터를 추출할 수도 있음 단, 앞 부분의 텍스트는 일부 압축 해제되어야 함 실제로는 직접 접근이 아님 앞 부분의 작업 양은 압축 해제할 부분의 텍스트 크기에 비례 압축 텍스트에서 데이터 추출 위치에 비례하는 것이 아님 Chapter 7

46 7.6 연구 동향 및 쟁점 텍스트 연산 클러스터링 검색 결과의 질적 향상이 목적
불용어 제거, 스테밍, 색인어 선정 등의 텍스트 연산이 검색 성능을 지속적으로 향상시킬 수 있다는 결정적인 증거는 없음 최근 IR 시스템에서는 이러한 텍스트 연산을 전혀 사용 안 하기도 함 일부 웹 검색 엔진은 모든 단어를 색인어로 사용 시소러스를 사용한 자동적 질의 확장이 검색 성능을 향상시킬 수 있는지도 분명하지 않음 단, 질의 구성 과정에서 사용자를 도와주기 위해 시소러스를 사용하는 것은 유용함 클러스터링 텍스트 변환 연산보다는 문헌 집단화 연산에 더 가까움 Chapter 7

47 7.6 연구 동향 및 쟁점(계속) 텍스트 압축 목적: 저장 공간, 입출력, 전송 비용 감소, 압축된 텍스트에서 보다 빠른 탐색(완전/근사 정합 탐색) IR 환경에서의 요구 조건: 좋은 압축률, 빠른 압축 및 해제, 빠른 임의 접근, 직접 탐색 준정적 단어 기반 모델과 허프만 코딩의 사용이 대세 단어 기반 바이트 허프만 압축 방법: 최신 IR 시스템에서 효과적인 압축 체계를 제공할 가능성이 매우 큼 색인과 텍스트 모두 항상 압축 상태로 유지하는 경향을 보임 문헌 번호 사이의 격차 코딩으로 효율적인 역파일 압축 가능 압축 텍스트의 직접 탐색이 가능 Vo와 Moffat의 최근 연구 결과 압축된 색인을 효율적으로 다룰 수 있게 되었음 Chapter 7