يعد البحث عن نص كامل أحد تلك الأدوات التي نستخدمها كل يوم تقريبًا عندما نبحث عن بعض المعلومات على الإنترنت. البحث عن نص كامل (FTS) هو طريقة للبحث عن نص في مجموعة من المستندات. يمكن أن يرتبط المستند بصفحة ويب أو مقالة جريدة أو رسالة بريد إلكتروني أو أي نص منظم.



سنقوم اليوم بكتابة محرك FTS الخاص بنا. بنهاية هذه المقالة ، سيكون قادرًا على البحث في ملايين المستندات في أقل من مللي ثانية. سنبدأ باستعلامات بحث بسيطة مثل "إرجاع جميع المستندات باستخدام cat" ثم نوسع المحرك لدعم الاستعلامات المنطقية الأكثر تعقيدًا.



ملاحظة: أشهر محرك بحث عن النص الكامل هو Lucene (بالإضافة إلى Elasticsearch و Solr مبني فوقه).

لماذا تحتاج FTS

قبل كتابة أي رمز ، قد تسأل: "ألا يمكنك استخدام grep أو حلقة للتحقق من كل مستند بحثًا عن كلمة البحث؟" نعم تستطيع. لكن هذه ليست دائمًا أفضل فكرة.

الإسكان

سنبحث عن أجزاء من التعليقات التوضيحية من ويكيبيديا باللغة الإنجليزية. أحدث تفريغ متاح في dumps.wikimedia.org . اعتبارًا من اليوم ، حجم الملف بعد التفريغ هو 913 ميغابايت. يحتوي ملف 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>

تحميل المستندات

أولاً ، تحتاج إلى تحميل جميع المستندات من ملف التفريغ باستخدام حزمة مضمنة سهلة الاستخدام 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
}

يتم تعيين معرف فريد لكل مستند. للتبسيط ، يتم تعيين معرف المستند الأول الذي تم تحميله = 0 ، والمعرف الثاني = 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 ).
  
  
• النظر في حدود الكلمة، وليس فرعية (بحيث لا توجد كلمات مثل كاتربيلر و الاتصالات في الناتج ).

البحث مع التعابير العادية

أحد الحلول الواضحة التي تحل كلتا المشكلتين هو التعبيرات النمطية .



في هذه الحالة نحتاج إلى (?i)\bcat\b:

• (?i) يعني أن التعبير العادي غير حساس لحالة الأحرف
  
  
• \b يشير إلى التطابق مع حدود الكلمات (مكان يوجد فيه حرف على جانب وليس على الجانب الآخر)

لكن الآن استغرق البحث أكثر من ثانيتين. كما ترون ، بدأ النظام في التباطؤ حتى على هيئة متواضعة من 600 ألف وثيقة. في حين أن هذا النهج سهل التنفيذ ، إلا أنه لا يتسع بشكل جيد. مع نمو مجموعة البيانات ، يلزم مسح المزيد والمزيد من المستندات ضوئيًا. التعقيد الزمني لهذه الخوارزمية خطي ، أي أن عدد المستندات المطلوب مسحها ضوئيًا يساوي إجمالي عدد المستندات. إذا كان لدينا 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"]

المرشحات

في معظم الحالات ، لا يكفي مجرد تحويل النص إلى قائمة الرموز المميزة. سيكون هناك حاجة إلى تسوية إضافية لتسهيل الفهرسة والبحث.

أحرف صغيرة

لجعل حالة البحث غير حساسة ، يحول مرشح الأحرف الصغيرة الرموز المميزة إلى أحرف صغيرة. يتم تطبيع الكلمات cAt و Cat و caT إلى شكل cat . لاحقًا ، عند الإشارة إلى الفهرس ، نقوم أيضًا بتطبيع استعلامات البحث إلى الأحرف الصغيرة ، بحيث يعثر استعلام البحث cAt على كلمة Cat .

إزالة الكلمات الشائعة

