검색 엔진 색인

3. 인덱스 데이터 구조

검색 엔진 아키텍처는 다양한 설계 요소를 충족하기 위해 색인 생성 방식과 색인 저장 방법이 서로 다르다.

;접미사 트리

: 나무처럼 그림으로 표현되는 구조로, 선형 시간 조회를 지원한다. 단어의 접미사를 저장하여 구축된다. 접미사 트리는 일종의 트라이이다. 트라이는 확장 해싱을 지원하며, 이는 검색 엔진 색인 생성에 중요하다.^[8] DNA 서열에서 패턴을 검색하고 클러스터링하는 데 사용된다. 주요 단점은 트리에 단어를 저장하는 데 단어 자체를 저장하는 데 필요한 공간을 초과하는 공간이 필요할 수 있다는 것이다.^[9] 대안적인 표현으로 접미사 배열이 있는데, 이는 가상 메모리가 덜 필요하고 BWT 알고리즘과 같은 데이터 압축을 지원하는 것으로 간주된다.

;역색인

: 일반적으로 해시 테이블 또는 이진 트리 형태로 각 원자 검색 기준의 발생 목록을 저장한다.^[10][11][12]

;인용 색인

: 인용 분석(이는 서지학의 주제임)을 지원하기 위해 문서 간 인용 또는 하이퍼링크를 저장한다.

;''n''-그램 색인

: 다른 유형의 검색 또는 텍스트 마이닝을 지원하기 위해 길이가 ''n''인 데이터 시퀀스를 저장한다.^[13]

;문서-용어 행렬

: 잠재 의미 분석에 사용되며, 문서 내 단어의 발생 횟수를 2차원 희소 행렬에 저장한다.

3. 1. 주요 데이터 구조

4. 병렬 처리 문제

검색 엔진 설계에서 주요 과제 중 하나는 직렬 컴퓨팅 프로세스의 관리이다. 경합 상태 및 일관성 오류가 발생할 가능성이 많다.^[14] 예를 들어, 새로운 문서가 자료에 추가되면 색인이 업데이트되어야 하지만, 동시에 색인은 검색 쿼리에 계속 응답해야 한다. 이것은 두 개의 경쟁 작업 간의 충돌이다. 저자는 정보의 생산자이고, 웹 크롤러는 이 정보를 소비하여 텍스트를 가져와 캐시(또는 코퍼스)에 저장한다고 생각해 보자. 순방향 색인은 코퍼스가 생성한 정보를 소비하고, 역방향 색인은 순방향 색인이 생성한 정보를 소비한다. 이것은 일반적으로 '''생산자-소비자 모델'''이라고 한다. 색인 생성기는 검색 가능한 정보의 생산자이고, 사용자는 검색해야 하는 소비자이다.^[14] 분산 저장소와 분산 처리를 사용할 때 이러한 과제는 더욱 커진다. 색인된 정보의 양이 증가함에 따라 확장하기 위해 검색 엔진 아키텍처는 여러 대의 기계가 동시에 작동하는 분산 컴퓨팅을 포함할 수 있다. 이렇게 하면 불일치 가능성이 증가하고 완벽하게 동기화된 분산 병렬 아키텍처를 유지하기가 더 어려워진다.^[14]

5. 역색인 (Inverted Index)

검색어를 평가할 때 역색인을 사용하여 쿼리에 포함된 단어가 있는 문서를 빠르게 찾은 다음 관련성에 따라 이러한 문서의 순위를 매긴다.^[15] 역색인은 각 단어가 포함된 문서 목록을 저장하므로 검색 엔진은 직접 액세스하여 일치하는 문서를 빠르게 검색하기 위해 쿼리의 각 단어와 관련된 문서를 찾을 수 있다.

이 색인은 단어의 빈도와 위치에 대한 정보를 저장하지 않으므로 특정 문서 내에 단어가 있는지 여부만 확인할 수 있다. 따라서 부울 색인으로 간주된다. 이러한 색인은 어떤 문서가 쿼리와 일치하는지 확인하지만 일치하는 문서의 순위를 매기지는 않는다. 일부 설계에서는 각 문서의 각 단어 빈도 또는 각 문서의 단어 위치와 같은 추가 정보가 색인에 포함된다.^[15] 위치 정보를 사용하면 검색 알고리즘이 구문 검색을 지원하기 위해 단어 근접성을 식별할 수 있다. 빈도는 쿼리에 대한 문서의 관련성 순위를 매기는 데 도움이 될 수 있다. 이러한 주제는 정보 검색의 중심 연구 초점이다.

