포스팅

포스팅은 낱말 하나가 어느 문서에 나왔는지를 검색 색인에 적어 둡니다. 낱말과 문서의 짝마다 한 건씩 생깁니다. 검색 엔진은 검색어의 포스팅을 읽어 후보 문서를 고릅니다. 블로그에 글을 올리는 일도 포스팅이라 부릅니다. 이 항목은 검색 쪽 뜻을 다룹니다.

상세

이 절은 짧은 문서 세 개로 포스팅 하나에 무엇이 적히는지 봅니다.

찾아보기의 쪽 번호 하나

두꺼운 기술 서적 뒤쪽에는 찾아보기가 있습니다. 「가비지 컬렉션 · 42, 118, 305」처럼 낱말 옆에 쪽 번호가 늘어서 있습니다. 이 줄에서 숫자 하나는 「이 낱말이 이 쪽에 나온다」는 표시 한 건입니다.

포스팅은 이 숫자 하나에 해당합니다. 쪽 번호 대신 문서 번호를 적습니다.

문서와 문서 번호

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

이 절에서 쓸 문서는 셋입니다. 3번 문서에는 「배송」이 두 번 나옵니다.

역색인 안에서 포스팅이 놓이는 곳

색인은 찾기 쉽게 미리 정리해 둔 목록입니다. 전부 넘겨 보지 않고 바로 찾으려고 만듭니다.

문서를 열면 그 안의 낱말이 보입니다. 문서에서 낱말로 가는 이 방향을 정방향이라고 합니다.

역색인은 이 방향을 뒤집은 색인입니다. 낱말을 주면 그 낱말이 든 문서가 나옵니다. 앞의 찾아보기가 낱말에서 쪽 번호로 가는 것과 같은 방향입니다.

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

아래 그림은 「배송」 한 낱말만 떼어 그린 것입니다.

flowchart TD
    subgraph 사전["용어 사전"]
        T["배송"]
    end
    subgraph 목록["「배송」의 포스팅 리스트"]
        P1["포스팅 · 문서 1"]
        P2["포스팅 · 문서 2"]
        P3["포스팅 · 문서 3"]
    end
    T --> 목록
    P1 ~~~ P2 ~~~ P3

용어 사전에서 「배송」을 찾으면 그 포스팅 리스트로 갑니다. 목록에는 「배송」이 나온 문서마다 포스팅이 하나씩 있습니다. 포스팅이 없다면 「배송」이 든 문서를 알려고 모든 문서의 글을 다시 읽어야 합니다.

3번 문서에는 「배송」이 두 번 나옵니다. 그래도 포스팅은 하나입니다. 포스팅은 낱말과 문서의 짝마다 하나씩 생기기 때문입니다. 몇 번 나왔는지는 그 포스팅 안에 따로 적습니다.

포스팅 하나에 적는 값

포스팅에는 문서 번호만 적을 수도 있고 값을 더 붙일 수도 있습니다. 아래 표는 3번 문서의 「배송」 포스팅 하나를 예로 듭니다.

문서 번호는 모든 포스팅에 들어갑니다. 이것만 있어도 「배송」이 든 문서가 1번·2번·3번이라는 답은 나옵니다. 나머지 셋은 검색에 일을 더 시키려고 붙이는 값입니다.

나온 횟수는 한 문서에 그 낱말이 몇 번 나오는지입니다. 이 값을 낱말 빈도라고 부릅니다.

문서가 검색어와 얼마나 맞는지 매긴 값은 관련도 점수라고 부릅니다. 검색 결과는 이 점수가 높은 순서로 늘어섭니다. 낱말 빈도는 이 점수의 재료입니다. 「배송」이 두 번 나온 3번 문서는 한 번 나온 1번 문서보다 「배송」 검색과 더 맞는다고 봅니다.

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

글자 위치는 그 낱말이 원문의 몇 번째 글자에서 시작해 어디서 끝나는지입니다. 이 값을 오프셋이라고 부릅니다.

글자 위치는 낱말 위치와 달리 0 부터 셉니다. 끝 값은 낱말 바로 뒤의 글자를 가리키므로 범위에 들지 않습니다. 3번 문서의 첫 「배송」은 0번째와 1번째 글자라서 0 이상 2 미만입니다. 띄어쓰기도 한 글자로 세므로 둘째 「배송」은 6 이상 8 미만입니다.

