파이썬 80줄로 만든 검색 엔진

 (alexmolas.com)
6P by GN⁺ | ★ favorite | 댓글 1개
  • microsearch는 검색 엔진 내부를 직접 이해하기 위한 장난감 구현으로, 핵심 검색 엔진 클래스는 80줄 미만이지만 크롤러·API·HTML 템플릿까지 포함하면 프로젝트는 더 큼
  • 작은 웹사이트와 블로그가 대형 검색엔진에서 잘 발견되지 않는 문제를 배경으로, 642개 RSS 피드에서 글을 수집해 검색 데이터를 만듦
  • asyncio 기반 비동기 크롤링으로 수집 시간이 20분에서 20초로 줄었고, 정리된 본문은 Parquet 데이터로 저장됨
  • 검색은 단어를 URL별 등장 횟수에 연결하는 역색인 위에서 동작하며, 결과 정렬에는 링크 기반 PageRank 대신 콘텐츠 기반 BM25를 사용함
  • FastAPI UI로 검색창과 결과 페이지를 제공하지만, 쿼리 연산자·n-gram 색인·쿼리/문서 확장·크롤링 중 색인 같은 기능은 아직 없음

microsearch의 목표와 범위

  • microsearch는 GitHub 저장소에 공개된 Python 검색 엔진 구현임
  • 목적은 프로덕션용 검색엔진이 아니라, 검색엔진이 내부에서 어떻게 동작하는지 보여주는 사용 가능한 장난감 예제를 만드는 것임
  • 검색 대상은 Google SEO 경쟁에서 잘 발견되지 않는 작은 웹사이트와 블로그에 가까움
  • 핵심 검색 엔진 구현은 80줄 미만이지만, 데이터 크롤러·API·HTML 템플릿 같은 보조 코드를 포함하면 프로젝트 전체는 더 큼
  • 구현은 Solr와 Lucene을 다루며 검색 엔진 동작을 더 깊게 이해하려는 과정에서 만들어짐

RSS 기반 크롤러

  • 검색할 데이터를 만들기 위해 블로그 RSS 피드를 크롤링함
  • 사용한 피드는 총 642개 RSS 피드임
  • 크롤링은 각 RSS 피드에서 글 URL을 추출하고, 글 HTML을 내려받은 뒤 본문 텍스트를 정리하는 흐름임
  • HTML 정리는 BeautifulSoup으로 script와 style을 제거하고, 줄바꿈과 공백을 정리해 텍스트로 변환함
  • aiohttp와 asyncio를 사용한 비동기 크롤링으로 실행 시간이 20분에서 20초로 줄어듦
  • 결과는 URL과 정리된 본문을 담은 DataFrame으로 만든 뒤 output.parquet에 저장함

역색인 구조

  • 검색 엔진의 첫 핵심 데이터 구조는 역색인임
  • 역색인은 키워드를 문서에 매핑해, 특정 단어가 어떤 문서에 등장하는지 빠르게 찾게 해줌
  • 구현은 dict[str, dict[str, int]] 형태의 defaultdict를 사용함
    • 바깥 키는 단어
    • 안쪽 키는 URL
    • 안쪽 값은 해당 단어가 그 URL의 문서에 등장한 횟수
  • SearchEngine 클래스는 두 개의 내부 딕셔너리를 가짐
    • _index: 단어별 URL 등장 횟수 저장
    • _documents: URL별 원문 콘텐츠 저장
  • index(url, content)는 콘텐츠를 정규화한 뒤 공백으로 분리하고, 각 단어의 URL별 등장 횟수를 증가시킴
  • bulk_index()는 URL과 콘텐츠 목록을 받아 여러 문서를 한 번에 색인함
  • get_urls(keyword)는 키워드를 정규화한 뒤 해당 단어를 포함하는 URL과 등장 횟수를 반환함

문자열 정규화와 기본 검색

  • 문자열 정규화는 문장 부호를 공백으로 바꾸고, 중복 공백을 정리한 뒤 소문자로 변환함
  • 대소문자 차이를 줄이기 위해 Foo와 foo는 같은 키워드로 처리됨
  • 예시 문서 두 개를 색인하면 foo 검색 결과는 두 문서 모두를 반환함
    • Foo: Hello, World! My name is Foo!
    • Bar: Hello, World! My name is Bar, I'm not Foo!
  • 이 단계에서는 문서가 검색어를 포함하는지와 몇 번 포함하는지만 알 수 있으므로, 결과 순서를 정하려면 별도 랭킹이 필요함