역색인은 모든 단어가 각 문서에 있는 것은 아니므로 희소 행렬이다. 컴퓨터 저장 장치 메모리 요구 사항을 줄이기 위해 2차원 배열과는 다르게 저장된다. 이 색인은 잠재 의미 분석에서 사용하는 용어 문서 행렬과 유사하다. 역색인은 해시 테이블의 한 형태로 간주될 수 있다. 경우에 따라 색인은 이진 트리의 형태인데, 추가 저장 공간이 필요하지만 조회 시간을 단축할 수 있다. 더 큰 색인에서는 아키텍처가 일반적으로 분산 해시 테이블이다.^[16]

5. 1. 역색인의 구조 및 작동 방식

이 색인은 단어의 빈도와 위치에 대한 정보를 저장하지 않으므로 특정 문서 내에 단어가 있는지 여부만 확인할 수 있다. 따라서 부울 색인으로 간주된다. 이러한 색인은 어떤 문서가 쿼리와 일치하는지 확인하지만 일치하는 문서의 순위를 매기지는 않는다. 일부 설계에서는 각 문서의 각 단어 빈도 또는 각 문서의 단어 위치와 같은 추가 정보가 색인에 포함된다.^[15] 위치 정보를 사용하면 검색 알고리즘이 구문 검색을 지원하기 위해 단어 근접성을 식별할 수 있다. 빈도는 쿼리에 대한 문서의 관련성 순위를 매기는 데 도움이 될 수 있다. 이러한 주제는 정보 검색의 중심 연구 초점이다.

역색인은 모든 단어가 각 문서에 있는 것은 아니므로 희소 행렬이다. 컴퓨터 저장 장치 메모리 요구 사항을 줄이기 위해 2차원 배열과는 다르게 저장된다. 이 색인은 잠재 의미 분석에서 사용하는 용어 문서 행렬과 유사하다. 역색인은 해시 테이블의 한 형태로 간주될 수 있다. 경우에 따라 색인은 이진 트리의 형태인데, 추가 저장 공간이 필요하지만 조회 시간을 단축할 수 있다. 더 큰 색인에서는 아키텍처가 일반적으로 분산 해시 테이블이다.^[16]

5. 2. 구절 검색 (Phrase Search)

5. 3. 색인 병합 (Index Merging)

6. 순방향 색인 (Forward Index)

순방향 색인은 각 문서에 대한 단어 목록을 저장한다. 순방향 색인을 개발하는 이유는 문서를 구문 분석할 때 문서당 단어를 중간에 저장하는 것이 더 효율적이기 때문이다. 이러한 구분은 비동기 시스템 처리를 가능하게 하여 역색인 업데이트 병목 현상을 부분적으로 해결한다.^[19] 순방향 색인은 정렬되어 역색인으로 변환된다. 순방향 색인은 본질적으로 문서별로 정리된 문서와 단어의 쌍 목록이다. 순방향 색인을 역색인으로 변환하는 것은 단어별로 쌍을 정렬하는 것만으로 충분하다. 이러한 측면에서 역색인은 단어별로 정렬된 순방향 색인이다.

7. 압축 (Compression)

대규모 검색 엔진 색인을 생성하거나 유지 관리하는 것은 상당한 저장 용량 및 처리 과제를 나타낸다. 많은 검색 엔진은 디스크의 색인 크기를 줄이기 위해 일종의 압축을 사용한다.^[20]

