2-5-6. Ngrams for Partial Matching

As we have said before, "You can find only terms that exist in the inverted index". Although the prefix, wildcard, and regexp queries demonstrated that that is not strictly true, it is true that doing a single-term lookup is much faster than iterating through the terms list to find matching terms on the fly. Preparing your data for partial matching ahead of time will increase your search performance.

"inverted index에 존재하는 단어만 검색할 수 있다" 라고, 이전에 이야기 했었다. 하지만, prefix, wildcard, regexp query에서는 이것이 엄격한 의미에서 사실이 아니라는 것을 보여준다. 하지만, 하나의 단어를 검색하는 것이, 즉석에서 일치하는 단어를 찾기 위해, 단어 목록을 순환하는 것 보다 더 빠르다는 것은 사실이다. 부분 일치를 위해, 미리 데이터를 준비하면, 검색 성능이 향상될 것이다.

Preparing your data at index time means choosing the right analysis chain, and the tool that we use for partial matching is the n-gram. An n-gram can be best thought of as a moving window on a word. The n stands for a length. If we were to n-gram the word quick, the results would depend on the length we have chosen:

색인 시에 데이터를 준비한다는 것은, 올바른 분석 chain을 선택한다는 것을 의미한다. 그리고, 부분 일치를 위해 사용할 도구는 n-gram 이다. n-gram은 단어에 따라 움직이는 윈도우(moving windows on a word)로서 최고의 아이디어가 될 수 있다. n 은 길이를 나타낸다. 만약 quick 이라는 단어를 n-gram으로 하면, 결과는 선택한 길이에 따라 달라진다.

• Length 1 (unigram): [ q, u, i, c, k ]
• Length 2 (bigram): [ qu, ui, ic, ck ]
• Length 3 (trigram): [ qui, uic, ick ]
• Length 4 (four-gram): [ quic, uick ]
• Length 5 (five-gram): [ quick ]

Plain n-grams are useful for matching somewhere within a word, a technique that we will use in Ngrams for Compound Words. However, for search-as-you-type, we use a specialized form of n-grams called edge n-grams. Edge n-grams are anchored to the beginning of the word. Edge n-gramming the word quick would result in this:

단순한 n-gram은 Ngrams for Compound Words에서 사용하는 기술로서, 단어 내 어딘가에서 일치하는 것에 유용하다. 그러나, instant search에서도, edge n-grams 라 불리는 n-gram의 특별한 형태를 사용한다. edge n-grams은 단어의 시작 부분에 고정되어 있다. 단어 quick 을 edge n-gram하면 결과는 다음과 같다.

• q
• qu
• qui
• quic
• quick

You may notice that this conforms exactly to the letters that a user searching for "quick" would type. In other words, these are the perfect terms to use for instant search!

"quick" 을 검색하려는 사용자가 입력할 문자에 정확히 부합한다는 알 수 있다. 즉, 이것은 instant 검색의 사용을 위한 최적의 조건이다.