Clever Geek Handbook

Menulis mesin pencari teks lengkap di Go

Pencarian teks lengkap adalah salah satu alat yang kami gunakan hampir setiap hari ketika kami mencari beberapa informasi di Internet. Full-Text Search (FTS) adalah metode pencarian teks dalam kumpulan dokumen. Dokumen dapat ditautkan ke halaman web, artikel surat kabar, pesan email, atau teks terstruktur apa pun.



Hari ini kita akan membuat mesin FTS kita sendiri. Di akhir artikel ini, dia akan dapat mencari jutaan dokumen dalam waktu kurang dari satu milidetik. Kami akan mulai dengan kueri penelusuran sederhana seperti "Kembalikan semua dokumen dengan cat" dan kemudian memperluas mesin untuk mendukung kueri logis yang lebih kompleks.



Catatan: Mesin pencari teks lengkap paling terkenal adalah Lucene (dan juga Elasticsearch dan Solr dibangun di atasnya).



Mengapa Anda membutuhkan FTS



Sebelum Anda menulis kode apa pun, Anda mungkin bertanya: "Tidak bisakah Anda menggunakan grep atau loop yang memeriksa setiap dokumen untuk kata pencarian?" Ya kamu bisa. Tapi itu tidak selalu merupakan ide terbaik.



Perumahan



Kami akan mencari fragmen penjelasan dari Wikipedia bahasa Inggris. Dump terbaru tersedia di dumps.wikimedia.org . Saat ini, ukuran file setelah pembongkaran adalah 913 MB. File XML berisi lebih dari 600 ribu dokumen.



Contoh dokumen: 



<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>


Mengupload dokumen



Pertama, Anda perlu memuat semua dokumen dari dump menggunakan paket bawaan yang sangat praktis 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
}


Setiap dokumen diberi ID unik. Untuk mempermudah, dokumen yang dimuat pertama diberi ID = 0, ID kedua = 1, dan seterusnya.



Percobaan pertama



Pencarian konten



Sekarang kita memiliki semua dokumen yang dimuat ke dalam memori, mari kita coba menemukan yang menyebutkan kucing. Pertama, mari telusuri semua dokumen dan periksa apakah ada substring 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
}


Di laptop saya, pencarian membutuhkan waktu 103ms - tidak terlalu buruk. Jika tempat memeriksa beberapa dokumen dari masalah ini, kita dapat melihat bahwa fungsi memberikan kepuasan pada kata ulat dan kategori , tetapi tidak pada Cat dengan huruf kapital C . Ini bukanlah yang kita cari.



Ada dua hal yang harus diperbaiki sebelum melanjutkan:



  • Buat kotak pencarian tidak peka (sehingga keluarannya menyertakan Cat juga ).

  • Pertimbangkan batasan kata, bukan substring (sehingga tidak ada kata seperti ulat dan komunikasi di keluaran ).


Telusuri dengan ekspresi reguler



Salah satu solusi jelas yang menyelesaikan kedua masalah tersebut adalah ekspresi reguler .



Dalam hal ini, kami membutuhkan (?i)\bcat\b:



  • (?i) berarti ekspresi reguler tidak peka huruf besar / kecil

  • \b menunjukkan korespondensi dengan batas kata (tempat di mana ada karakter di satu sisi dan bukan di sisi lain)


Tapi sekarang pencariannya memakan waktu lebih dari dua detik. Seperti yang Anda lihat, sistem mulai melambat bahkan pada 600 ribu dokumen sederhana. Meskipun pendekatan ini mudah diterapkan, pendekatan ini tidak berskala dengan baik. Saat kumpulan data bertambah, semakin banyak dokumen perlu dipindai. Kompleksitas waktu dari algoritma ini adalah linier, yaitu jumlah dokumen yang akan dipindai sama dengan jumlah dokumen. Jika kami memiliki 6 juta dokumen, bukan 600 ribu, pencarian akan memakan waktu 20 detik. Kami harus menemukan sesuatu yang lebih baik.



Indeks terbalik



Untuk mempercepat kueri penelusuran, kami akan memproses teks tersebut dan membuat indeks.



Inti dari FTS adalah struktur data yang disebut indeks terbalik . Ini menghubungkan setiap kata ke dokumen yang berisi kata itu.



Contoh: 



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],
}


Di bawah ini adalah contoh nyata dari indeks terbalik. Ini adalah indeks dalam sebuah buku yang istilahnya diikuti dengan nomor halaman:







Analisis teks



Sebelum mulai membuat indeks, Anda perlu membagi teks sumber menjadi daftar kata (token) yang sesuai untuk pengindeksan dan pencarian.



Penganalisis teks terdiri dari tokenizer dan beberapa filter.







Tokenizer



Tokenizer adalah langkah pertama dalam penguraian teks. Tugasnya adalah mengubah teks menjadi daftar token. Penerapan kami memisahkan teks pada batas kata dan menghapus tanda baca: 



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"]


Filter



Dalam kebanyakan kasus, mengonversi teks menjadi daftar token tidaklah cukup. Normalisasi tambahan akan diperlukan untuk memfasilitasi pengindeksan dan pencarian.



Huruf kecil