전체 텍스트 인터넷 검색 엔진의 경우, 20억 개의 웹 페이지에 대한 비압축 색인은 5,000억 개의 단어 항목을 저장해야 하며, 문자당 1바이트 또는 단어당 5바이트일 경우 저장 공간만 2,500GB가 필요하다.^[21][22] (단일 문자를 저장하는데 8비트(또는 1바이트)가 필요하며, 일부 인코딩은 문자당 2바이트를 사용하며, 페이지의 특정 단어에 있는 평균 문자 수는 5개로 추정할 수 있다.) 이 저장 공간 요구 사항은 내결함성 분산 저장 아키텍처의 경우 더 커질 수 있다. 선택한 압축 기술에 따라 색인은 이 크기의 일부로 줄일 수 있지만, 그 대가는 압축 및 압축 해제에 필요한 시간과 처리 능력이다.

대규모 검색 엔진 설계에는 저장 비용뿐만 아니라 저장 장치에 전력을 공급하는 전기 비용도 포함되므로 압축은 비용의 척도이다.

8. 문서 구문 분석 (Document Parsing)

문서 파싱은 문서나 기타 미디어의 구성 요소(단어)를 분리하여 순방향 색인과 역방향 색인에 삽입하는 과정이다. 발견된 단어를 '토큰'이라고 하며, 검색 엔진 색인 및 자연어 처리의 맥락에서 파싱은 더 일반적으로 토큰화라고 한다. 때로는 단어 경계 불명확성 해소, 태깅, 텍스트 분절, 콘텐츠 분석, 텍스트 분석, 텍스트 마이닝, 콘코던스 생성, 음성 분절, 렉싱, 또는 어휘 분석이라고도 한다. '색인', '파싱', '토큰화'라는 용어는 회사 내부에서 서로 바꿔 사용되기도 한다.

자연어 처리는 지속적인 연구와 기술적 개선이 이루어지고 있는 분야이다. 토큰화는 양질의 검색을 지원하기 위한 색인을 위해 문서에서 필요한 정보를 추출하는 데 많은 어려움을 야기한다. 색인을 위한 토큰화는 여러 기술을 포함하며, 그 구현은 일반적으로 기업 비밀로 유지된다.

== 자연어 처리 문제 ==

자연어 처리(NLP)는 검색 엔진 색인에서 중요한 역할을 하며, 다음과 같은 문제들을 야기한다.

; 단어 경계 모호성

영어와 달리 중국어나 일본어와 같이 공백으로 단어가 명확하게 구분되지 않는 언어의 경우, 토큰화 과정이 더 복잡하다. 검색 엔진은 사용자가 검색할 단어를 정확하게 식별하기 위해 언어별 논리를 사용하여 단어 경계를 파악한다.

; 언어 모호성

검색 엔진은 일치하는 문서의 순위를 매기기 위해 각 단어의 언어나 어휘 범주(품사)와 같은 추가 정보를 수집한다. 이러한 기술은 언어마다 구문이 다르기 때문에 언어에 따라 달라진다. 일부 검색 엔진은 문서 토큰화 과정에서 문서의 언어를 자동으로 식별하려고 시도한다.

; 다양한 파일 형식

검색 엔진은 다양한 파일 형식을 올바르게 처리하여 문서 내 문자를 나타내는 바이트를 정확하게 식별해야 한다. 여러 파일 형식을 지원하는 검색 엔진은 문서를 올바르게 열고 액세스하여 문자를 토큰화할 수 있어야 한다.

; 잘못된 저장

자연어 데이터의 품질이 항상 완벽하지 않을 수 있다. 특히 인터넷 문서 중에는 파일 프로토콜을 제대로 따르지 않는 경우가 많다. 바이너리 문자가 문서에 잘못 인코딩될 수 있으며, 이를 제대로 처리하지 않으면 색인 품질이나 성능이 저하될 수 있다.

== 토큰화 (Tokenization) ==

컴퓨터는 자연어 문서의 구조를 이해하지 못하므로, 토큰(token)이라고 하는 개별 단어를 식별하도록 프로그래밍해야 한다. 이러한 프로그램은 일반적으로 토크나이저(tokenizer) 또는 파서(parser) 또는 렉서(lexer)라고 불린다. 많은 검색 엔진과 기타 자연어 처리 소프트웨어는 전문 프로그램 (예: YACC 또는 렉스(Lex))을 구문 분석에 통합한다.

