불리언 검색

불리언 검색은 찾는 단어들을 조건으로 묶어 그 조건에 맞는 문서만 골라 줍니다. 「배송과 환불이 둘 다 든 글」처럼 조건을 적으면 문서가 맞는 쪽과 안 맞는 쪽으로 딱 갈립니다. 맞는 문서끼리 어느 것이 더 잘 맞는지는 따지지 않습니다.

상세

이 절은 문서 네 개짜리 작은 예로 불리언 검색이 조건을 받아 답을 내는 과정을 따라갑니다.

집 구하기에 빗대면

부동산 중개인에게 「역에서 걸어갈 수 있고 반려동물을 받아 주는 집, 반지하는 빼고」라고 부탁했다고 합시다. 중개인은 이 조건에 맞는 집만 추려 보여 줍니다. 조건을 하나라도 어긴 집은 아무리 싸도 목록에 안 올라옵니다.

중개인은 추린 집에 순위를 매기지 않습니다. 조건에 맞으면 목록에 듭니다. 안 맞으면 빠집니다.

불리언 검색에서는 집 대신 문서를 추립니다. 문서는 검색이 찾아 줄 대상 한 건입니다. 게시글 하나, 상품 설명 하나, 로그 한 줄이 각각 문서가 됩니다. 조건은 「이 단어가 문서에 들었나」입니다.

참과 거짓 두 값

불리언은 참과 거짓 두 값만 갖는 값입니다. 자바의 boolean 타입이 담는 값이 이것입니다.

이 이름은 수학자 조지 불에게서 왔습니다. 그는 참과 거짓만으로 계산하는 논리 체계를 세웠습니다. 이 체계가 불 대수입니다.

불리언 검색은 문서마다 「이 문서가 조건에 맞나」를 묻습니다. 답은 참 아니면 거짓입니다. 답이 불리언 값이라서 이 검색에 불리언이라는 이름이 붙었습니다.

연산자 셋

단어 하나로만 찾으면 「배송」이 든 글이 전부 나옵니다. 그 가운데 해외 배송 글을 빼려면 사람이 결과를 하나씩 열어 봐야 합니다. 불리언 검색은 이 걸러 내는 조건을 검색어 안에 적게 해 줍니다.

조건 여러 개를 하나로 잇는 단어가 논리 연산자입니다. 불리언 검색은 AND · OR · NOT 셋을 씁니다. SQL(Structured Query Language)의 WHERE 절에 쓰는 AND · OR · NOT 과 같은 논리입니다. 다른 점은 조건이 열의 값을 묻지 않고 글 속에 단어가 들었는지를 묻는다는 것입니다.

아래 표는 연산자마다 뜻과 위 네 문서에 돌린 결과를 보입니다. 결과 칸의 수는 문서 번호입니다.

AND 는 붙일수록 결과가 줄어듭니다. 조건을 하나 더 걸면 문서가 그 조건까지 통과해야 하기 때문입니다. OR 는 붙일수록 결과가 늘어납니다.

NOT 은 혼자 쓰는 일이 드뭅니다. 「해외가 없는 문서」만 달라고 하면 해외가 든 문서를 뺀 나머지 전부가 답입니다. 문서가 천만 개면 답도 천만 개에 가깝습니다. NOT 은 대개 다른 조건 뒤에 붙어 결과를 줄이는 데 씁니다.

위 표의 「배송 AND NOT 해외」가 그렇게 쓴 꼴입니다. AND 뒤에 NOT 을 붙인 이 꼴을 흔히 AND NOT 이라고 부릅니다. 앞 조건에 맞는 문서에서 뒤 조건에 맞는 문서를 뺀다는 뜻입니다.

괄호로 묶기

연산자가 둘 이상 섞이면 어느 연산자부터 계산하느냐가 결과를 가릅니다. 배송 OR 환불 AND 당일 은 두 가지로 읽힙니다.

논리학에서는 흔히 NOT 을 먼저, 그다음 AND 를, 마지막에 OR 를 계산합니다. 그 순서라면 위 검색어는 두 번째로 읽힙니다. 검색 엔진마다 이 순서를 달리 풀기도 합니다. 괄호로 묶어 뜻을 밝혀 두는 쪽이 안전합니다.

