인덱스의 구성 부분 - 사전

이것은 내가 dev.to에 쓴 네 번째 문장이다.우리는 본고에서 첫 번째 구성 요소, 즉 사전을 토론하고, 다음 문장에서 다른 구성 요소, 즉 게시물 목록을 토론할 것이다.이 문장은 나의 이전 문장과 밀접한 관계가 있으니, 이 문장을 읽기 전에 먼저 좀 읽어서 더욱 잘 이해할 수 있도록 하세요.Please don't assume the dictionary as the python dictionary/HashMap. There is more to it. 😌

포괄할 주제

 * Overview and need for Dictionary
 * Supported Operations
 * Types of Dictionary
 * Sort-based Dictionary
 * Hash-based Dictionary
 * Which one is better?

개요

우리 는 이전 문장 에서 본 역렬 색인 의 간단한 표시 를 되돌아보자
In this article, we are going to focus on the term column in the Inverted Index representation in the above diagram.이 용어열은 우리 집합의 모든 단어/용어를 포함하기 때문에, 우리도 이를 역방향 색인 사전이라고 부른다.
🙋 그런데 왜 나는 사전 한 권이 필요합니까?
답안도 간단하다. 그림에서 보듯이 사전 용어의 주요 목적은 텍스트 집합의 용어 그룹을 관리하고 색인 용어 집합에서 발표 목록 위치까지 비추는 것이다.과금 목록 열은 데이터를 포함하지 않고 실제 데이터에 저장된 포인터/인용을 가리키며, 메모리나 디스크에서 사용할 수 있는 실제 텍스트 데이터에 대한 인용일 뿐입니다.

사전 지원 작업🚀

역방향 색인/검색 엔진의 "기본"사전은 일반적으로 다음과 같은 작업을 제공합니다.

사전에 새 항목 삽입

사전에서 키워드 검색/찾기:

특정 키/용어를 찾아 체크아웃 목록 항목으로 돌아갑니다.

접두사로 시작하는 용어의 항목을 찾습니다.

새로운 전송 데이터에 따라 사전 용어 항목을 업데이트합니다.삭제 작업도 그 중의 일부일 수 있다. 왜냐하면 낡은 용어를 삭제하는 것은 새로 전송된 데이터를 바탕으로 하는 사전 업데이트이기 때문이다.

우리는 이 글에서 검색/찾기와 삽입 조작을 이해할 것이다.
우리 아름다운 사전의 문제는 무엇입니까?❓
내 사전에 10000000개의 용어가 있다고 가정해 봐.나는 이 사전에서 "Scranton"이라는 단어를 검색할 계획이다.이 자체가 문제가 되었다. 사전에서 스캔/회색을 하면 O(n)의 시간 복잡도를 초래하기 때문이다.우리는 어떻게 그것을 줄일 수 있습니까?지금 앉아서 제가 가장 자주 사용하는 두 가지 방법으로 설명해 드릴게요.

사전 용어 유형 저장:

정렬 기반 사전

검색 트리

사전 순서표

해시 기반 사전.

마찬가지로 완벽한 해결 방안이 없으면 필요에 따라 유형을 선택할 수 있습니다.우리는 모든 실현의 장단점을 이해할 것입니다. 이것은 당신이 문제/장면에 따라 더 좋은 방법을 선택하는 데 도움을 줄 것입니다.

정렬 기반 사전👀

말 그대로 이 실현은 우리의 텍스트 집합(일명 사전)을 바탕으로 정렬 형식의 배열이다.이런 사전 정렬 형식은 두 가지 방식을 통해 실현할 수 있는데, 하나는 정렬 수조이고, 다른 하나는 검색 트리이다.정렬 수조에 대해서는 이진 검색을 사용하여 텍스트 집합 (사전이라고도 함) 을 검색하고, 검색 트리에 대해서는 트리를 사용합니다.

해시 기반 사전👀

해시 기반 사전에 대해 우리는 해시 표를 사용할 수 있다.그 중에서 모든 용어는 해시표에 상응하는 항목이 있다.우리가 특정 용어를 검색할 때, 해시표의 속도는 놀랍게도 빠르지만, 이것도 함정이 있다. 우리는 본문 뒤에서 토론할 것이다. (즉 접두사 일치)그 밖에 대부분의 사람들은 검색과 삽입이 해시 테이블에서 O(1)의 시간 복잡도로 발생한다고 생각하지만 사실은 그렇지 않다.이 점을 이해하려면 stackoverflow 에서 이 답을 읽을 수 있습니다

