포스팅 리스트

포스팅 리스트는 낱말 하나를 주면 그 낱말이 나오는 문서 번호들을 알려 줍니다. 검색 엔진은 낱말마다 이 목록을 미리 만들어 둡니다. 검색어가 들어오면 글을 다시 읽지 않고 그 낱말의 목록만 읽어 후보 문서를 얻습니다.

상세

이 절은 포스팅 리스트에 무엇을 적는지, 두 목록을 어떻게 겹치는지, 목록을 어떻게 줄여 담는지를 봅니다.

책 찾아보기의 쪽 번호 줄

두꺼운 기술 서적 뒤쪽에는 찾아보기가 있습니다. 「가비지 컬렉션 · 42, 118, 305」처럼 낱말 옆에 그 낱말이 나오는 쪽 번호가 작은 것부터 적혀 있습니다. 궁금한 낱말이 있으면 책을 처음부터 넘기지 않고 이 줄만 보고 그 쪽들을 펼칩니다.

포스팅 리스트는 이 쪽 번호 줄에 해당합니다. 쪽 번호 대신 문서 번호가 적힙니다.

문서와 문서 번호

검색에서 문서는 찾아 줄 대상 한 건을 가리킵니다. 게시글 하나, 상품 하나, 로그 한 줄이 각각 문서가 됩니다. 문서마다 번호가 붙습니다. 검색 결과로는 이 번호를 돌려줍니다.

이 절에서 쓸 문서는 셋입니다.

역색인의 두 부분

찾기 쉽게 미리 정리해 둔 목록을 색인이라고 합니다. 낱말에서 문서로 찾아가도록 만든 색인이 역색인입니다. 문서를 열면 낱말이 보입니다. 역색인은 이 방향을 뒤집어 낱말을 주면 문서가 나오게 합니다.

역색인은 두 부분으로 이루어집니다. 하나는 색인에 오른 낱말을 모두 모은 용어 사전입니다. 다른 하나가 낱말마다 붙은 포스팅 리스트입니다.

목록 안의 항목 하나를 포스팅이라고 부릅니다. 포스팅이 모인 목록이라서 포스팅 리스트입니다. 세 문서로 만들면 아래 모양이 됩니다.

flowchart TD
    subgraph 용어사전["용어 사전 · 낱말 여섯"]
        T1["당일"]
        T2["무료"]
        T3["배송"]
        T4["안내"]
        T5["조건"]
        T6["환불"]
    end
    T1 --> P1["1 · 3"]
    T2 --> P2["2"]
    T3 --> P3["1 · 2"]
    T4 --> P4["1 · 3"]
    T5 --> P5["2"]
    T6 --> P6["3"]

위의 상자가 용어 사전입니다. 화살표 끝의 번호 줄이 각 낱말의 포스팅 리스트입니다. 「배송」을 찾으면 용어 사전에서 「배송」을 찾은 뒤 그 목록 「1 · 2」를 읽습니다. 문서가 셋이든 천만 개든 읽는 것은 이 목록 하나입니다.

포스팅 하나에 적는 값

포스팅에는 문서 번호만 적을 수도 있고 값을 더 붙일 수도 있습니다. 무엇을 붙이느냐에 따라 검색이 할 수 있는 일이 달라집니다. 아래 표는 「배송」이 1번 문서에 나온 포스팅 하나를 예로 듭니다.

나온 횟수는 한 문서에 그 낱말이 몇 번 나오는지입니다. 이 값을 낱말 빈도라고 부릅니다. 「배송」이 다섯 번 나온 문서는 한 번 나온 문서보다 검색어와 더 맞는다고 봅니다.

문서가 검색어와 얼마나 맞는지 매긴 값이 관련도 점수입니다. 검색 결과는 이 점수가 높은 순서로 늘어섭니다. 낱말 빈도는 이 점수를 매기는 재료 가운데 하나입니다.

나온 위치는 그 낱말이 글에서 몇 번째 낱말인지입니다. 1번 문서에서 「당일」은 첫째, 「배송」은 둘째입니다. 위치가 이어져 있으니 「당일 배송」을 붙은 채로 찾는 검색에 1번이 걸립니다. 이런 검색을 구문 검색이라고 부릅니다.