Untuk membuat pencarian tidak peka huruf besar / kecil, filter huruf kecil mengonversi token menjadi huruf kecil. Kata cAt , Cat, dan caT dinormalisasi ke dalam bentuk cat . Nanti, jika mengacu pada indeks, kami juga menormalkan kueri penelusuran menjadi huruf kecil, sehingga kueri penelusuran cAt menemukan kata Cat .



Menghapus kata-kata umum



Hampir setiap teks bahasa Inggris mengandung kata-kata umum seperti a , I , The, atau be . Mereka disebut kata-kata berhenti dan ada di hampir semua dokumen, jadi mereka harus dihapus.



Tidak ada daftar stopword "resmi". Mari kita hilangkan 10 teratas di daftar OEC . Jangan ragu untuk melengkapinya: 



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"]


Stemming



Karena aturan tata bahasa, ada berbagai bentuk kata dalam dokumen. Stemming menguranginya menjadi bentuk dasar. Misalnya, memancing , memancing dan memancing semuanya diringkas menjadi bentuk ikan utama .



Menerapkan stemming bukanlah tugas yang sepele dan tidak tercakup dalam artikel ini. Mari kita ambil salah satu modul yang ada : 



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"]


Catatan: Stemmer tidak selalu bekerja dengan benar. Sebagai contoh, beberapa dapat mempersingkat maskapai ke airlin .



Merakit penganalisis



func analyze(text string) []string {
    tokens := tokenize(text)
    tokens = lowercaseFilter(tokens)
    tokens = stopwordFilter(tokens)
    tokens = stemmerFilter(tokens)
    return tokens
}


Tokenizer dan filter mengubah kalimat menjadi daftar token: 



> analyze("A donut on a glass plate. Only the donuts.")

["donut", "on", "glass", "plate", "only", "donut"]


Token siap untuk diindeks.



Membangun indeks



Mari kembali ke indeks terbalik. Ini cocok dengan setiap kata dengan ID dokumen. Tipe data bawaan berfungsi dengan baik untuk menyimpan peta (menampilkan) map. Kuncinya akan menjadi token (string), dan nilainya akan menjadi daftar ID dokumen: 



type index map[string][]int


Dalam proses membangun indeks, dokumen dianalisis dan pengenalnya ditambahkan ke peta: 



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)
}


Semuanya bekerja! Setiap token dalam tampilan mengacu pada ID dari dokumen yang berisi token itu: 



map[donut:[1 2] glass:[1] is:[2] on:[1] only:[1] plate:[1]]


Pertanyaan



Untuk kueri ke indeks, kami akan menerapkan tokenizer dan filter yang sama yang kami gunakan untuk mengindeks: 



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, ...]]


Dan sekarang, akhirnya, kami dapat menemukan semua dokumen yang menyebutkan kucing. Pencarian 600 ribu dokumen membutuhkan waktu kurang dari satu milidetik (18 Ξs)!



Dengan indeks terbalik, kompleksitas waktu kueri penelusuran adalah linier dengan jumlah token penelusuran. Dalam contoh kueri di atas, selain menganalisis teks masukan, hanya tiga pencarian peta yang dilakukan.



Pertanyaan logis



Permintaan sebelumnya mengembalikan daftar dokumen yang tidak ditautkan untuk setiap token. Namun kami biasanya mengharapkan penelusuran untuk kucing liar kecil mengembalikan daftar hasil yang berisi kucing kecil , liar, dan kucing . Langkah selanjutnya adalah menghitung persimpangan antara daftar. Dengan demikian, kami akan mendapatkan daftar dokumen yang sesuai dengan semua token.







Untungnya, ID dalam indeks terbalik kami dimasukkan dalam urutan menaik. Karena ID diurutkan, Anda dapat menghitung perpotongan antara daftar dalam waktu linier. Fungsi ini melakukan intersectioniterasi melalui dua daftar secara bersamaan dan mengumpulkan pengenal yang ada di keduanya: 



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
}


Yang diperbarui searchmengurai teks permintaan yang diberikan, mencari token dan menghitung persimpangan yang diberikan antara daftar 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
}


Sampah Wikipedia hanya berisi dua dokumen yang secara bersamaan berisi kata kecil , liar dan kucing : 



> 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.


Pencarian berfungsi seperti yang diharapkan!



Ngomong-ngomong, saya pertama kali belajar tentang catopum , ini salah satunya:







kesimpulan



Jadi, kami membuat mesin pencari teks lengkap. Terlepas dari kesederhanaannya, ini dapat memberikan dasar yang kokoh untuk proyek yang lebih maju.



Saya belum menyebutkan banyak aspek yang dapat meningkatkan kinerja secara signifikan dan membuat pencarian lebih nyaman. Berikut beberapa ide untuk perbaikan lebih lanjut:



  • Tambahkan operator logika ATAU dan BUKAN .

  • Simpan indeks di disk:

    • Perlu beberapa saat untuk memulihkan indeks setiap kali aplikasi dimulai ulang.

    • Indeks besar mungkin tidak muat di memori.
  • Bereksperimen dengan memori dan format data yang dioptimalkan CPU untuk menyimpan kumpulan ID. Lihatlah Roaring Bitmaps .

  • Mengindeks beberapa bidang dokumen.

  • Urutkan hasil berdasarkan relevansi.


Semua kode sumber dipublikasikan di GitHub .


More articles:


All Articles