괄호로 묶은 검색어는 트리 모양으로 풀립니다. 아래 그림은 (배송 OR 환불) AND 당일 을 푼 모양입니다. 맨 아래 단어 칸에서 문서 번호를 얻습니다. 그 번호를 들고 위로 올라가며 연산자를 하나씩 계산합니다. 맨 위 칸의 번호가 답입니다.

flowchart TD
    A["AND · 1, 3"] --- B["OR · 1, 2, 3, 4"]
    A --- C["당일 · 1, 3"]
    B --- D["배송 · 1, 2, 4"]
    B --- E["환불 · 3"]

역색인 위의 집합 연산

문서마다 글을 열어 단어를 찾으면 문서가 천만 개일 때 검색 한 번에 천만 개를 읽습니다. 그래서 불리언 검색은 대개 역색인 위에서 돕니다. 역색인은 단어마다 그 단어가 든 문서 번호를 적어 둔 찾아보기입니다. 책 뒤의 찾아보기가 단어 옆에 쪽 번호를 적는 것과 같은 모양입니다.

단어마다 붙은 번호 목록은 포스팅 리스트라는 이름으로 부릅니다. 위 네 문서의 역색인은 아래와 같습니다.

역색인이 있으면 연산자 셋은 번호 목록끼리의 연산이 됩니다. 문서를 하나도 열지 않고 목록만 읽어 답을 냅니다. 아래 표는 「배송」(1, 2, 4)과 「당일」(1, 3) 두 목록에 연산을 돌린 결과입니다.

코드로 보기

백엔드 코드로 옮기면 역색인은 「단어 → 번호 집합」 맵입니다. 연산자 셋은 집합 연산이 됩니다. 아래는 파이썬의 집합으로 셋을 돌린 것입니다. 줄 끝의 주석이 그 줄이 내는 값입니다.

idx = {"배송": {1, 2, 4},
       "당일": {1, 3},
       "환불": {3},
       "해외": {4}}

idx["배송"] & idx["당일"]  # {1}
idx["배송"] | idx["환불"]  # {1, 2, 3, 4}
idx["배송"] - idx["해외"]  # {1, 2}

& 가 AND, | 가 OR, - 가 AND NOT 을 맡습니다. 검색 엔진은 집합 대신 문서 번호를 작은 것부터 늘어놓은 목록을 씁니다. 번호가 정렬돼 있으면 두 목록을 앞에서부터 함께 훑어 교집합을 구할 수 있습니다. 목록마다 지금 읽는 번호를 가리키는 포인터를 하나씩 둡니다.

훑는 법은 이렇습니다. 두 포인터가 가리키는 번호를 비교합니다. 같으면 그 번호를 답에 넣습니다. 그다음 두 포인터를 다 한 칸 옮깁니다. 다르면 작은 번호 쪽 포인터만 한 칸 옮깁니다.

「배송」(1, 2, 4)과 「당일」(1, 3)로 해 봅니다. 먼저 1과 1이 같아 1을 답에 넣습니다. 다음은 2와 3이라 작은 2 쪽을 옮깁니다. 이어 4와 3이라 3 쪽을 옮기면 「당일」 목록이 끝납니다. 답은 1 입니다.

작은 번호 쪽 포인터를 그냥 옮겨도 되는 것은 목록이 정렬돼 있어서입니다. 상대 목록에 남은 번호는 모두 그보다 큽니다. 지나친 번호가 상대 목록에서 나올 일이 없습니다.

포인터는 뒤로 가지 않습니다. 한 번 비교할 때마다 적어도 하나가 한 칸 나아갑니다. 비교 횟수는 두 목록 길이의 합을 넘지 않습니다. 문서가 천만 개여도 두 단어의 목록만 읽으면 됩니다.

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

단어가 들었는지만 본다

불리언 검색은 단어가 문서에 들었는지만 봅니다. 단어가 몇 번 나오는지, 어디에 나오는지는 안 봅니다.

그래서 「배송 AND 안내」는 두 단어가 붙어 있든 멀리 떨어져 있든 똑같이 맞습니다. 「배송 안내」라는 붙은 구절로 찾으려면 단어의 위치까지 적어 두는 구문 검색이 따로 필요합니다.

맞거나 안 맞거나