검색 결과 화면에서 찾은 낱말을 굵게 칠해 보여 주는 일을 하이라이트라고 합니다. 오프셋이 있으면 원문을 다시 쪼개지 않고 그 범위만 칠하면 됩니다.

포스팅에 없는 값

「배송」이 든 문서가 몇 개인지는 포스팅 하나에 적히지 않습니다. 이 수는 「배송」의 포스팅 리스트에 포스팅이 몇 건 있는지 세면 나옵니다. 이 수를 문서 빈도라고 부릅니다.

포스팅은 한 문서 안의 일만 압니다. 여러 문서에 걸친 값은 목록이 압니다.

관련도 점수는 두 쪽을 다 씁니다. 한 문서에 여러 번 나온 낱말일수록 그 문서의 점수를 올립니다. 여러 문서에 흔한 낱말일수록 점수에 덜 보탭니다. 거의 모든 문서에 나오는 낱말은 문서를 가려내는 힘이 약하기 때문입니다.

포스팅을 직접 만들기

이 소절은 위의 문서 세 개로 포스팅을 만들어 봅니다. 먼저 글을 낱말로 쪼개야 합니다. 글을 검색 단위로 쪼개는 이 일을 토큰화라고 부릅니다.

아래 코드는 띄어쓰기로만 쪼갭니다. 쪼갠 낱말마다 몇 번째인지 세어 「낱말 → 문서 번호 → 위치 목록」으로 모읍니다.

docs = {
    1: "당일 배송 안내",
    2: "무료 배송 조건",
    3: "배송 조회 배송 문의",
}

index = {}
for doc_id, text in docs.items():
    words = text.split()
    for pos, word in enumerate(words, 1):
        per_word = index.setdefault(word, {})
        per_word.setdefault(doc_id, []).append(pos)

index["배송"][3]       # [1, 3]
len(index["배송"][3])  # 2
list(index["배송"])    # [1, 2, 3]

아래 세 줄 가운데 첫 줄이 3번 문서의 「배송」 포스팅입니다. 첫째 낱말과 셋째 낱말이라는 뜻입니다.

둘째 줄은 그 위치 목록의 길이입니다. 3번 문서에 「배송」이 두 번 나왔다는 뜻입니다. 위치를 적어 두면 횟수는 따로 적지 않아도 세어서 얻습니다.

셋째 줄은 「배송」의 포스팅 리스트에 든 문서 번호만 늘어놓은 것입니다. 이 목록의 길이 3 이 곧 문서 빈도입니다.

위치 목록은 작은 것부터 늘어섭니다. 글을 앞에서부터 읽으며 적으니 따로 정렬하지 않아도 순서가 지켜집니다.

적는 값에 따라 갈리는 세 가지 포스팅

무엇까지 적느냐에 따라 포스팅은 대개 세 가지로 나뉩니다. 적는 값이 늘수록 검색이 할 수 있는 일도 늡니다.

첫 줄의 「그리고」「또는」은 낱말 여럿을 묶어 문서를 거르는 방식입니다. 「당일 그리고 배송」은 두 낱말이 다 든 문서만 남깁니다. 이렇게 거르는 검색을 불리언 검색이라고 부릅니다.

셋째 줄처럼 위치까지 적는 색인은 따로 위치 색인이라고 부릅니다. 글자 위치는 여기에 하이라이트를 하려고 더 붙이는 값입니다.

포스팅의 크기

적는 값이 늘면 포스팅 하나가 커집니다. 이 소절은 포스팅이 몇 건 생기고 숫자가 몇 개 쌓이는지 셉니다.

포스팅의 수는 서로 다른 「낱말과 문서의 짝」의 수와 같습니다. 문서 세 개에서 짝을 세면 1번 셋, 2번 셋, 3번 셋으로 모두 아홉입니다. 3번 문서의 「배송」은 두 번 나와도 짝으로는 하나입니다.

위치까지 적으면 낱말이 나올 때마다 숫자가 하나씩 붙습니다. 그래서 위치의 수는 모든 문서에 든 낱말 수의 합과 같습니다. 세 문서의 낱말은 3, 3, 4 개라서 위치는 열 개입니다.

