How a CJK Bigram Tokenizer Powers Search in Nine Languages

This blog serves posts in nine languages, and every one of them needs working title search. The English titles split on spaces without any trouble. The Korean, Chinese, and Japanese titles do not, because those languages write words without spaces between them. One search box has to handle both worlds. The fix that made it work is a bigram tokenizer: for CJK text it indexes overlapping two-character windows, and for Latin text it keeps whole words. This post walks through why space splitting breaks, how the bigram tokenizer is built, and when you would want a heavier morphological analyzer instead.

Why splitting on spaces fails on CJK text

A tokenizer turns a string into the units you index and match against. The default tokenizer in most databases splits on whitespace and punctuation. For English that is a reasonable model of where words begin and end. The title "cursor pagination in firestore" becomes four tokens, and a search for "pagination" finds it.

Korean, Chinese, and Japanese do not put spaces between words. A Korean phrase like "전세보증금월세" is written as one unbroken run of characters, even though a reader parses it as several concepts. A whitespace tokenizer sees that whole run as a single token. The only query that matches is the exact full string, character for character. Search for "월세" alone and you get nothing, because "월세" is not a token, "전세보증금월세" is.

So the same tokenizer that works for English produces one giant useless token for CJK. You cannot pick one strategy and apply it everywhere. The tokenizer has to look at the text and decide, per character, which rule applies.

Bigrams: overlapping two-character windows

The idea behind a bigram tokenizer is to stop trying to find word boundaries in CJK text and instead index every adjacent pair of characters. Take "전세보증금" and slide a two-character window across it:

Five characters produce four bigrams. The windows overlap by one character, which is the part that makes search work. Because "보증" is now a token in its own right, a query for "보증" matches. So does "전세", and so does the full "전세보증금", which expands to the same four bigrams and matches when all of them are present.

The one rule you cannot break is that indexing and querying must use the exact same tokenizer. If the index stores bigrams but the query is passed through a whitespace tokenizer, the query token "전세보증금" will never equal any stored bigram, and the search returns nothing. This is the most common way a bigram search silently breaks. The document is there, the tokens are there, and every query comes back empty because the two sides disagree on how to cut the string. Route both paths through one function and the class of bug disappears.

Latin text does not go through the bigram path. Breaking "firestore" into "fi", "ir", "re", and so on would bloat the index and match on meaningless fragments. For scripts that already mark word boundaries with spaces, whole words are the right unit.

Detecting script per character with Unicode blocks

To mix the two strategies in one pass, the tokenizer classifies each character by its Unicode block. Characters sit in fixed numeric ranges, and the CJK scripts occupy known blocks. A small function decides whether a rune belongs to the bigram path:

func isCJK(r rune) bool {
	switch {
	case r >= 0x4E00 && r <= 0x9FFF: // CJK Unified Ideographs
		return true
	case r >= 0x3400 && r <= 0x4DBF: // CJK Extension A
		return true
	case r >= 0xAC00 && r <= 0xD7A3: // Hangul syllables
		return true
	case r >= 0x3040 && r <= 0x309F: // Hiragana
		return true
	case r >= 0x30A0 && r <= 0x30FF: // Katakana
		return true
	}
	return false
}

Hangul covers Korean, the ideograph blocks cover Chinese and the Han characters in Japanese, and the kana blocks cover the rest of Japanese. Anything outside these ranges, including Latin letters, digits, Thai, Hindi, and Vietnamese, takes the word path. Vietnamese is written in Latin script with diacritics and separates words with spaces, so it behaves like English here even though it is a CJK-adjacent language geographically.

The tokenizer walks the string rune by rune, collecting Latin characters into a running word and CJK characters into a running buffer. When it hits a boundary, whitespace, punctuation, or a switch from one script to the other, it flushes what it has:

func Tokenize(s string) []string {
	s = strings.ToLower(norm.NFKC.String(s))

	var tokens []string
	var latin, cjk []rune

	flushLatin := func() {
		if len(latin) > 0 {
			tokens = append(tokens, string(latin))
			latin = latin[:0]
		}
	}
	flushCJK := func() {
		tokens = append(tokens, bigrams(cjk)...)
		cjk = cjk[:0]
	}

	for _, r := range s {
		switch {
		case isCJK(r):
			flushLatin()
			cjk = append(cjk, r)
		case unicode.IsLetter(r) || unicode.IsDigit(r):
			flushCJK()
			latin = append(latin, r)
		default:
			flushLatin()
			flushCJK()
		}
	}
	flushLatin()
	flushCJK()
	return dedupe(tokens)
}

The bigram helper handles the sliding window, with a fallback for a run that is only one character long:

func bigrams(rs []rune) []string {
	if len(rs) == 0 {
		return nil
	}
	if len(rs) == 1 {
		return []string{string(rs)}
	}
	out := make([]string, 0, len(rs)-1)
	for i := 0; i+1 < len(rs); i++ {
		out = append(out, string(rs[i:i+2]))
	}
	return out
}

A title that mixes scripts, like "Firestore 색인", produces the Latin token "firestore" plus the bigram "색인" from the Korean part. Both go into the same token list, and a search in either language finds the post.

Normalizing before you tokenize

Two strings that look identical to a reader can differ byte for byte. A full-width Latin "Ａ" is a different code point from the plain "A". Some accented characters exist both as a single composed code point and as a base letter followed by a combining mark. If the index stores one form and the query arrives in the other, they will not match, even though a human sees the same text.

The tokenizer normalizes first with NFKC, then lowercases. NFKC is Unicode normalization form compatibility composition. It folds compatibility variants, so full-width characters collapse to their plain equivalents, and it composes base plus combining sequences into single code points where one exists. Lowercasing then removes case as a source of mismatch for Latin script.

import (
	"strings"

	"golang.org/x/text/unicode/norm"
)

func normalize(s string) string {
	return strings.ToLower(norm.NFKC.String(s))
}

Doing this once, at the top of the tokenizer, means every downstream step sees clean text. Because both indexing and querying call the same tokenizer, they both get the same normalization for free, and the two sides stay in agreement.

Storing tokens and querying with $all

Each post document carries a title_tokens array holding the output of the tokenizer for its title. At index time the tokens are computed once and written alongside the post:

doc := bson.M{
	"slug":         post.Slug,
	"lang":         post.Lang,
	"title":        post.Title,
	"title_tokens": Tokenize(post.Title),
}

A multikey index on title_tokens lets the database match on any element of the array. Search runs the incoming query through the identical tokenizer and asks for documents whose token array contains all of the query tokens:

func SearchFilter(query string) bson.M {
	tokens := Tokenize(query)
	if len(tokens) == 0 {
		return bson.M{}
	}
	return bson.M{
		"title_tokens": bson.M{"$all": tokens},
	}
}

The $all operator requires every query token to be present in the document, which gives an AND across tokens. For a CJK query this is what makes partial matching feel natural. A search for "보증금" becomes the bigrams "보증" and "증금", and any title containing that substring has both bigrams in its token array, so it matches. A title that contains only "보증" but not "증금" does not match, which is the behavior you want, since the user asked for the longer run.

There is one edge to know about. Bigram overlap can produce a match for a token sequence that appears out of order in the original text, because $all checks for presence, not adjacency. In practice, for short title search this is rare and harmless. If you need strict adjacency you would store positions and check them, which is more index and more query cost than title search justifies.

The tradeoffs: index size and one-character queries

Bigrams are not free. The first cost is index size. A CJK title of n characters produces n minus one tokens, and every one of them lands in the multikey index. Compared to a whitespace tokenizer that might emit one or two tokens for the same title, the bigram index is several times larger. For title search across a few thousand posts this is a small absolute number. For full body text across millions of documents it would be the dominant cost, and you would think harder before reaching for bigrams.

The second cost is the one-character query. A single CJK character cannot form a bigram, so the tokenizer falls back to emitting it as a lone token. That works only if single characters were also indexed, which they are here through the same one-character fallback in the bigrams helper. But a single character is a weak query. It matches a large fraction of documents and ranks poorly, so the result is close to useless even when it technically returns rows. Bigram search is built for queries of two characters or more, and short queries are where it is weakest.

Neither cost is a reason to avoid bigrams for title search. They are reasons to know the boundary of where the technique stays cheap.

When a morphological analyzer is the better choice

The alternative to bigrams is a morphological analyzer, a tokenizer that actually understands the language and splits text into real words. For Korean this means a tool that knows "전세보증금" is a compound and can separate the parts a reader would. For Japanese it means recognizing where one word ends and the next begins without any spaces to guide it.

A morphological analyzer produces cleaner, more meaningful tokens, and a smaller index, because it emits real words instead of every overlapping pair. The costs are real too. Each language needs its own analyzer and its own dictionary, the dictionaries are large and need updates as language use shifts, and the analysis is heavier per document than sliding a window. Supporting nine languages this way means integrating and maintaining several separate analyzers, each with its own quirks and failure modes.

The table below is the tradeoff in one view:

For this blog the choice was clear. Title search is a small, forgiving surface. Users type a few characters and expect matching posts, and they are not doing linguistic analysis. Bigrams give that with one language-neutral rule, no per-language dictionaries, and no analyzer to keep current in nine languages at once. If the search surface grew into ranked full-text search over article bodies, where token quality and index size start to matter more than simplicity, a morphological analyzer for the CJK languages would earn its cost. Match the tokenizer to the size of the problem, and for title search the bigram is the right size.