해시와 정렬 기반 사전 간의 비교🚀

해시표의 크기를 정확하게 선택하면 특정 용어를 검색하는 해시표는 정렬 기반 사전보다 통상적으로 더 빠르다.정렬 기반 방법과 달리 2진 검색이나 트리가 두루 다닐 필요가 없기 때문이다.

접두사가 일치하는 검색을 고려해 보겠습니다. 예를 들어 사전에서 "Jef*"를 검색하면 "Jef"-> Jeff Bezos, Jeffrey Archer 등으로 시작하는 모든 색인 항목과 일치해야 합니다. 이 요구에 따라 해시 테이블은 전체 해시 테이블 (즉 용어 집합) 을 스캔하는 시스템이 필요합니다. 정렬 기반 방법에서는 보통 O (log (n) 가 더 빠릅니다.
이 때문에 아마존 같은 사이트의 자동 완성 기능은com은 백그라운드 어딘가의 제품 디렉터리 데이터에 접두사를 사용합니다. 속도를 놀라게 하려면 O(n) 시간의 복잡도 내에서 사용할 수 없습니다. 이것은 반드시 O(log(n)) 이상이어야 합니다.이런 데이터 구조는 속도가 놀라운 검색 트리가 가장 좋다.
또한 이것은 모든 검색엔진이나 역방향 색인에 필요한 주요 기능입니다. 하루가 끝날 때 "lap"을 입력하고 그림과 같은 옵션을 얻을 수 있기 때문입니다.

(받아들여, 너는 이 기능을 좋아해, 너는 매일 그것을 사용하고, 이 빌어먹을 물건을 받아들여)😜

그러나 우리 인류의 경향에 따라 우리는 항상 누가 누구보다 더 좋은지 알고 싶어 한다. 그렇지?메시 VS 호날두?로버트 데니로 VS 알 파시노?dev.to VS.medium?🙄
🙋 그렇다면 어떤 정렬 기반 사전과 해시 기반 사전이 더 좋을까?

토마스 소엘은 해결책은 없고 따져봐야 한다고 말한 적이 있다.
따라서 토마스의 진술을 감안하면 답은 검색 트리의 정렬 기반 사전을 사용하는 것이다.(물론 조회 처리 시간에 있어서 적당한 균형이 있다.)

접두사 조회 지원, 예측 가능한 성능 외에 내가 왜'정렬 기반 인덱스가 더 좋다'고 말하는지 설명할 수 있는 또 다른 이유가 있다.루첸이라고 들어보셨나요?elastic search와 Solr under the hood가 사용하는 가장 유행하는 검색엔진입니다.
메모리 인덱스 Apache Lucene 전체 텍스트 검색 인덱스의 경우 Lucene은 정렬 기반 사전 방법을 사용합니다.내가 직접 원본 코드를 검사하는 것을 믿지 않을 것이다.여기 있다
(I have asked the Lucene committers to confirm this, will update this too after getting the confirmation from them)상금 Gyaan:
참고: SortedMap은 아름다운 붉은색과 검은색 나무에 불과합니다.🖖
또 토마스 콤(Thomas Cormem)의 신성한'알고리즘 소개'에서 "붉은색과 검은색 나무는 좋은 검색 나무"라고 말했다.증명은 309페이지 참조.나는 미래의 몇몇 게시물에서 이 점을 긍정적으로 이야기할 것이다.당신이 여기에서 링크를 가입할 수 있기를 바랍니다.
따라서 우리는 본고에서 사전 실현 간의 모든 주요 균형을 논의했다.다음 글에서 우리는 사전의 실현과 관련된 내용, 즉 용어의 표기화를 다시 한 번 연구할 것이다.지금까지 우리는 문장/문서 사이의'공간'만을 고려하여 용어를 식별했지만 아직 고려해야 할 다른 일이 많다.
그리고 당신이 이 글을 좋아하길 바랍니다. 그것은 당신에게 도움이 될 것입니다.여느 때와 마찬가지로, 나는 이 일련의 건의와 피드백을 받아들이고 싶다.