1-06-2. Inverted Index

Elasticsearch uses a structure called an inverted index, which is designed to allow very fast full-text searches. An inverted index consists of a list of all the unique words that appear in any document, and for each word, a list of the documents in which it appears.

Elasticsearch는 full-text 검색을 매우 빠르게 할 수 있도록 설계된, inverted index 라는 구조를 사용한다. inverted index는 특정 document에 나타나는 유일한 단어 모두의 목록과, 각각의 단어에 대해, 그것이 나타나는 document의 목록으로 구성되어 있다.

For example, let’s say we have two documents, each with a content field containing the following:

예를 들어, 두 개의 document를 가지고 있고, 각각은 다음과 같은 content field를 가지고 있다고 가정해 보자.

1. The quick brown fox jumped over the lazy dog
2. Quick brown foxes leap over lazy dogs in summer

To create an inverted index, we first split the content field of each document into separate words (which we call terms, or tokens), create a sorted list of all the unique terms, and then list in which document each term appears. The result looks something like this:

inverted index를 생성하기 위해, 먼저 각 document의 content field를 개별 단어(term 이나 token 이라 한다)로 분리하고, 유일한 단어 모두의 정렬된 목록을 생성하고, 그 다음에, 각 단어가 나타나는 document를 나열한다. 결과는 다음과 같다.

Term      Doc_1  Doc_2
-------------------------
Quick   |       |  X
The     |   X   |
brown   |   X   |  X
dog     |   X   |
dogs    |       |  X
fox     |   X   |
foxes   |       |  X
in      |       |  X
jumped  |   X   |
lazy    |   X   |  X
leap    |       |  X
over    |   X   |  X
quick   |   X   |
summer  |       |  X
the     |   X   |
------------------------

Now, if we want to search for quick brown, we just need to find the documents in which each term appears:

이제, quick brown 을 검색하려면, 각 단어가 나타나는 document만 찾으면 된다.

Term      Doc_1  Doc_2
-------------------------
brown   |   X   |  X
quick   |   X   |
------------------------
Total   |   2   |  1

Both documents match, but the first document has more matches than the second. If we apply a naive similarity algorithm that just counts the number of matching terms, then we can say that the first document is a better match—is more relevant to our query—than the second document.

두 document 모두가 일치한다. 그러나 첫 번째 document가 두 번째보다 더 많이 일치한다. 단순히 일치하는 단어의 수를 세는, similarity algorithm 을 적용하면, 첫 번째 document가 두 번째보다 더 많이 일치 한다고(query에 더 관련 있다고) 할 수 있다.

But there are a few problems with our current inverted index:

그런데, 현재의 inverted index에는 약간의 문제가 있다.

• Quick and quick appear as separate terms, while the user probably thinks of them as the same word.

  Quick 과 quick 이 서로 다른 단어로 나타난다. 하지만 사용자는 동일한 단어로 생각한다.

• fox and foxes are pretty similar, as are dog and dogs; They share the same root word.

  fox 와 foxes 는 dog 와 dogs 처럼 매우 유사하다. 이들은 동일한 원형(root word)를 공유한다.

• jumped and leap, while not from the same root word, are similar in meaning. They are synonyms.

  jumped 와 leap 은 동일한 원형을 가지지는 않지만 유사한 의미를 가지고 있다. 그들은 동의어(synonym)이다.

With the preceding index, a search for +Quick +fox wouldn’t match any documents. (Remember, a preceding + means that the word must be present.) Both the term Quick and the term fox have to be in the same document in order to satisfy the query, but the first doc contains quick fox and the second doc contains Quick foxes.

위의 index에서 +Quick +fox 로 검색하면 어떤 document와도 일치하지 않는다. (접두어 + 는 단어가 존재해야 한다는 것을 의미한다.) query를 만족시키기 위해서, Quick 과 fox 라는 두 단어는 동일한 document에 있어야 한다. 그러나 첫 번째 document는 quick fox 를 가지고 있고, 두 번째는 Quick foxes 를 가지고 있다.

Our user could reasonably expect both documents to match the query. We can do better.

사용자는 두 document 모두 query에 일치할 거라고 기대할 것이다. 우리는 더 잘 할 수 있다.

If we normalize the terms into a standard format, then we can find documents that contain terms that are not exactly the same as the user requested, but are similar enough to still be relevant. For instance:

단어를 표준 형태(standard format)으로 정규화한다면, 사용자가 request한 것과 정확하게 동일하지 않지만, 충분히 관련있는, 유사한 단어를 포함하는 document를 찾을 수 있다. 예를 들자면,

• Quick can be lowercased to become quick.

  Quick 을 소문자로 바꾸면 quick 이 된다.

• foxes can be stemmed--reduced to its root form—to become fox. Similarly, dogs could be stemmed to dog.

  foxes 를 형태소 분석 하면(원형으로 축소하면) fox 가 된다. 유사하게 dogs 는 dog 이 된다.

• jumped and leap are synonyms and can be indexed as just the single term jump.

  jumped 와 leap 은 동의어이므로 하나의 단어 jump 로 색인할 수 있다.

Now the index looks like this:

이제 index는 아래와 같다.

Term      Doc_1  Doc_2
-------------------------
brown   |   X   |  X
dog     |   X   |  X
fox     |   X   |  X
in      |       |  X
jump    |   X   |  X
lazy    |   X   |  X
over    |   X   |  X
quick   |   X   |  X
summer  |       |  X
the     |   X   |  X
------------------------

But we’re not there yet. Our search for +Quick +fox would still fail, because we no longer have the exact term Quick in our index. However, if we apply the same normalization rules that we used on the content field to our query string, it would become a query for +quick +fox, which would match both documents!

그러나 아직이다. +Quick +fox 로 검색하면 여전히 실패한다. index에는 정확한 단어 Quick 을 더 이상 가지지 않기 때문이다. 그러나, query string에 content field를 사용할 때, 동일한 정규화 규칙을 사용한다면, query는 +quick +fox 이 된다. 그러면 두 document 모두 일치하게 된다!

This is very important. You can find only terms that exist in your index, so both the indexed text and the query string must be normalized into the same form.

이는 매우 중요하다. index에 존재하는 단어만 검색할 수 있다. 따라서, 색인된 텍스트와 query string은 동일한 형식으로 정규화 되어야 한다.

This process of tokenization and normalization is called analysis, which we discuss in the next section.

이러한 분리(tokenization)와 정규화(normalization) 프로세스를 analysis(분석) 라 한다. 다음에 바로 이야기할 것이다.