불리언 검색의 답은 문서의 집합입니다. 집합 안의 문서끼리는 순서가 없습니다. 「배송」이 열 번 나온 문서와 한 번 나온 문서가 똑같이 「맞음」입니다.

이 성질 때문에 결과 수를 맞추기가 어렵습니다. AND 를 하나 더 걸면 결과가 0건이 되기 쉽습니다. OR 로 넓히면 수천 건으로 불어나기 쉽습니다. 쓰는 사람은 조건을 넣었다 뺐다 하며 알맞은 수를 찾아야 합니다.

결과가 수천 건일 때 무엇부터 볼지도 알려 주지 않습니다. 사람이 결과를 처음부터 끝까지 훑어야 합니다.

이 곤란을 풀려고 문서가 검색어와 얼마나 맞는지 점수를 매기는 방식이 나왔습니다. 그 점수가 관련도 점수입니다.

점수가 높은 문서부터 늘어놓는 일은 랭킹이라고 합니다. 랭킹이 있으면 사람은 맨 위 몇 건만 보면 됩니다.

관련도 점수를 매기는 대표 공식이 둘 있습니다. 하나는 TF-IDF(Term Frequency-Inverse Document Frequency, 단어 빈도-역문서 빈도)입니다. 다른 하나는 BM25(Best Matching 25)입니다. 둘 다 드문 단어가 여러 번 나오는 문서에 높은 점수를 줍니다.

오늘날 검색 엔진 안의 불리언 검색

점수 방식이 나왔다고 불리언 검색이 사라지지는 않았습니다. 검색 엔진은 대개 두 단계로 답합니다. 먼저 불리언 조건으로 후보 문서를 거릅니다. 그다음 남은 후보에만 관련도 점수를 매겨 순서를 정합니다.

사용자가 AND 를 직접 안 써도 이 필터링은 일어납니다. 검색창에 「당일 배송」을 치면 엔진은 이를 「당일 AND 배송」이나 「당일 OR 배송」 가운데 하나로 풀어 후보를 거릅니다. 어느 쪽으로 풀지는 엔진 설정이 정합니다.

쇼핑몰 검색에서 「신발 분류이고 재고가 있는 상품」만 남기는 필터링도 같은 불리언 연산입니다. 이런 조건은 점수에 보태지 않습니다. 맞느냐 아니냐만 보고 후보를 줄입니다.

조건에 맞는 문서를 하나도 빠뜨리면 안 되는 검색도 있습니다. 특허 조사, 판례 검색, 논문 문헌 조사가 그렇습니다. 불리언 검색은 조건에 맞는 문서를 한 건도 빼지 않고 결과에 넣습니다. 점수 방식은 흔히 점수가 높은 몇 건만 보여 주고 나머지를 끊습니다.

이런 곳에서는 검색하는 사람이 괄호와 연산자로 긴 불리언 검색어를 직접 짭니다. 같은 검색어를 다시 돌리면 같은 문서 집합이 나옵니다. 무엇을 찾았는지 기록으로 남기기도 쉽습니다.

쓸 때와 안 쓸 때

맞는 쓰임과 모자란 쓰임을 함께 놓아 봅니다.

관련 항목

불리언 검색을 받치는 논리와 집합 연산

불 대수 · 불리언 · 논리 연산자 · 교집합 · 합집합 · 차집합 · 드모르간 법칙 · 연산자 우선순위

불리언 검색이 올라서는 색인 구조

역색인 · 포스팅 리스트 · 용어 사전 · 스킵 리스트 · 순방향 색인

불리언 검색으로 거른 후보에 순서를 매기는 방식

관련도 점수 · 랭킹 · TF-IDF · BM25 · 벡터 공간 모델 · 확장 불리언 모델 · 재순위화

불리언 검색이 못 하는 일을 맡는 검색 방식

구문 검색 · 근접 검색 · 퍼지 검색 · 와일드카드 검색 · 접두사 검색 · 벡터 검색 · 시맨틱 검색 · 동의어

불리언 조건으로 검색 결과를 좁히는 기능

필터 · 패싯 · 검색 연산자 · 쿼리 파서

불리언 검색을 채택한 검색 라이브러리와 서버

Apache Lucene · Elasticsearch · OpenSearch · Solr

불리언 검색이 속하는 상위 분류

정보 검색 · 전문 검색 · 검색 엔진 · 검색 · 검색 모델