토큰화 과정에서 파서는 단어와 구두점과 같은 다른 요소를 나타내는 문자열을 식별한다. 이러한 요소는 숫자 코드로 표현되며, 일부는 인쇄되지 않는 제어 문자이다. 파서는 개체 (예: 이메일(email) 주소, 전화번호, URL(Uniform Resource Locator))도 식별할 수 있다. 각 토큰을 식별할 때 토큰의 대소문자(대문자, 소문자, 혼합, 고유 명사), 언어 또는 인코딩, 어휘 범주('명사' 또는 '동사'와 같은 품사), 위치, 문장 번호, 문장 내 위치, 길이 및 줄 번호와 같은 여러 특성이 저장될 수 있다.

== 언어 인식 (Language Recognition) ==

검색 엔진이 여러 언어를 지원하는 경우, 토큰화 과정의 일반적인 첫 단계는 각 문서의 언어를 식별하는 것이다. 후속 단계의 상당수는 어간 추출 및 품사 태깅과 같이 언어에 따라 달라진다. 언어 인식은 컴퓨터 프로그램이 문서의 언어를 자동으로 식별하거나 분류하려고 시도하는 과정이다. 언어 인식의 다른 이름으로는 언어 분류, 언어 분석, 언어 식별 및 언어 태깅이 있다. 자동 언어 인식은 자연어 처리 분야에서 지속적인 연구 과제이다. 단어가 속한 언어를 찾는 데에는 언어 인식 차트를 사용하는 것이 포함될 수 있다.

== 형식 분석 (Format Analysis) ==

검색 엔진이 여러 문서 형식을 지원하는 경우, 문서는 토큰화를 위해 준비되어야 한다. 많은 문서 형식이 텍스트 내용 외에도 서식 정보를 포함하고 있기 때문이다. 예를 들어, HTML 문서는 줄 바꿈, 굵은 글꼴, 글꼴 크기 또는 스타일과 같은 서식 정보를 지정하는 HTML 태그를 포함한다. 검색 엔진이 콘텐츠와 '마크업'의 차이를 무시하면, 불필요한 정보가 색인에 포함되어 검색 결과가 저하될 수 있다. 형식 분석은 문서에 포함된 서식 내용을 식별하고 처리하는 것으로, 이는 문서가 컴퓨터 화면에 렌더링되거나 소프트웨어 프로그램에 의해 해석되는 방식을 제어한다. 형식 분석은 구조 분석, 형식 파싱, 태그 제거, 형식 제거, 텍스트 정규화, 텍스트 정리 및 텍스트 준비라고도 한다.

형식 분석의 어려움은 다양한 파일 형식의 복잡성으로 인해 더욱 복잡해진다. 특정 파일 형식은 독점적이며 공개된 정보가 거의 없지만, 다른 파일 형식은 잘 문서화되어 있다. 많은 검색 엔진이 지원하는 일반적이고 잘 문서화된 파일 형식은 다음과 같다.

• HTML
• ASCII 텍스트 파일(특정 컴퓨터가 읽을 수 있는 서식이 없는 텍스트 문서)
• 어도비의 휴대용 문서 형식(PDF)
• 포스트스크립트 (PS)
• LaTeX
• 유즈넷 뉴스 서버 형식
• XML 및 RSS와 같은 파생물
• SGML
• 멀티미디어 메타데이터 형식(예: ID3)
• 마이크로소프트 워드
• 마이크로소프트 엑셀
• 마이크로소프트 파워포인트
• IBM 로터스 노츠

• ZIP - Zip 보관 파일
• RAR - Roshal ARchive 파일
• CAB - 마이크로소프트 윈도우 Cabinet 파일
• Gzip - gzip으로 압축된 파일
• BZIP - bzip2를 사용하여 압축된 파일
• Tape ARchive (TAR), 유닉스 보관 파일(자체적으로 압축되지 않음)
• TAR.Z, TAR.GZ 또는 TAR.BZ2 - Compress, GZIP 또는 BZIP2로 압축된 유닉스 보관 파일

• 서식을 사용하여 컴퓨터 화면에는 표시되지 않지만 색인 생성기에는 표시되는 섹션에 수백 또는 수천 개의 단어를 포함하는 것(예: HTML의 숨겨진 "div" 태그로, 이는 이를 위해 CSS 또는 JavaScript를 사용할 수 있음).
• 단어의 전경 글꼴 색상을 배경 색상과 동일하게 설정하여 문서를 보는 사람에게는 단어가 컴퓨터 화면에 숨겨져 있지만, 색인 생성기에는 숨겨져 있지 않게 하는 것.