크기가 무엇에 비례하는지는 빅오 표기법으로 적습니다. O(1) 은 입력이 커져도 크기가 일정하다는 뜻입니다. O(f) 는 f 에 비례해 커진다는 뜻입니다. 아래 표의 f 는 한 문서에서 그 낱말이 나온 횟수입니다.

횟수를 더해도 포스팅마다 숫자 하나가 늘 뿐입니다. 위치를 더하면 흔한 낱말이 자주 나오는 긴 문서에서 포스팅 하나가 크게 불어납니다. 위치 색인 전체는 원문에 든 낱말 수만큼 숫자를 들고 있게 됩니다.

숫자를 줄여 적기

포스팅 안의 위치 목록은 작은 것부터 늘어섭니다. 그래서 위치 대신 앞 위치와의 간격을 적을 수 있습니다. 차이만 적는 이 방식을 델타 인코딩이라고 부릅니다.

어떤 긴 문서에서 한 낱말이 5번째, 130번째, 131번째에 나온다고 합시다. 아래 표의 간격은 바로 앞 위치를 뺀 값입니다.

첫 위치는 앞 위치가 없으므로 0 에서부터의 간격으로 적습니다. 긴 문서일수록 위치 값은 커집니다. 간격은 문서 길이와 상관없이 작은 수로 남기 쉽습니다.

작은 수는 적은 바이트로 적을 수 있습니다. 수의 크기에 맞춰 바이트 수를 달리 쓰는 방식이 가변 길이 정수입니다.

흔한 방식은 한 바이트 8비트 가운데 7비트에만 값을 담습니다. 남은 1비트는 수가 다음 바이트로 이어지는지를 표시합니다. 그래서 한 바이트에는 127 까지 들어갑니다.

위 표에서 130 은 두 바이트가 필요합니다. 간격으로 바꾸면 5, 125, 1 이 모두 한 바이트에 들어갑니다. 문서 번호도 포스팅 리스트 안에서 같은 방식으로 줄여 적습니다.

무엇까지 적을지 고르는 기준

문서는 흔히 제목·본문·태그처럼 여러 칸으로 나뉩니다. 이 칸을 필드라고 부릅니다. 포스팅은 필드마다 따로 만들 수 있습니다. 그래서 적을 값도 필드마다 고릅니다.

마지막 줄은 포스팅이 잘 안 맞는 일입니다. 포스팅 리스트는 낱말 하나에 문서를 모을 뿐 값의 크고 작음으로 늘어서 있지 않습니다. 그래서 1만~2만 원 사이의 값을 모두 찾으려면 그 사이의 값마다 목록을 따로 열어야 합니다. B-tree 는 값의 순서대로 늘어서 있습니다. 범위의 시작을 찾은 뒤 끝까지 차례로 읽으면 됩니다.

적지 않은 값은 나중에 포스팅에서 꺼낼 수 없습니다. 위치를 빼고 만든 색인으로 구절을 찾으려면 문서를 다시 넣어 색인을 새로 만들어야 합니다.

거꾸로 쓰지 않을 값을 적으면 색인만 커집니다. 있나 없나만 묻는 태그 필드에 위치를 적어도 그 위치를 읽는 검색은 오지 않습니다.

관련 항목

포스팅을 모아 담는 상위 구조

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

포스팅 하나에 적히는 값

문서 · 낱말 빈도 · 위치 색인 · 오프셋 · 페이로드

포스팅을 만들기 전에 글을 쪼개는 단계

분석기 · 토큰화 · 토큰 · 형태소 분석 · 불용어

포스팅을 읽어 답하는 검색 방식

불리언 검색 · 구문 검색 · 근접 검색 · 전문 검색 · 하이라이트

포스팅의 값으로 매기는 점수

관련도 점수 · 문서 빈도 · 역문서 빈도 · TF-IDF · BM25

포스팅을 줄여 담는 압축 기법

압축 · 델타 인코딩 · 가변 길이 정수 · 비트 패킹 · 스킵 포인터

포스팅을 채택한 검색 라이브러리와 인덱스

Apache Lucene · Elasticsearch · OpenSearch · Apache Solr · GIN

포스팅이 속하는 상위 분류

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