fbpx
17 C
София

Нека напишем пълнотекстова търсачка на програмния език Go

Оригиналът е на Artem Krylysov

Най-четени

Даниел Десподов
Даниел Десподовhttps://www.kaldata.com/
Ежедневен автор на новини. Увличам се от съвременни технологии, оръжие, информационна безопасност, спорт, наука и концепцията Internet of Things.

Пълнотекстовото търсене е един от инструментите, които използваме на практика всеки ден., когато търсим някаква информация в интернет. Това е Full-Text Search (FTS) – метод  за търсене на текст в колекция от документи. Всеки документ може да има препратка към уеб страница, вестникарска статия, съобщение в електронната поща или към някакъв друг структуриран текст.

Нека да напишем свой собствен FTS енджин. В края на тази статия той ще може да извършва търсене в милиони документи за по-малко от една милисекунда. Да започнем с нещо съвсем просто, от типа на ‘Да се извадят всички документи с думата cat’, а след това да разширим възможностите на този енджин за поддръжката на по-сложни логически базирани запитвания.

Забележка: най-известният енджин за пълнотекстово търсене към днешен ден е Luceneкакто и Elasticsearch и Solr, базирани на него.

За какво е необходим FTS

Преди да започнем да пишем сорс кода, може би някой ще запита: ‘А не може ли просто да използваме grep или някакъв цикъл с проверката на всеки документ за търсената дума?’. Може разбира се. Но това съвсем не е най-добрата идея.

Основата

Ще търсим фрагменти от анотацията на англоезичната Уикипедия. Последният дъмп може да бъде взет по адреса dumps.wikimedia.org. Към днешен ден размерът на файла след разкомпресирането е 913 MB. В този XML файл има над 600 хиляди документа.

Ето един пример на такъв документ:

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

Зареждане на документите

Първоначално е необходимо да заредим всички документи от дъмпа, което може да стане с използването на удобния интегриран в Go пакет 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, вторият 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 милисекунди, което не е толкова зле. Но ако проверим някои от получените резултати ще видим, че тази функция изкарва още и думите caterpillar и category, но не и Cat с главно C. Ясно е, че съвсем не се е получило това, което ни трябва.

Пред да продължим, да уточним две неща:

  • Трябва да направим търсенето да не зависи от главните и малките букви (за да можем да получим както cat, така и Cat)
  • Трябва да се съобразим с границите на думите и да не използваме само низ (за да не излизат и думите caterpillar и category)
Търсене с помощта на регулярни изрази

Едно от очевидните решения, което решава и двата проблема, е използването на регулярни изрази.

В нашия случай на нас ни трябва израза (?i)\bcat\b:

  • (?i) означава търсенето да не е чувствително към главните и малките букви
  • \\b указва за съответствие с границите на думите – мястото, където от едната и/или другата страна има символ
func search(docs []document, term string) []document {
    re := regexp.MustCompile(`(?i)\b` + term + `\b`) // Don't do this in production, it's a security risk. term needs to be sanitized.
    var r []document
    for _, doc := range docs {
        if re.MatchString(doc.Text) {
            r = append(r, doc)
        }
    }
    return r
}

Само че сега търсенето отнема повече от две секунди. Виждаме, че системата започна да се бави дори и при един твърде скромен комплект от 600 000 документа. Въпреки че този подход е съвсем лесен за реализиране, той не се мащабира добре. С увеличаването на данните, в случая документите, ще трябва да бъдат сканиране повече материали. Времевата сложност на този алгоритъм е линейна и ако имаме комплект от около 6 милиона документа, вместо 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"]
Филтрите

В повечето случаи е недостатъчно единствено преобразуването на текста в списък с токени. За да се облекчи индексирането и търсенето е необходима допълнителна нормализация.

Малки букви

За да бъде търсенето нечувствително към малките и големите букви, ще преобразуваме всички токени да станат с малки букви. По този начин думите cAtCat и caT ще се нормализират до cat. По-късно, при използването на индекса, ще преобразуваме и подадените заявки към малки букви – ако бъде подадено запитването cAt, то търсачката ще търси cat.