아래는 위치까지 적은 포스팅 리스트를 파이썬 맵으로 옮긴 것입니다. 포스팅 하나가 문서 번호와 위치 목록의 짝입니다. 위치 목록의 길이가 곧 나온 횟수입니다.

postings = {
    "당일": [(1, [1]), (3, [1])],
    "배송": [(1, [2]), (2, [2])],
}

postings["배송"][0]         # (1, [2])
len(postings["배송"][0][1]) # 1

첫 줄은 「배송」의 첫 포스팅입니다. 1번 문서의 둘째 낱말이라는 뜻입니다. 둘째 줄은 그 위치 목록의 길이라서 1번 문서에 「배송」이 한 번 나왔다는 뜻입니다.

값을 더 적을수록 검색이 더 많은 일을 합니다. 대신 포스팅 하나가 커져서 목록 전체가 차지하는 공간도 늡니다. 그래서 문서 번호만 두는 목록, 횟수까지 두는 목록, 위치까지 두는 목록을 쓰임에 따라 골라 만듭니다.

목록의 길이

목록에 번호가 몇 개인지가 곧 그 낱말이 든 문서의 수입니다. 이 수를 문서 빈도라고 부릅니다. 위 그림에서 「당일」의 문서 빈도는 2 입니다.

문서 빈도는 점수 계산에 쓰입니다. 드문 낱말은 목록이 짧습니다. 그런 낱말이 든 문서는 검색어와 더 맞는다고 봅니다. 문서 빈도가 작을수록 무겁게 치는 값이 역문서 빈도입니다.

관련도 점수를 매기는 대표 공식으로 TF-IDF와 BM25가 있습니다. TF-IDF 라는 이름은 낱말 빈도(Term Frequency)와 역문서 빈도(Inverse Document Frequency)를 합친 것입니다. 두 공식 모두 포스팅에 적힌 횟수와 목록의 길이를 읽어 점수를 냅니다.

목록 길이는 낱말마다 크게 다릅니다. 드문 낱말은 번호 몇 개로 끝납니다. 거의 모든 문서에 나오는 낱말은 목록이 문서 수만큼 깁니다.

번호 순서로 늘어서는 까닭

포스팅 리스트는 문서 번호가 작은 것부터 오게 둡니다. 순서가 정해져 있으면 두 목록을 앞에서부터 나란히 읽으며 비교할 수 있습니다. 순서가 없으면 한쪽 번호 하나마다 다른 쪽 목록을 처음부터 뒤져야 합니다.

이 순서를 지키기는 어렵지 않습니다. 새 문서에 늘 앞선 문서보다 큰 번호를 주면 됩니다. 새 번호는 언제나 목록 끝에 붙습니다. 목록을 따로 정렬하지 않아도 순서가 지켜집니다.

두 목록 겹치기

검색어가 「당일 배송」처럼 두 낱말이면 두 목록을 함께 봐야 합니다. 두 낱말이 다 든 문서만 원하면 두 목록에 모두 있는 번호를 고릅니다. 겹치는 것만 남기는 이 셈이 교집합입니다.

두 목록이 정렬돼 있으니 앞에서부터 나란히 걸으면 됩니다. 두 번호가 같으면 답에 넣고 둘 다 한 칸 나아갑니다. 다르면 작은 쪽만 한 칸 나아갑니다. 작은 번호는 다른 목록에서 이미 지나쳤으니 더 볼 필요가 없기 때문입니다.

세 문서로는 목록이 너무 짧습니다. 아래 코드는 더 긴 번호 목록 두 개로 봅니다.