• 서로 다른 섹션의 콘텐츠가 실제로는 관련이 없는데도 색인에서 관련이 있는 것으로 처리된다.
• 조직적인 "사이드 바" 콘텐츠가 색인에 포함되지만, 사이드 바 콘텐츠는 문서의 의미에 기여하지 않으며, 색인에는 문서의 부실한 표현이 채워진다.

8. 1. 자연어 처리 문제

8. 2. 토큰화 (Tokenization)

8. 3. 언어 인식 (Language Recognition)

8. 4. 형식 분석 (Format Analysis)

• HTML
• ASCII 텍스트 파일(특정 컴퓨터가 읽을 수 있는 서식이 없는 텍스트 문서)
• 어도비의 휴대용 문서 형식(PDF)
• 포스트스크립트 (PS)
• LaTeX
• 유즈넷 뉴스 서버 형식
• XML 및 RSS와 같은 파생물
• SGML
• 멀티미디어 메타데이터 형식(예: ID3)
• 마이크로소프트 워드
• 마이크로소프트 엑셀
• 마이크로소프트 파워포인트
• IBM 로터스 노츠

• ZIP - Zip 보관 파일
• RAR - Roshal ARchive 파일
• CAB - 마이크로소프트 윈도우 Cabinet 파일
• Gzip - gzip으로 압축된 파일
• BZIP - bzip2를 사용하여 압축된 파일
• Tape ARchive (TAR), 유닉스 보관 파일(자체적으로 압축되지 않음)
• TAR.Z, TAR.GZ 또는 TAR.BZ2 - Compress, GZIP 또는 BZIP2로 압축된 유닉스 보관 파일

• 서식을 사용하여 컴퓨터 화면에는 표시되지 않지만 색인 생성기에는 표시되는 섹션에 수백 또는 수천 개의 단어를 포함하는 것(예: HTML의 숨겨진 "div" 태그로, 이는 이를 위해 CSS 또는 JavaScript를 사용할 수 있음).
• 단어의 전경 글꼴 색상을 배경 색상과 동일하게 설정하여 문서를 보는 사람에게는 단어가 컴퓨터 화면에 숨겨져 있지만, 색인 생성기에는 숨겨져 있지 않게 하는 것.

8. 5. 섹션 인식 (Section Recognition)

• 서로 다른 섹션의 콘텐츠가 실제로는 관련이 없는데도 색인에서 관련이 있는 것으로 처리된다.
• 조직적인 "사이드 바" 콘텐츠가 색인에 포함되지만, 사이드 바 콘텐츠는 문서의 의미에 기여하지 않으며, 색인에는 문서의 부실한 표현이 채워진다.

9. HTML 우선순위 시스템

색인 생성 과정에서는 우선순위를 정하기 위해 HTML 태그를 인식해야 하는 경우가 많다. 텍스트의 처음에 있는 ''strong''이나 ''link''와 같은 레이블에 대한 우선순위를 최적화하기 위해 낮은 우선순위부터 높은 우선순위까지 색인을 생성하는데, 이러한 레이블이 관련성이 없을 수도 있다. 구글과 빙과 같은 일부 색인 생성기는 강력한 형식 시스템 호환성 때문에 검색 엔진이 큰 텍스트를 관련 소스로 간주하지 않도록 한다.^[23]

10. 메타 태그 인덱싱

메타 태그 색인은 웹 콘텐츠를 구성하고 분류하는 데 중요한 역할을 한다. 특정 문서에는 작성자, 키워드, 설명 및 언어와 같은 메타 정보가 포함되어 있다. HTML 페이지의 경우, 메타 태그에는 색인에 포함되는 키워드가 포함된다.^[24] 초기 인터넷 검색 엔진 기술은 순방향 색인의 메타 태그에 있는 키워드만 색인화했다.^[24] 당시에는 전문 색인이 잘 확립되지 않았고, 컴퓨터 하드웨어도 그러한 기술을 지원할 수 없었다.^[24]