func lowercaseFilter(tokens []string) []string {
    r := make([]string, len(tokens))
    for i, token := range tokens {
        r[i] = strings.ToLower(token)
    }
    return r
}
> lowercaseFilter([]string{"A", "donut", "on", "a", "glass", "plate", "Only", "the", "donuts"})

["a", "donut", "on", "a", "glass", "plate", "only", "the", "donuts"]
Премахване на думите за обща употреба

Почти всеки англоезичен текст съдържа думи като aIThe или be. Те често се наричат стоп-думи и присъстват във всички документи. Трябва да ги премахнем.

Няма никакъв официален списък на стоп-думите. Нека премахнем топ-10 от тях според списъка OEC. Не се притеснявайте да го допълвате:

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"]
Стъминг

Според граматичните правила, в документите има различни форми на думите. Стъмингът ги привежда към основната им форма. Така например, fishingfished и fisher се преобразуват в основната форма fish.

Реализацията на стъминга не е тривиална задача и няма да се разглежда в тази статия. Ние ще използваме един от добре известните софтуерни модули.

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

Забележка: Стъмърите не винаги работят коректно. Например, някои от тях съкращават airline до 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"]

Изграждане на индекса

Да се върнем към инвертирания индекс. Той съпоставя всяка дума с идентификаторите на документите. Това е нещо като карта, за която е идеален типа данни map, който си е вграден в програмния език Go. Ключът ще бъде токенът (стринг), а за значението – списъка с идентификаторите на документите:

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

Всичко работи! Всеки токен в картата се отнася към идентификатора на документите, които съдържат този токен:

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

Заявките

За подаване на заявките/запитванията към индекса, ще използваме същите токенизатор и филтри, които използвахме при индексирането:

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

И сега, най-накрая може да намерим всички документи, в които става дума за котки. Търсенето в 600 хиляди документа отне по-малко от една милисекунда (18 микросекунди)!

При използването на инвертиран индекс времевата сложност на запитванията е линейна към броя на токените. В извършеното по-горе запитване, освен анализа на входния текст, се извършват само три търсения в картата.

Логическите заявки

Предишната подадена заявка връща несвързан списък от документи за всеки токен Но все пак ние очакваме, че при подаването на заявка с текста small wild cat ще излязат няколко резултата, които ще включват едновременно  smallwild и cat. Тоест, следващата стъпка ще бъде пресмятането на пресичането между различните списъци. По този начин ще получим списъка с документи, който съответства на всички токени.

За щастие, идентификаторите в нашия инвертиран списък са вмъкнати по реда на тяхното нарастване. И тъй като ID-тата са сортирани, можем да изчислим пресичанията между списъците в линейно време. Функцията intersection едновременно извършва итерацията за два списъка и събира техните идентификатори:

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
}

В дъмпа на Уикипедия има само два документа, които едновременно съдържат думите smallwild и cat:

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

Търсачката работи точно както трябва!

Между другото, по този начин за първи път разбрах какво са катопумите. Ето една от тях:

Изводи

И така, ние създадохме енджин за пълнотекстово търсене. Въпреки своята простота, той може да бъде една много здрава основа за по-големи проекти.

Има аспекти, които значително могат да повишат производителността и да направят търсенето по-удобно. Ето някои от възможните подобрения:

  • Да се добави използването на логическите оператори OR и NOT
  • Индексът да се съхранява записан на диска, понеже неговото съставяне всеки път в оперативната памет отнема известно време, а и големите индекси могат и да не се съберат
  • Да се използват специално оптимизираните за съвременните процесори нови формати на данните запис на ID. Да се разгледа проекта Roaring Bitmaps
  • Да се направи индексиране по няколко полета на документа
  • Резултатите да се сортират по релевантност

Целят сорс код е публикуван в GitHub.


Коментирайте статията в нашите Форуми. За да научите първи най-важното, харесайте страницата ни във Facebook, и ни последвайте в Telegram и Viber или изтеглете приложението на Kaldata.com за Android, iOS и Huawei!

Абонирай се
Извести ме за
guest

3 Коментара
стари
нови
Отзиви
Всички коментари

Нови ревюта

Подобни новини