def both(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            out.append(a[i])
            i += 1
            j += 1
        elif a[i] < b[j]:
            i += 1
        else:
            j += 1
    return out

a = [2, 5, 9, 14]
b = [5, 8, 14, 20]
both(a, b)  # [5, 14]

5 와 14 가 두 목록에 다 있으므로 답은 이 둘입니다. 두 목록을 한 번씩만 지나가므로 걸리는 시간은 두 목록 길이의 합에 비례합니다.

둘 중 하나라도 든 문서를 원하면 같은 방식으로 걸으며 번호를 모두 모읍니다. 이 셈은 합집합입니다. 「그리고」와 「또는」으로 후보를 거르는 이 방식을 불리언 검색이라고 부릅니다.

낱말이 셋 이상이면 가장 짧은 목록부터 겹칩니다. 짧은 목록과 먼저 겹치면 후보가 금방 줄어듭니다. 뒤의 긴 목록에서 확인할 번호도 그만큼 줄어듭니다.

스킵 포인터

나란히 걷는 방식은 한 칸씩만 나아갑니다. 한쪽 목록이 아주 짧고 다른 쪽이 아주 길면 긴 목록의 대부분을 헛걸음합니다. 「환불」이 세 문서에, 「안내」가 백만 문서에 나온다고 해 봅니다. 그러면 번호 세 개를 확인하려고 백만 칸을 지납니다.

이 헛걸음을 줄이려고 긴 목록 군데군데에 멀리 뛰는 표지를 달아 둡니다. 이 표지가 스킵 포인터입니다. 스킵 포인터는 「몇 칸 앞의 번호가 무엇인지」와 그 칸이 목록 안 어디에 있는지를 함께 적어 둡니다.

아래 그림은 번호 일곱 개짜리 목록에 스킵 포인터 둘을 단 모양입니다. 실선은 한 칸씩 걷는 길입니다. 점선이 스킵 포인터입니다.

flowchart TD
    A["3"] --> B["7"] --> C["12"] --> D["30"] --> E["31"] --> F["45"] --> G["52"]
    A -. 스킵 포인터 .-> D
    D -. 스킵 포인터 .-> G

이 목록에서 31 을 찾는다고 해 봅니다. 3 에서 스킵 포인터 끝의 30 을 먼저 봅니다. 30 은 31 보다 크지 않으므로 7 과 12 를 건너뛰고 30 으로 갑니다.

30 에서 다음 스킵 포인터 끝은 52 입니다. 52 는 31 보다 크므로 뛰지 않고 한 칸 걸어 31 을 만납니다. 일곱 칸 가운데 셋만 밟았습니다.

스킵 포인터를 얼마나 촘촘히 두느냐는 맞바꿈입니다. 촘촘하면 한 번에 조금씩만 뛰고 비교를 자주 합니다. 성기면 멀리 뛰지만 뛸 기회가 적습니다. 흔히 쓰는 어림은 길이가 p 인 목록에 √p 개쯤을 고르게 두는 것입니다.

번호 대신 간격 적기

포스팅 리스트는 역색인에서 공간을 가장 많이 차지합니다. 흔한 낱말은 목록 하나에 번호가 수백만 개씩 들어갑니다. 그래서 목록을 줄여 담는 방법이 여럿 쓰입니다.

대표적인 방법은 번호 대신 앞 번호와의 간격을 적는 것입니다. 목록이 정렬돼 있어서 간격은 늘 0 보다 크고 대개 작은 수가 됩니다. 차이만 적는 이 방식이 델타 인코딩입니다.

첫 번호는 앞 번호가 없으므로 0 에서부터의 간격으로 적습니다. 번호는 31 까지 커지지만 간격은 대부분 한 자릿수입니다.

작은 수는 적은 바이트로 적을 수 있습니다. 수의 크기에 맞춰 바이트 수를 달리 쓰는 방식이 가변 길이 정수입니다. 흔한 방식은 한 바이트에 값을 7비트씩 담습니다. 남은 1비트로는 「다음 바이트가 이어진다」를 표시합니다.

간격이 대부분 작으니 번호 하나에 한 바이트 남짓으로 끝나는 경우가 많습니다. 고정 크기 정수로 적을 때보다 목록이 몇 배 작아집니다.

대가는 읽는 방식이 묶인다는 것입니다. 간격으로 적으면 목록 가운데 번호 하나를 바로 읽지 못합니다. 앞에서부터 간격을 더해 가야 번호가 나옵니다.

앞에서부터 나란히 걷는 교집합과는 잘 맞습니다. 가운데로 뛰어야 하는 스킵 포인터는 조금 달라집니다.

앞에서 스킵 포인터가 그 칸의 위치를 적어 둔다고 했습니다. 간격으로 적은 목록에서는 이 위치가 목록 앞에서부터 센 바이트 위치입니다. 여기에 그 칸의 원래 번호도 함께 적습니다. 그래야 뛴 곳에서 간격 더하기를 다시 시작할 수 있습니다.

복잡도

속도는 빅오 표기법으로 적습니다. O(n) 은 걸리는 시간이 n 에 비례해 는다는 뜻입니다. 아래 표에서 p 는 포스팅 리스트 하나의 길이입니다.

읽기는 목록 길이만 따르고 전체 문서 수를 따르지 않습니다. 붙이기는 싸고 지우기는 비쌉니다. 공간은 간격 적기로 줄이지만 목록 가운데를 바로 읽는 힘을 내줍니다.

목록을 고치는 방식

지우기가 비싸므로 지운 문서의 번호를 목록에서 바로 빼지 않는 방식이 흔합니다. 그 번호에 「지워졌다」는 표시만 따로 남깁니다. 검색할 때 목록을 읽고 나서 표시된 번호를 걸러 냅니다.

새 문서도 큰 목록에 바로 끼워 넣지 않는 경우가 많습니다. 새로 들어온 문서들로 작은 역색인을 따로 만듭니다. 이 작은 역색인 하나를 흔히 세그먼트라고 부릅니다.

검색할 때는 세그먼트마다 목록을 읽어 결과를 합칩니다. 세그먼트가 여럿 쌓이면 목록끼리 합쳐 큰 세그먼트 하나로 만듭니다. 이 일이 세그먼트 병합입니다. 지운 표시가 붙은 번호도 이때 정리합니다.

포스팅 리스트를 쓰는 곳

이 절은 포스팅 리스트가 어느 제품 안에 들어 있는지를 봅니다. 검색 라이브러리, 관계형 데이터베이스, 시계열 데이터베이스 셋입니다.

Lucene은 검색 라이브러리입니다. Elasticsearch와 OpenSearch가 그 위에 서 있습니다. 문서는 흔히 제목·본문처럼 여러 칸으로 나뉩니다. 이 칸이 필드이고 필드마다 포스팅 리스트를 따로 둡니다. Elasticsearch 에서는 필드마다 index_options 설정으로 문서 번호만 적을지, 횟수와 위치까지 적을지 고릅니다.

PostgreSQL의 GIN(Generalized Inverted Index, 일반화 역색인)은 배열이나 글 속 낱말로 행을 찾는 인덱스입니다. 값마다 그 값이 든 행을 가리키는 목록을 둡니다. 이 목록을 포스팅 리스트라고 부릅니다. 목록이 길어지면 트리 모양의 포스팅 트리로 바꿔 담습니다.

Prometheus는 시계열 데이터베이스입니다. 시계열은 시각마다 찍힌 값을 이어 놓은 것입니다. 시계열마다 method="GET" 같은 이름표가 붙습니다. 이름표 하나마다 그 이름표가 붙은 시계열의 번호 목록을 둡니다. 이 목록을 postings 라고 부릅니다.

쓸 때와 안 쓸 때

포스팅 리스트는 「이 값이 든 것이 어느 것인가」를 묻는 곳에 맞습니다. 값의 크기 순서나 한 문서 안쪽을 묻는 곳에는 맞지 않습니다.

관련 항목

포스팅 리스트를 품는 상위 구조

역색인 · 용어 사전 · 딕셔너리 · 색인 · 세그먼트

포스팅 하나에 적히는 값

포스팅 · 문서 · 낱말 빈도 · 문서 빈도 · 위치 색인 · 페이로드

목록을 겹치고 건너뛰는 방법

교집합 · 합집합 · 스킵 포인터 · 스킵 리스트 · 갤로핑 검색 · 이진 탐색

목록을 줄여 담는 압축 기법

압축 · 델타 인코딩 · 가변 길이 정수 · 비트 패킹 · 프레임 오브 레퍼런스 · 감마 부호 · 비트맵 · 로어링 비트맵

목록을 읽어 쓰는 검색과 점수

불리언 검색 · 구문 검색 · 관련도 점수 · TF-IDF · BM25 · 역문서 빈도 · 전문 검색

포스팅 리스트와 같은 일을 두고 겨루는 자료구조

순방향 색인 · B-tree · 비트맵 인덱스 · 트라이 · 해시테이블

포스팅 리스트를 채택한 제품과 인덱스

Apache Lucene · Elasticsearch · OpenSearch · Apache Solr · GIN · PostgreSQL · Prometheus

포스팅 리스트가 속하는 상위 분류

자료구조 · 정보 검색 · 검색 엔진 · 검색