今日は、独自のFTSエンジンを作成します。この記事の終わりまでに、彼は1ミリ秒未満で数百万のドキュメントを検索できるようになります。「catを使用してすべてのドキュメントを返す」などの単純な検索クエリから始めて、より複雑な論理クエリをサポートするようにエンジンを拡張します。
注：最も有名なフルテキスト検索エンジンはLucene（およびElasticsearch）です。 そしてSolrはその上に構築されました）。
なぜFTSが必要なのですか
コードを書く前に、「各ドキュメントで検索ワードをチェックするgrepまたはループを使用できませんか？」と質問するかもしれません。はい、できます。しかし、それが常に最良のアイデアであるとは限りません。
ハウジング
英語のウィキペディアから注釈の断片を検索します。最新のダンプは、dumps.wikimedia.orgで入手できます。現在、解凍後のファイルサイズは913MBです。XMLファイルには60万を超えるドキュメントが含まれています。
サンプルドキュメント：
<title>Wikipedia: Kit-Cat Klock</title>
<url>https://en.wikipedia.org/wiki/Kit-Cat_Klock</url>
<abstract>The Kit-Cat Klock is an art deco novelty wall clock shaped like a grinning cat with cartoon eyes that swivel in time with its pendulum tail.</abstract>ドキュメントのアップロード
まず、非常に便利な組み込みパッケージを使用して、ダンプからすべてのドキュメントをロードする必要があります
encoding/xml。
import (
"encoding/xml"
"os"
)
type document struct {
Title string `xml:"title"`
URL string `xml:"url"`
Text string `xml:"abstract"`
ID int
}
func loadDocuments(path string) ([]document, error) {
f, err := os.Open(path)
if err != nil {
return nil, err
}
defer f.Close()
dec := xml.NewDecoder(f)
dump := struct {
Documents []document `xml:"doc"`
}{}
if err := dec.Decode(&dump); err != nil {
return nil, err
}
docs := dump.Documents
for i := range docs {
docs[i].ID = i
}
return docs, nil
}各ドキュメントには一意のIDが割り当てられます。簡単にするために、最初にロードされたドキュメントにはID = 0、2番目のID = 1というように割り当てられます。
初挑戦
コンテンツ検索
これですべてのドキュメントがメモリに読み込まれました。猫について言及しているドキュメントを探してみましょう。まず、すべてのドキュメントを調べて、サブストリングがないか確認しましょう
cat。
func search(docs []document, term string) []document {
var r []document
for _, doc := range docs {
if strings.Contains(doc.Text, term) {
r = append(r, doc)
}
}
return r
}私のラップトップでは、検索に103ミリ秒かかります-それほど悪くはありません。スポットが問題からいくつかのドキュメントをチェックすると、関数がキャタピラーとカテゴリという単語に満足を与えるが、大文字のCが付いたCatでは満足しないことがわかります。これはまさに私たちが探しているものではありません。 先に進む前に修正することが2つあります。
- 検索ケースを非依存にします（出力にCatも含まれるようにします）。
- サブストリングではなく、単語の境界を考慮してください（出力にcaterpillarやcommunicationのような単語がないようにします）。
正規表現で検索
両方の問題を解決する1つの明白な解決策は、正規表現です。
この場合、次のものが必要です
(?i)\bcat\b。
(?i)regexが大文字と小文字を区別しないことを意味します
\b単語の境界（片側に文字があり、反対側にはない場所）との対応を示します
しかし、今では検索に2秒以上かかりました。ご覧のとおり、60万件の適度なドキュメントでも、システムの速度が低下し始めました。このアプローチは簡単に実装できますが、拡張性はあまり高くありません。データセットが大きくなるにつれて、ますます多くのドキュメントをスキャンする必要があります。このアルゴリズムの時間の複雑さは線形です。つまり、スキャンするドキュメントの数はドキュメントの総数に等しくなります。60万ではなく600万のドキュメントがある場合、検索には20秒かかります。もっと良いものを考え出す必要があります。
反転インデックス
検索クエリを高速化するために、テキストを前処理してインデックスを作成します。
FTSの中核は、逆インデックスと呼ばれるデータ構造です。各単語を、その単語を含むドキュメントにリンクします。
例：
documents = {
1: "a donut on a glass plate",
2: "only the donut",
3: "listen to the drum machine",
}
index = {
"a": [1],
"donut": [1, 2],
"on": [1],
"glass": [1],
"plate": [1],
"only": [2],
"the": [2, 3],
"listen": [3],
"to": [3],
"drum": [3],
"machine": [3],
}以下は、反転インデックスの実際の例です。これは、用語の後にページ番号が続く本の索引です。
テキスト分析
インデックスの作成を開始する前に、ソーステキストをインデックス作成と検索に適した単語（トークン）のリストに分割する必要があります。
テキストアナライザーは、トークナイザーといくつかのフィルターで構成されています。
トークナイザー
トークナイザーは、テキスト解析の最初のステップです。そのタスクは、テキストをトークンのリストに変換することです。私たちの実装では、テキストを単語の境界で分割し、句読点を削除します。
func tokenize(text string) []string {
return strings.FieldsFunc(text, func(r rune) bool {
// Split on any character that is not a letter or a number.
return !unicode.IsLetter(r) && !unicode.IsNumber(r)
})
}> tokenize("A donut on a glass plate. Only the donuts.")
["A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"]フィルター
ほとんどの場合、テキストをトークンのリストに変換するだけでは不十分です。インデックス作成と検索を容易にするために、追加の正規化が必要になります。
小文字
検索ケースを非依存にするために、小文字フィルターはトークンを小文字に変換します。cAt、Cat、およびcaTという単語は、すべてcatに正規化されています。後でインデックスを参照するときに、検索クエリを小文字に正規化して、検索クエリcAtがCatという単語を見つけるようにします。
一般的な単語の削除
ほぼすべての英語のテキストは、次のような一般的な単語が含まれ、I、、またはこと。これらはストップワードと呼ばれ、ほとんどすべてのドキュメントに存在するため、削除する必要があります。 「公式の」ストップワードリストはありません。OECリストのトップ10を削除しましょう。自由に補足してください：
var stopwords = map[string]struct{}{ // I wish Go had built-in sets.
"a": {}, "and": {}, "be": {}, "have": {}, "i": {},
"in": {}, "of": {}, "that": {}, "the": {}, "to": {},
}
func stopwordFilter(tokens []string) []string {
r := make([]string, 0, len(tokens))
for _, token := range tokens {
if _, ok := stopwords[token]; !ok {
r = append(r, token)
}
}
return r
}> stopwordFilter([]string{"a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"})
["donut", "on", "glass", "plate", "only", "donuts"]ステミング
文法規則により、ドキュメントにはさまざまな形式の単語があります。ステミングはそれらを基本的な形に縮小します。例えば、釣り、釣り、と漁師すべての沸騰メインにダウン魚の形。
ステミングの実装は簡単な作業ではなく、この記事では取り上げません。既存のモジュールの1つを見てみましょう：
import snowballeng "github.com/kljensen/snowball/english"
func stemmerFilter(tokens []string) []string {
r := make([]string, len(tokens))
for i, token := range tokens {
r[i] = snowballeng.Stem(token, false)
}
return r
}> stemmerFilter([]string{"donut", "on", "glass", "plate", "only", "donuts"})
["donut", "on", "glass", "plate", "only", "donut"]注：ステマーは常に正しく機能するとは限りません。たとえば、航空会社をairlinに短縮する場合があります。
アナライザーの組み立て
func analyze(text string) []string {
tokens := tokenize(text)
tokens = lowercaseFilter(tokens)
tokens = stopwordFilter(tokens)
tokens = stemmerFilter(tokens)
return tokens
}トークナイザーとフィルターは、文をトークンのリストに変換します。
> analyze("A donut on a glass plate. Only the donuts.")
["donut", "on", "glass", "plate", "only", "donut"]トークンはインデックス作成の準備ができています。
インデックスの作成
反転インデックスに戻りましょう。各単語をドキュメントIDと照合します。組み込みのデータタイプは、マップの保存（表示）に適しています
map。キーはトークン（文字列）になり、値はドキュメントIDのリストになります。
type index map[string][]intインデックスを作成する過程で、ドキュメントが分析され、それらの識別子がマップに追加されます。
func (idx index) add(docs []document) {
for _, doc := range docs {
for _, token := range analyze(doc.Text) {
ids := idx[token]
if ids != nil && ids[len(ids)-1] == doc.ID {
// Don't add same ID twice.
continue
}
idx[token] = append(ids, doc.ID)
}
}
}
func main() {
idx := make(index)
idx.add([]document{{ID: 1, Text: "A donut on a glass plate. Only the donuts."}})
idx.add([]document{{ID: 2, Text: "donut is a donut"}})
fmt.Println(idx)
}すべてが機能しています！ディスプレイの各トークンは、そのトークンを含むドキュメントのIDを参照します。
map[donut:[1 2] glass:[1] is:[2] on:[1] only:[1] plate:[1]]お問い合わせ
インデックスへのクエリには、インデックス作成に使用したものと同じトークナイザーとフィルターを適用します。
func (idx index) search(text string) [][]int {
var r [][]int
for _, token := range analyze(text) {
if ids, ok := idx[token]; ok {
r = append(r, ids)
}
}
return r
}> idx.search("Small wild cat")
[[24, 173, 303, ...], [98, 173, 765, ...], [[24, 51, 173, ...]]そして今、ついに、猫について言及しているすべての文書を見つけることができます。60万のドキュメントを検索するのに、1ミリ秒（18μs）もかかりませんでした。
逆インデックスを使用すると、検索クエリの時間の複雑さは検索トークンの数に比例します。上記のクエリの例では、入力テキストの分析に加えて、3つのマップ検索のみが実行されます。
論理クエリ
前のリクエストは、トークンごとにリンクされていないドキュメントのリストを返しました。ただし、通常、小さな野生の猫を検索すると、small、wild、catの両方を含む結果のリストが返されることが期待されます。次のステップは、リスト間の共通部分を計算することです。したがって、すべてのトークンに対応するドキュメントのリストを取得します。
幸い、反転インデックスのIDは昇順で挿入されます。 IDがソートされているため、リスト間の交差を線形時間で計算できます。この関数は
intersection、2つのリストを同時に繰り返し、両方に存在するIDを収集します。
func intersection(a []int, b []int) []int {
maxLen := len(a)
if len(b) > maxLen {
maxLen = len(b)
}
r := make([]int, 0, maxLen)
var i, j int
for i < len(a) && j < len(b) {
if a[i] < b[j] {
i++
} else if a[i] > b[j] {
j++
} else {
r = append(r, a[i])
i++
j++
}
}
return r
}更新されたもの
searchは、指定されたクエリテキストを解析し、トークンを探し、IDリスト間の指定された交差を計算します。
func (idx index) search(text string) []int {
var r []int
for _, token := range analyze(text) {
if ids, ok := idx[token]; ok {
if r == nil {
r = ids
} else {
r = intersection(r, ids)
}
} else {
// Token doesn't exist.
return nil
}
}
return r
}Wikipediaダンプには、small、wild、catという単語を同時に含む2つのドキュメントのみが含まれています。
> idx.search("Small wild cat")
130764 The wildcat is a species complex comprising two small wild cat species, the European wildcat (Felis silvestris) and the African wildcat (F. lybica).
131692 Catopuma is a genus containing two Asian small wild cat species, the Asian golden cat (C. temminckii) and the bay cat.検索は期待どおりに機能します！
ちなみに、私は最初にカトプムについて学びました、ここにそれらの1つがあります：
結論
そこで、フルテキスト検索エンジンを作成しました。そのシンプルさにもかかわらず、それはより高度なプロジェクトのための強固な基盤を提供することができます。
パフォーマンスを大幅に向上させ、検索をより便利にする多くの側面については触れていません。さらなる改善のためのいくつかのアイデアは次のとおりです。
- 論理演算子ORおよびNOTを追加します。
- ディスクにインデックスを保存します。
- アプリケーションを再起動するたびに、インデックスの復元には時間がかかります。
- 大きなインデックスはメモリに収まらない場合があります。
- アプリケーションを再起動するたびに、インデックスの復元には時間がかかります。
- IDセットを格納するために、メモリとCPUに最適化されたデータ形式を試してください。咆哮するビットマップを見てください。
- ドキュメントの複数のフィールドにインデックスを付けます。
- 結果を関連性で並べ替えます。
すべてのソースコードはGitHubで公開されています。