BM25 랭커

  • 검색 결과 정렬에는 BM25를 사용함
  • PageRank는 링크를 기반으로 문서를 랭킹하지만, BM25는 문서 콘텐츠를 기반으로 점수를 계산함
  • SearchEngine은 BM25 계산을 위해 기본 파라미터 k1=1.5, b=0.75를 가짐
  • 클래스는 랭킹 계산에 필요한 속성을 제공함
    • posts: 색인된 URL 목록
    • number_of_documents: 전체 문서 수
    • avdl: 평균 문서 길이
  • idf(kw)는 특정 키워드의 역문서빈도를 계산함
    • 전체 문서 수 N
    • 해당 키워드를 포함하는 문서 수 n_kw
    • log((N - n_kw + 0.5) / (n_kw + 0.5) + 1) 수식을 사용함
  • bm25(kw)는 해당 키워드를 포함하는 URL마다 BM25 점수를 계산함
  • search(query)는 쿼리를 정규화하고 단어로 나눈 뒤, 각 단어의 BM25 점수를 URL별로 합산해 반환함
  • 예시에서 foo만 검색하면 Foo 문서 점수가 Bar보다 높고, foo bar를 검색하면 Bar 문서 점수가 더 높아짐

FastAPI 인터페이스

  • 검색 엔진은 작은 FastAPI 앱으로 노출됨
  • 앱은 SearchEngine 인스턴스를 만들고, 시작 시 Parquet 데이터에서 URL과 콘텐츠를 읽어 bulk_index()로 색인함
  • 주요 라우트는 세 가지임
    • /: 검색 페이지를 렌더링하고 색인된 글 목록을 전달함
    • /results/{query}: 쿼리를 검색하고 상위 5개 URL을 결과 페이지에 표시함
    • /about: 소개 페이지를 렌더링함
  • 결과는 점수 기준 내림차순으로 정렬한 뒤 top-N URL만 선택함
  • UI와 UX는 개선 여지가 크지만, 검색은 빠르게 동작하고 결과도 나쁘지 않음

빠진 기능과 한계

  • 구현에는 실제 검색 엔진에서 기대할 수 있는 여러 기능이 빠져 있음
  • 쿼리 연산자가 없음
    • 예를 들어 Google의 how to build a search engine -solr처럼 특정 단어를 제외하는 검색을 지원하지 않음
  • n-gram 색인이 없음
    • "search engine"처럼 두 단어가 특정 순서로 등장하는 문서만 찾는 방식이 지원되지 않음
  • 쿼리 또는 문서 확장이 없음
    • engine을 검색해도 engines가 들어간 문서는 자동으로 검색되지 않음
  • 크롤링과 색인이 분리돼 있음
    • 문서를 받는 즉시 색인하는 방식으로 통합할 수 있고, 이 과정도 비동기로 만들 수 있음

