FAST01

가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 정리 13장 검색어 자동 완성 시스템

6 min read

가상 면접 사례로 배우는 대규모 시스템 설계 기초 - 정리 13장 검색어 자동 완성 시스템

요약

가상 면접 사례로 배우는 대규모 시스템 설계 기초 리뷰

아키텍처 개념을 실제 설계 판단에 연결하기 위한 참고 노트입니다.

핵심 포인트

  • 가상 면접 사례로 배우는 대규모 시스템 설계 기초 리뷰
  • 가상 면접 사례로 배우는 대규모 시스템 설계 기초
  • 13장 검색어 자동 완성 시스템
  • 설계
  • 트라이 자료구조

지식 그래프

정리 내용

가상 면접 사례로 배우는 대규모 시스템 설계 기초

학습 목적으로 정리한 내용으로 문제가 있다면 내리겠습니다.

(이 책은 한국어판 저작권은 에이전시 원을 통해 저작권자와의 독점 계약으로 인사이트에 있습니다. 저작권법에 의해 한국 내에서 보호를 받는 저작물이므로 무단전재와 무단 복제를 금합니다.)

13장 검색어 자동 완성 시스템

개략적으로는 시스템은 두 부분으로 나뉜다.

  • 데이터 수집 서비스 : 사용자가 입력한 질의를 실시간으로 수집하는 시스템이다. 데이터가 많은 애플리케이션에 실시간 시스템은 그다지 바람직하지 않지만 설계안을 만드는 출발점으로는 괜찮을 것이다.
  • 질의 서비스 : 주어진 질의에 다섯 개의 인기 검색어를 정렬해 내놓는 서비스이다.

설계

최적화 방안을 논의한다.

  • 트라이 자료구조
  • 데이터 수집 서비스
  • 질의 서비스
  • 규모 확장이 가능한 저장소
  • 트라이 연산

트라이 자료구조

관계형 데이터베이스를 이용해 질의문을 골라내는 방안은 효율적이지 않다. 이 문제는 Trie 접두어 트리라고도 하는 트라이를 사용해 해결할 것이다. 트라이 자료구조는 트리형태의 자료 구조로 루트 노드는 빈 문자열을 나타낸다. 각 노드는 글자 하나를 저장하며 26개의 자식 노드를 가질 수 있다. 각 트리 노드는 하나의 단어 또는 접두어 문자열을 나타낸다. tree, try, true, toy, wish, win 이 보관된 트라이이다. p : 접두어의 길이 n : 트라이 안에 노드 개수 c : 주어진 노드의 자식 개수

  • 접두어를 표현하는 노드를 찾는 시간 복잡도는 O(p)
  • 해당 노드부터 시작하는 하위 트리를 탐색하여 모든 유효 노드를 찾는 복잡도는 O(c)
  • 유효 노드들을 정렬하여 가장 인기있는 검색어 k개를 찾는 복잡도는 O(clogc) 트라이를 갱신하는 방법은 두가지가 있다.
  • 매주 한번 갱신하는 방법
  • 트라이의 각 노드를 개별적으로 갱신하는 방법 검색어 삭제
  • 혐오성, 폭력성, 성적이 노골적이거나 위협요소는 제거해야한다.
    • 필터 계층을 통해 질의어가 반환되지 않도록하는 방법
    • 물리적 삭제

학습 목적으로 정리한 내용으로 문제가 있다면 내리겠습니다.

(이 책은 한국어판 저작권은 에이전시 원을 통해 저작권자와의 독점 계약으로 인사이트에 있습니다. 저작권법에 의해 한국 내에서 보호를 받는 저작물이므로 무단전재와 무단 복제를 금합니다.)

출처

그래프 뷰