CJKバイグラムトークナイザーが9言語の検索を強化する仕組み
スペースベースのトークナイザーは、韓国語、中国語、日本語のテキストではうまく機能しません。ここでは、1つのインデックスで9つの言語を検索するバイグラム方式を紹介します。
このブログは9つの言語で記事を公開しており、そのすべてで機能するタイトル検索が必要です。英語のタイトルは、問題なくスペースで分割できます。韓国語、中国語、日本語のタイトルはそうではありません。これらの言語では単語間にスペースを入れずに記述するためです。1つの検索ボックスで、この両方の世界を扱う必要があります。これを機能させるための修正はバイグラムトークナイザーです。CJKテキストの場合は重複する2文字のウィンドウをインデックス化し、ラテン文字テキストの場合は単語全体を保持します。この記事では、なぜスペースによる分割がうまくいかないのか、バイグラムトークナイザーがどのように構築されているか、そして、どのような場合に代わりによりヘビーな形態素解析器が必要になるのかを順を追って説明します。
CJKテキストでスペースによる分割が失敗する理由
トークナイザーは、文字列をインデックス作成や照合の対象となる単位に変換します。ほとんどのデータベースのデフォルトのトークナイザーは、空白文字と句読点で分割を行います。英語の場合、これは単語の始まりと終わりを示す合理的なモデルです。「cursor pagination in firestore」というタイトルは4つのトークンになり、「pagination」で検索するとそれが見つかります。
韓国語、中国語、日本語では、単語の間にスペースを入れません。「전세보증금월세」のような韓国語のフレーズは、読み手には複数の概念として解釈されるにもかかわらず、一続きの文字列として書かれます。空白文字で分割するトークナイザーは、その全体を1つのトークンと見なします。一致する唯一のクエリは、文字単位で完全に一致する文字列そのものだけです。「월세」だけで検索しても何もヒットしません。なぜなら、「월세」はトークンではなく、「전세보증금월세」が1つのトークンだからです。
このように、英語では機能する同じトークナイザーが、CJKに対しては1つの巨大で役に立たないトークンを生成してしまいます。1つの戦略を選んで、それをどこにでも適用することはできません。トークナイザーはテキストを見て、文字ごとにどのルールを適用するかを判断する必要があります。
バイグラム: 重複する 2 文字のウィンドウ
バイグラム トークナイザーの背景にある考え方は、CJK テキストで単語の境界を見つけようとするのをやめ、代わりに隣接するすべての文字ペアをインデックスに登録するというものです。「전세보증금」を例にとり、2 文字のウィンドウをスライドさせてみましょう。
| ウィンドウの位置 | トークン |
|---|---|
| 1 から 2 | 전세 |
| 2 から 3 | 세보 |
| 3 から 4 | 보증 |
| 4 から 5 | 증금 |
5 文字から 4 つのバイグラムが生成されます。ウィンドウは 1 文字分重複しており、これが検索を機能させる部分です。「보증」はそれ自体がトークンになったため、「보증」のクエリは一致します。「전세」も同様で、完全な「전세보증금」も同様です。これは同じ 4 つのバイグラムに展開され、そのすべてが存在する場合に一致します。
破ってはならない唯一のルールは、インデックス登録とクエリでまったく同じトークナイザーを使用しなければならないということです。インデックスがバイグラムを保存しているのに、クエリが空白トークナイザーを通過する場合、クエリトークン「전세보증금」は保存されているどのバイグラムとも一致せず、検索は何も返しません。これは、バイグラム検索が静かに失敗する最も一般的な方法です。ドキュメントはそこにあり、トークンもそこにありますが、両サイドで文字列の分割方法が一致しないため、すべてのクエリが空の結果を返します。両方のパスを 1 つの関数を経由させれば、この種のバグはなくなります。
ラテン文字のテキストはバイグラムのパスを通りません。「firestore」を「fi」、「ir」、「re」などに分割すると、インデックスが肥大化し、意味のない断片で一致してしまいます。すでにスペースで単語の境界を示しているスクリプトでは、単語全体が適切な単位です。
Unicodeブロックによる文字ごとのスクリプトの検出
2つの戦略を1回のパスで組み合わせるために、トークナイザーは各文字をそのUnicodeブロックによって分類します。文字は固定された数値範囲にあり、CJKスクリプトは既知のブロックを占めています。小さな関数が、ルーンがバイグラムパスに属するかどうかを決定します。
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
}
ハングルは韓国語を、表意文字ブロックは中国語と日本語の漢字を、かなブロックは日本語の残りの部分をカバーします。ラテン文字、数字、タイ語、ヒンディー語、ベトナム語など、これらの範囲外のものはすべて、単語パスを取ります。ベトナム語は、発音区別符号付きのラテン文字で記述され、単語をスペースで区切るため、地理的にはCJKに隣接する言語ですが、ここでは英語のように動作します。
トークナイザーは文字列をルーンごとにたどり、ラテン文字を実行中の単語に、CJK文字を実行中のバッファに収集します。境界、空白、句読点、または一方のスクリプトからもう一方への切り替えに達すると、保持しているものをフラッシュします。
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)
}
バイグラムヘルパーはスライディングウィンドウを処理し、1文字だけの実行に対するフォールバックを備えています。
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
}
「Firestore 색인」のようにスクリプトが混在するタイトルは、ラテン語のトークン「firestore」と、韓国語部分からのバイグラム「색인」を生成します。両方とも同じトークンリストに入り、どちらの言語で検索してもその投稿が見つかります。
トークン化する前の正規化
読者にとって同一に見える2つの文字列が、バイト単位では異なる場合があります。全角のラテン文字「Ａ」は、通常の「A」とは異なるコードポイントです。一部のアクセント付き文字は、単一の合成済みコードポイントとしても、基本文字に結合マークが続く形としても存在します。インデックスが一方の形式を格納し、クエリがもう一方の形式で到着した場合、人間には同じテキストに見えても、それらは一致しません。
トークナイザーは、まずNFKCで正規化し、次に小文字化します。NFKCは、Unicode正規化形式の互換合成です。これは互換性のある異体字を畳み込むため、全角文字は通常の等価な文字に変換され、基本文字と結合シーケンスの組み合わせは、単一のコードポイントが存在する場合にはそれに合成されます。その後、小文字化によって、ラテン文字における大文字と小文字の不一致の原因が取り除かれます。
import (
"strings"
"golang.org/x/text/unicode/norm"
)
func normalize(s string) string {
return strings.ToLower(norm.NFKC.String(s))
}
これをトークナイザーの先頭で一度行うことで、後続のすべてのステップがクリーンなテキストを扱うことになります。インデックス作成とクエリの両方が同じトークナイザーを呼び出すため、両方で同じ正規化が自動的に行われ、両者の一致が保たれます。
トークンの保存と$allによるクエリ
各投稿ドキュメントは、そのタイトルのトークナイザーの出力を保持するtitle_tokens配列を持っています。インデックス作成時に、トークンは一度計算され、投稿と一緒に書き込まれます。
doc := bson.M{
"slug": post.Slug,
"lang": post.Lang,
"title": post.Title,
"title_tokens": Tokenize(post.Title),
}
title_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},
}
}
$all演算子は、ドキュメント内にすべてのクエリトークンが存在することを要求し、これによりトークン間のANDが実現されます。CJKクエリの場合、これが部分一致を自然に感じさせる要因です。「보증금」の検索は、バイグラムの「보증」と「증금」になります。その部分文字列を含むタイトルは、トークン配列に両方のバイグラムを持つため、マッチします。「보증」のみを含み「증금」を含まないタイトルはマッチしませんが、これはユーザーがより長い連続した文字列を要求したため、望ましい動作です。
知っておくべきエッジケースが1つあります。バイグラムの重複は、元のテキストで順序がばらばらに現れるトークンシーケンスに対してマッチを生成する可能性があります。なぜなら、$allは隣接性ではなく存在をチェックするからです。実際には、短いタイトルの検索ではこれはまれで無害です。厳密な隣接性が必要な場合は、位置を保存してそれらをチェックすることになりますが、これはタイトル検索が正当化する以上のインデックスとクエリコストを要します。
トレードオフ: インデックスサイズと1文字クエリ
Bigramにはコストがかかります。最初のコストはインデックスサイズです。n文字のCJKタイトルはn-1個のトークンを生成し、そのすべてがマルチキーインデックスに格納されます。同じタイトルに対して1つか2つのトークンを生成するであろう空白文字トークナイザーと比較して、bigramインデックスは数倍大きくなります。数千件の投稿にわたるタイトル検索では、これは絶対数としては小さいです。数百万のドキュメントにわたる全文テキスト検索では、それが主要なコストとなり、bigramに手を出す前にもっと慎重に考えることになるでしょう。
2番目のコストは1文字クエリです。単一のCJK文字はbigramを形成できないため、トークナイザーはそれを単独のトークンとして生成するフォールバック処理を行います。これは、単一文字もインデックス化されている場合にのみ機能しますが、ここではbigramsヘルパー内の同じ1文字フォールバックによってインデックス化されています。しかし、単一文字は弱いクエリです。それはドキュメントの大部分にマッチし、ランキングも低くなるため、技術的には行を返すとしても、その結果はほとんど役に立ちません。Bigram検索は2文字以上のクエリのために作られており、短いクエリがその最も弱い点です。
どちらのコストも、タイトル検索でbigramを避ける理由にはなりません。それらは、このテクニックが低コストで済む境界線を知るための理由となります。
形態素解析器の方が優れた選択肢である場合
バイグラムの代替案は、言語を実際に理解し、テキストを実際の単語に分割するトークナイザーである形態素解析器です。韓国語の場合、これは「전세보증금」が複合語であることを認識し、読者がするようにその部分を分割できるツールを意味します。日本語の場合、それは、区切りとなるスペースがなくても、ある単語がどこで終わり次の単語がどこで始まるかを認識することを意味します。
形態素解析器は、重なり合うすべてのペアの代わりに実際の単語を出力するため、よりクリーンで意味のあるトークンと、より小さなインデックスを生成します。コストもまた現実のものです。各言語は独自の解析器と辞書を必要とし、辞書は大規模で言語使用の変化に応じて更新が必要であり、解析はスライディングウィンドウ方式よりもドキュメントごとに負荷が大きくなります。この方法で9つの言語をサポートするということは、それぞれに独自の癖や障害モードがある複数の個別の解析器を統合し、維持することを意味します。
以下の表は、そのトレードオフを一目でわかるようにまとめたものです。
| 特性 | バイグラム | 形態素解析器 |
|---|---|---|
| 言語サポート | すべてのCJKに1つのルール | 言語ごとに1つの解析器 |
| トークンの品質 | 重なり合うペア | 実際の単語 |
| インデックスサイズ | 大きい | 小さい |
| 依存関係 | Unicodeデータ以外はなし | 言語ごとの辞書 |
| 短いクエリ | 弱い | より良い |
このブログにとって、選択は明らかでした。タイトル検索は、小規模で許容範囲の広い機能です。ユーザーは数文字を入力して一致する投稿を期待するだけで、言語的な分析を行っているわけではありません。バイグラムは、1つの言語中立なルールで、言語ごとの辞書を必要とせず、9つの言語で同時に最新の状態に保つべき解析器もなしに、それを実現します。もし検索対象が記事本文にわたるランキング付きの全文検索に拡大し、トークンの品質とインデックスサイズが単純さよりも重要になり始めた場合、CJK言語向けの形態素解析器はそのコストに見合う価値があるでしょう。問題の規模に合わせてトークナイザーを選ぶべきであり、タイトル検索にはバイグラムが適切なサイズです。