1990년대 인터넷이 성장함에 따라 많은 오프라인 기업들이 온라인으로 진출하여 회사 웹사이트를 구축했다. 웹페이지를 설명하는 데 사용되는 키워드는 설명적인 것에서 특정 검색어에 대한 검색 결과 상위에 웹페이지를 배치하여 판매를 유도하도록 설계된 마케팅 중심의 키워드로 바뀌었다. 이러한 키워드가 주관적으로 지정되었다는 사실은 스팸 색인으로 이어졌고, 이는 1990년대 많은 검색 엔진이 전문 색인 기술을 채택하게 만들었다. 전문 색인은 더 객관적이었고 검색 엔진 결과의 품질을 향상시켰다.^[24]

데스크톱 검색에서 많은 솔루션은 메타 태그를 통합하여 작성자가 파일 콘텐츠에서 명확하지 않은 다양한 파일의 콘텐츠 색인 방식을 추가로 사용자 지정할 수 있는 방법을 제공한다.

참조

_[1] 논문 Dynamic Inverted Indexes for a Distributed Full-Text Retrieval System University of Waterloo 1995-02-01
_[2] 학술지 RDF-powered semantic video annotation tools with concept mapping to Linked Data for next-generation video indexing https://ap01.alma.ex[...] 2016-08-01
_[3] 웹사이트 Wang03-shazam http://www.ee.columb[...] 2022-03-01
_[4] 논문 Fast Multiresolution Image Querying http://grail.cs.wash[...] Department of Computer Science and Engineering, University of Washington 1995-12-01
_[5] 논문 Execution Performance Issues in Full-Text Information Retrieval Computer Science Department, University of Massachusetts Amherst 1995-10-01
_[6] 학술지 Optimizations for dynamic inverted index maintenance 1990-01-01
_[7] 웹사이트 Linear Hash Partitioning http://dev.mysql.com[...] 2006-12-01
_[8] 웹사이트 trie https://xlinux.nist.[...]
_[9] 서적 Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology Cambridge University Press 1999-01-01
_[10] 웹사이트 inverted index https://xlinux.nist.[...] 2006-12-01
_[11] 학술지 Information retrieval: information storage and retrieval using AVL trees 1965-08-26
_[12] 학술지 The balanced tree and its utilization in information retrieval 1963-12-01
_[13] 웹사이트 Google Ngram Datasets http://www.ldc.upenn[...] 2013-09-29
_[14] 논문 MapReduce: Simplified Data Processing on Large Clusters Google, Inc. OSDI 2004-01-01
_[15] 웹사이트 IR Basics of Inverted Index http://www.cs.clemso[...] 2011-08-01
_[16] 논문 Hybrid Global Local Indexing for Efficient Peer to Peer Information Retrieval http://www.cs.roches[...] University of Rochester
_[17] 서적 Information retrieval: implementing and evaluating search engines The MIT Press 2016-01-01
_[18] 논문 Incremental Updates of Inverted Lists for Text Document Retrieval Stanford University 1993-12-01
_[19] 웹사이트 The Anatomy of a Large-Scale Hypertextual Web Search Engine http://infolab.stanf[...] Stanford University 2006-12-01
_[20] 학술지 Storage analysis of a compression coding for a document database 1972-02-01
_[21] 웹사이트 The Unicode Standard - Frequently Asked Questions https://www.unicode.[...] 2006-12-01
_[22] 웹사이트 Storage estimates https://web.archive.[...] 2006-12-01
_[23] 뉴스 Hypertext Markup Language 5 Google Webmaster Tools 2012-01-01
_[24] 간행물 Hypertext Markup Language - 2.0 Network Working Group 1995-11-01
_[25] 논문 Dynamic Inverted Indexes for a Distributed Full-Text Retrieval System University of Waterloo 1995-02-01
_[26] 학술지 RDF-powered semantic video annotation tools with concept mapping to Linked Data for next-generation video indexing https://ap01.alma.ex[...] 2016-08-01
_[27] 웹사이트 Wang03-shazam http://www.ee.columb[...]
_[28] 논문 Fast Multiresolution Image Querying http://grail.cs.wash[...] Department of Computer Science and Engineering, University of Washington 1995-12-01