다음 단계

  • 프로젝트를 통해 Solr가 내부에서 어떻게 동작하는지에 대한 직관이 더 생김
  • IO 중심 작업에서는 비동기 코드가 큰 효과를 낸다는 점도 확인됨
  • 다음 단계는 검색 엔진에 시맨틱 검색 기능을 추가하는 것임
  • 임베딩 모델과 ANN을 실험해 왔고, 그 기능을 microsearch에 넣는 것이 다음 작업임

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 이거 정말 멋짐. 로컬 테스트용으로 꽤 빠른 BM25 검색 엔진을 Pandas로 만들고 있음: https://github.com/softwaredoug/searcharray
    Pandas를 쓰는 이유는 BM25만으로는 부족하고, 최신성·인기도 같은 다른 요소를 pandas/numpy로 쉽게 계산해 결합하고 싶기 때문임
    참고로 구문 검색이 어려운 부분임. 구문 매칭에는 경계 사례가 많고, slop 같은 것도 고려해야 함. 위치 정보도 가능한 한 적은 메모리에 압축해야 함: https://github.com/softwaredoug/searcharray/blob/main/searcharray/utils/roaringish.py

    • 장난감 프로젝트에서 구문 매칭을 다뤄봤음: https://github.com/vasilionjea/lofi-dx/blob/main/test/search/inverted-search.test.ts#L140
      꽤 철저히 테스트했다고 생각하지만 피드백을 받으면 좋겠음. 위치 정보는 델타 인코딩하고 base36으로 인코딩했음
    • 감성 분석을 넣는 게 구문 처리에 도움이 됐는지, 아니면 오히려 해가 됐는지 궁금함. 구문은 다루기 어렵고 성능을 개선하려면 뭘 할 수 있을지 고민 중임
    • 이 글을 이렇게 빨리 찾아와 댓글을 단 게 궁금함. 관심 키워드를 찾으려고 첫 페이지를 훑는 검색 감시 도구 같은 걸 쓰는 건지, 아니면 우연인지 알고 싶음

  • 맞는 얘기임. 검색에서 어려운 부분 대부분은 데이터 규모를 다루는 데 있음. 로직 자체는 놀랄 만큼 쉽거나 쉽게 만들 수 있음
    물론 끝없이 복잡하게 만들 수도 있지만, 이 프로젝트는 불필요한 부분을 잘 덜어냈음. 검색 엔진을 더 크게 만드는 문제가 아니라 데이터를 물리적으로 더 작게 만들거나 신호 대 잡음비를 높이는 문제로 접근하면 상당히 멀리 갈 수 있음

  • src/microsearch/engine.py를 보면 SearchEngine.__init__(self, k1: float = 1.5, b: float = 0.75) 같은 코드가 있는데, k1이나 b가 뭔지 전혀 모르겠고 파일 전체에 주석이 하나도 없음
    요즘은 주석이 유행이 아닌 건가? _documents는 키가 URL이고 값이 그 URL의 내용일 것 같지만 틀릴 수도 있음. 검색 엔진을 만드는 법을 배우고 확장할 수 있는 자료가 될 수 있었을 텐데, 문서화를 하지 않아 코드 품질이 아쉽다

    • 그 부분은 글에서 설명하고 있고, 글 자체가 코드의 문서 역할을 함. BM25 링크는 수학적 배경으로 이어지고, BM25 매개변수를 조금만 더 찾아보면 어떻게 고르는지 다룬 관련 글도 나옴
    • 글 제목을 눈길 끌게 만들려면 코드 줄 수를 최대한 줄여야 했음 ;)
      농담은 제쳐두고, 보통은 문서와 코드가 함께 있는 게 더 낫다는 데 동의함. 다만 이 경우는 교육용 프로젝트라 코드와 문서를 나누고, 블로그 글에서 코드를 문서화하기로 했음
    • 모바일이라 자세히는 못 보지만, k1과 b는 TF-IDF나 BM25에서 쓰는 표준 가중치 값이고 여기서는 BM25 쪽임
      주석이 있으면 유용하겠지만, 이 문제에 익숙한 사람에게는 바로 알아볼 수 있는 이름이기도 함
    • k1과 b는 BM25 순위 함수의 조정 매개변수임. 원글 작성자가 새로 만든 이름이 아니라 거의 모든 구현과 교과서에서 이 변수명을 씀
      정보 검색 분야를 아는 사람이 이해하려면 오히려 k1과 b라고 이름 붙이는 게 맞음: https://en.wikipedia.org/wiki/Okapi_BM25
    • a: float 같은 흐름을 보면 Rich Hickey의 “타입이 필요한 게 아니라 제대로 된 이름이 필요하다”는 강연이 늘 떠오름
      Go에서 온 것처럼 느껴지는, 설명 없는 한 글자 변수명을 쓰고 타입 시스템을 이름 보조 도구처럼 남용하는 경향이 정말 싫음. 이름은 프로그램이 무엇을 하는지에 대한 의미 정보를 전달할 수 있으니 제대로 써야 함

  • 외부 의존성을 쓰면서 전체 \r\n 수가 아닌 코드 줄 수를 자랑하는 게 무슨 의미인지 모르겠음
    코드베이스를 재는 SI 단위는 없지만, 인지 부하는 어떻게든 측정해야 한다고 봄

    • 공식적인 기준은 아니지만 우리 팀은 가끔 https://grugbrain.dev를 빗대서 “이 코드는 grug하지 않다”거나 “이 코드는 꽤 grug하다”고 말함
    • 80줄짜리 검색 엔진 자체는 외부 의존성을 쓰지 않음. collections, math, string만 가져오고 전부 표준 라이브러리임
      다만 더 정확히는 “검색 엔진 엔진”이라고 부르는 게 맞을 수도 있음. 크롤러와 인터페이스는 그 80줄에 포함되지 않았지만 어떤 형태로든 필요하고, 제시된 구현은 줄 수와 라이브러리를 꽤 늘림. 그래도 그 라이브러리들은 검색 엔진 자체와 관련된 건 아님. pandas나 fastapi 같은 일반 의존성까지 세기 시작하면, 운영체제의 수백만 줄이나 네트워크 카드 펌웨어, 하드웨어 복잡도까지 세야 할 수도 있음
    • 이런 걸 80줄로 만들 수 있게 된 산업의 성과를 축하하면 안 될 이유가 있나?
    • 여기서는 의미가 있음. “Python 4000줄로 만든 검색 엔진”이었다면 대부분 그냥 지나쳤겠지만, 80줄이면 한 번 들여다볼 만큼 짧기 때문임
    • 예전 방식으로는 순환 복잡도가 있음

  • 마음에 듦. 검색 엔진과 함께 쓸 수 있는 20줄 미만 추천 엔진도 가능함. 클릭한 URL의 세션 로그를 보관한다면, 각 세션에서 현재 URL 뒤의 슬라이딩 윈도우를 보고 가까운 링크일수록 높은 가중치를 줘 추천 목록을 만들 수 있음
    추천 결과를 정렬해 상위 N개만 남기면 특정 URL에 대한 추천 URL 목록이 나옴. 조금 손보면 입력한 검색어와 클릭한 URL을 로그에 섞어서 맞춤법 제안도 뽑아낼 수 있음

  • 아주 멋지고 교육적임. 다만 배포는 하지 말 것 :-)
    예전에 비슷한 게 필요했는데 규모가 조금 더 커서 문서가 수만 개 정도였고, 답은 늘 그렇듯 sqlite였음. 구조적으로는 여기 있는 것과 같지만, 역색인 영속화 계층을 다른 사람이 대신 작성해준 형태임

    • SQLite FTS는 거의 모든 곳에 쓰고 있는데, 한 번도 실망시킨 적이 없음
    • 실제로 같은 수식까지 들어 있네. 이 댓글 덕분에 “이해의 전율” 같은 게 왔음

  • Google은 "search engine"처럼 큰따옴표로 검색하면 두 단어가 그 순서로 등장하는 결과만 보여줌
    적어도 일부 경우에는 그렇지만 아쉽게도 항상 그렇지는 않음. 고급 사용자가 원하는 건 “웹용 grep”이지, “Google이 보여주고 싶은 걸 말해주는 것”이 아님

    • “웹용 grep”을 실제로 원하는 사람은 거의 없다고 장담할 수 있음. 아주 작은 질의 확장만 하는 검색 엔진과 비교해도 웹용 grep은 명백히 나쁨
      Google이 질의를 해석할 때 너무 많은 자유를 행사하는 건 맞지만, 어떤 검색 엔진이든 하지 않는 것보다 확실히 나은 처리들이 많음. 지금 Google 검색의 문제는 왜 그런 결과가 나오는지 추론하기 어렵다는 데 있고, 문자열 비교에 임베딩을 너무 크게 의존해서 그런 것처럼 보임. "cat food"가 "dog restaurant"와 매칭되는 식으로, 임베딩 공간에서는 의미적으로 가깝지만 인간의 추론과는 맞지 않는 결과가 나올 때 답답함

  • 외부 라이브러리인 feedparser, bs4 등을 쓰면서 80줄 코드라고 말하는 건 공정하지 않다고 봄

    • elasticsearch 위에 만든 거라면 동의하겠지만, 실제 검색 엔진 부분이 그 80줄에 구현되어 있다면 공정하다고 봄. 가져온 라이브러리들은 직접 구현하지 않는 편이 맞는 종류임
      가끔 “나만의 검색 엔진 만들기”라는 글이 사실은 searxng나 yacy 설치 가이드인 경우가 있는데, 이건 그런 경우와 다름
    • 그 의존성이 매우 일반적이고 주류라면 괜찮다고 봄

  • 좋음. 여기에 퍼지 검색 기능을 추가하는 것도 크게 어렵지 않을 듯함. 예를 들어 "hackrnew" 검색이 "hackernews"와 매칭되도록, 접두 편집 거리가 어떤 임계값 이하인 결과를 찾는 방식임
    기본 아이디어는 추가 역색인을 하나 더 두되, 키를 문서 컬렉션에 있는 단어의 n-그램(보통 3-그램)으로 하고, 포스팅은 그 n-그램이 등장하는 단어 또는 단어 ID로 두는 것임. PED(x, y) <= delta이면 |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta라는 보조정리를 이용할 수 있음. 입력 x의 n-그램을 계산해 각 n-그램의 포스팅을 가져오고 중복을 합치면 각 후보 단어 y와 공유하는 n-그램 수를 얻음. 이 수가 기준보다 크면 그때만 실제 PED를 계산하고, 작으면 건너뛰어 비싼 계산을 크게 줄일 수 있음
    이렇게 얻은 단어 목록을 기존 색인에 질의하면 됨. 예전에 https://dont.watch/에서 클라이언트 측 JS 퍼지 검색 엔진을 만들 때 이 접근을 썼음. JS 코드 안을 보면 역색인과 압축된 n-그램 색인을 JS 파일로 그대로 전달하는 걸 볼 수 있음. 실제 검색 엔진은 외부 의존성 없이 약 300줄의 JS이고, 검색 결과 개선을 위한 아주 기본적인 휴리스틱만 들어 있음

    • 그 방식이면 색인 크기가 얼마나 늘어남?
답변달기