يحتوي كل نص إنجليزي تقريبًا على كلمات شائعة مثل a أو I أو The أو 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"]

ينبع

بسبب القواعد النحوية ، هناك أشكال مختلفة من الكلمات في المستندات. الاشتقاق يقلل منها إلى الشكل الأساسي. على سبيل المثال، الصيد ، صيد، و الصياد كل يغلي وصولا الى الرئيسي الأسماك شكل .



لا يعد تنفيذ الاشتقاق مهمة تافهة ولم يتم تناوله في هذه المقالة. لنأخذ إحدى الوحدات الموجودة :

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

ملاحظة: لا يعمل Stemmers دائمًا بشكل صحيح. على سبيل المثال، قد يكون بعض تقصير الطيران ل تذاكر الطيرا .

تجميع المحلل

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. سيكون المفتاح رمزًا مميزًا (سلسلة) ، وستكون القيمة قائمة بمعرفات المستندات:

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

استفسارات

بالنسبة إلى الاستعلامات على الفهرس ، سنطبق نفس الرمز المميز والمرشحات التي استخدمناها للفهرسة:

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

والآن ، أخيرًا ، يمكننا العثور على جميع المستندات التي تذكر القطط. استغرق البحث في 600 ألف مستند أقل من مللي ثانية (18 ميكرو ثانية)!



باستخدام الفهرس المقلوب ، يكون التعقيد الزمني لاستعلام البحث خطيًا مع عدد رموز البحث. في مثال الاستعلام أعلاه ، إلى جانب تحليل نص الإدخال ، يتم إجراء ثلاث عمليات بحث فقط على الخريطة.

استفسارات منطقية

أرجع الطلب السابق قائمة غير مرتبطة بالمستندات لكل رمز مميز. لكننا نتوقع عادة بالبحث عن القط البرية الصغيرة ل إرجاع قائمة النتائج التي تحتوي على كل صغيرة ، البرية، و القط . الخطوة التالية هي حساب التقاطع بين القوائم. وبالتالي ، سوف نحصل على قائمة بالوثائق المقابلة لجميع الرموز المميزة.







لحسن الحظ ، يتم إدخال المعرفات الموجودة في فهرسنا المقلوب بترتيب تصاعدي. نظرًا لأنه يتم فرز المعرفات ، يمكنك حساب التقاطع بين القوائم في الوقت الخطي. 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يوزع المحدث نص الاستعلام المحدد ويبحث عن الرموز ويحسب التقاطع المحدد بين قوائم المعرفات:

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
}

تفريغ ويكيبيديا يحتوي على اثنين فقط المستندات التي تحتوي في نفس الوقت عبارة صغيرة ، البرية و القط :

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

البحث يعمل كما هو متوقع!



بالمناسبة ، تعلمت لأول مرة عن catopums ، وهنا أحدها:

الاستنتاجات

لذلك ، قمنا بعمل محرك بحث كامل النص. على الرغم من بساطته ، يمكنه توفير أساس متين لمشاريع أكثر تقدمًا.



لم أذكر العديد من الجوانب التي يمكن أن تحسن الأداء بشكل كبير وتجعل البحث أكثر ملاءمة. فيما يلي بعض الأفكار لمزيد من التحسينات:

• أضف عوامل التشغيل المنطقية OR و NOT .
  
  
• فهرس التخزين على القرص:
  
  
  • تستغرق استعادة الفهرس بعض الوقت في كل مرة يتم فيها إعادة تشغيل التطبيق.
    
    
  • قد لا تتناسب الفهارس الكبيرة مع الذاكرة.
• جرب الذاكرة وتنسيقات البيانات المحسنة لوحدة المعالجة المركزية لتخزين مجموعات المعرفات. ألق نظرة على Roaring Bitmaps .
  
  
• فهرسة حقول متعددة من الوثيقة.
  
  
• فرز النتائج حسب الصلة.

يتم نشر جميع التعليمات البرمجية المصدر على GitHub .