البحث الثنائي Boolean search ودمج نتائج البحث وترتيبها

سنشرح في هذه المقالة حل التمرين التالي من المقالة السابقة فهرسة الصفحات وتحليل زمن تشغيلها، ثم ننفّذ شيفرة تدمج مجموعةً من نتائج البحث وترتِّبها بحسب مدى ارتباطها بكلمات البحث.

الزاحف crawler

لنمرّ أولًا على حل تمرين المقالة المشار إليها. كنا قد وفَّرنا الشيفرة المبدئية للصنف WikiCrawler وكان المطلوب منك هو إكمال التابع crawl. انظر الحقول المُعرَّفة في ذلك الصنف:

public class WikiCrawler {
    // يشير إلى المكان الذي بدأنا منه
    private final String source;

    // المفهرِس الذي سنخزن فيه النتائج
    private JedisIndex index;

    // رتل محددات الموارد الموحدة المطلوب فهرستها
    private Queue<String> queue = new LinkedList<String>();

    // يُستخدَم لقراءة الصفحات من موقع ويكيبيديا
    final static WikiFetcher wf = new WikiFetcher();
}

عندما نُنشِئ كائنًا من النوع WikiCrawler، علينا أن نُمرِّر قيمتي source و index. يحتوي المتغير queue مبدئيًا على عنصر واحد فقط هو source.

لاحِظ أن الرتل queue مُنفَّذ باستخدام قائمةٍ من النوع LinkedList، وبالتالي، تستغرق عملية إضافة العناصر إلى نهايته -وحذفها من بدايته- زمنًا ثابتًا، ولأننا أسندنا قائمةً من النوع LinkedList إلى متغير من النوع Queue، أصبح استخدامنا له مقتصرًا على التوابع المُعرَّفة بالواجهة Queue، أي سنَستخدِم التابع offer لإضافة العناصر و poll لحذفها منه.

انظر تنفيذنا للتابع WikiCrawler.crawl:

    public String crawl(boolean testing) throws IOException {
        if (queue.isEmpty()) {
            return null;
        }
        String url = queue.poll();
        System.out.println("Crawling " + url);

        if (testing==false && index.isIndexed(url)) {
            System.out.println("Already indexed.");
            return null;
        }

        Elements paragraphs;
        if (testing) {
            paragraphs = wf.readWikipedia(url);
        } else {
            paragraphs = wf.fetchWikipedia(url);
        }
        index.indexPage(url, paragraphs);
        queueInternalLinks(paragraphs);
        return url;
    }

السبب وراء التعقيد الموجود في التابع السابق هو تسهيل عملية اختباره. تُوضِّح النقاط التالية المنطق المبني عليه التابع:

إذا كان الرتل فارغًا، يعيد التابع القيمة الفارغة null لكي يشير إلى أنه لم يُفهرِس أي صفحة.
إذا لم يكن فارغًا، فإنه يقرأ محدد الموارد الموحد URL التالي ويَحذِفه من الرتل.
إذا كان محدد الموارد قيد الاختيار مُفهرَسًا بالفعل، لا يُفهرِّسه التابع مرة أخرى إلا إذا كان في وضع الاختبار.
يقرأ التابع بعد ذلك محتويات الصفحة: إذا كان التابع في وضع الاختبار، فإنه يقرؤها من ملف، وإن لم يكن كذلك، فإنه يقرؤها من شبكة الإنترنت.
يُفهرِس الصفحة.
يُحلِّل الصفحة ويضيف الروابط الداخلية الموجودة فيها إلى الرتل.
يعيد في النهاية مُحدّد موارد الصفحة التي فهرَسها للتو.

كنا قد عرضنا تنفيذًا للتابع Index.indexPage في نفس المقالة المشار إليها في الأعلى، أي أن التابع الوحيد الجديد هو WikiCrawler.queueInternalLinks.

كتبنا نسختين من ذلك التابع بمعاملات parameters مختلفة: تَستقبِل الأولى كائنًا من النوع Elements يتضمَّن شجرة DOM واحدةً لكل فقرة، بينما تَستقبِل الثانية كائنًا من النوع Element يُمثِل فقرة واحدة.

تمرّ النسخة الأولى عبر الفقرات، في حين تُنفِّذ النسخة الثانية العمل الفعلي.

    void queueInternalLinks(Elements paragraphs) {
        for (Element paragraph: paragraphs) {
            queueInternalLinks(paragraph);
        }
    }

    private void queueInternalLinks(Element paragraph) {
        Elements elts = paragraph.select("a[href]");
        for (Element elt: elts) {
            String relURL = elt.attr("href");

            if (relURL.startsWith("/wiki/")) {
                String absURL = elt.attr("abs:href");
                queue.offer(absURL);
            }
        }
    }

لكي نُحدِّد ما إذا كان مُحدّد موارد موحد معين هو مُحدّد داخلي، فإننا نفحص ما إذا كان يبدأ بكلمة "/wiki/". قد يتضمَّن ذلك بعض الصفحات التي لا نرغب في فهرستها مثل بعض الصفحات الوصفية لموقع ويكيبيديا، كما قد يستثني ذلك بعض الصفحات التي نريدها مثل روابط الصفحات المكتوبة بلغات أخرى غير الإنجليزية، ومع ذلك، تُعدّ تلك الطريقة جيدة بالقدر الكافي كبداية.

لا يتضمَّن هذا التمرين الكثير، فهو فرصة فقط لتجميع الأجزاء الصغيرة معًا.

استرجاع البيانات

سننتقل الآن إلى المرحلة التالية من المشروع، وهي تنفيذ أداة بحث تتكوّن مما يلي:

واجهة تُمكِّن المُستخدمين من إدخال كلمات البحث ومشاهدة النتائج.
طريقة لاستقبال كلمات البحث وإعادة الصفحات التي تتضمَّنها.
طريقة لدمج نتائج البحث العائدة من عدة كلمات بحث.
خوارزمية تُصنِّف نتائج البحث وتُرتِّبها.

يُطلَق على تلك العمليات وما يشابهها اسم استرجاع المعلومات Information retrieval.

أنشأنا بالفعل نسخةً بسيطةً من الخطوة رقم 2، وسنُركِّز في هذا التمرين على الخطوتين 3 و 4. قد ترغب بالعمل أيضًا على الخطوة رقم 1 إذا كنت مهتمًا ببناء تطبيقات الويب.

البحث المنطقي/الثنائي Boolean search

تستطيع معظم محركات البحث أن تُنفِّذ بحثًا منطقيًا، بمعنى أن بإمكانها دمج نتائج البحث الخاصة بعدة كلمات باستخدام المنطق الثنائي، ولنأخذ أمثلةً على ذلك:

تعيد عملية البحث عن "java AND programming" الصفحات التي تحتوي على الكلمتين "java" و "programming" فقط.
تعيد عملية البحث عن "java OR programming" الصفحات التي تحتوي على إحدى الكلمتين وليس بالضرورة كلتيهما.
تعيد عملية البحث عن "java -indonesia" الصفحات التي تحتوي على كلمة "java" ولا تحتوي على كلمة "indonesia".

يُطلَق على تلك التعبيرات، أي تلك التي تحتوي على كلمات بحث وعمليات، اسم "استعلامات queries".

عندما تُطبَّق تلك العمليات على نتائج البحث، فإن الكلمات "AND" و "OR" و "-" تقابل في الرياضياتِ عمليات "التقاطع" و "الاتحاد" و "الفرق" على الترتيب. لنفترض مثلًا أن:

s1 يمثل مجموعة الصفحات التي تحتوي على كلمة "java"،
s2 يمثل مجموعة الصفحات التي تحتوي على كلمة "programming"،
s3 يمثل مجموعة الصفحات التي تحتوي على كلمة "indonesia"،

في تلك الحالة:

يُمثِل التقاطع بين s1 و s2 مجموعة الصفحات التي تحتوي على الكلمتين "java" و "programming" معًا.
يُمثِل الاتحاد بين s1 و s2 مجموعة الصفحات التي تحتوي على كلمة "java" أو كلمة "programming".
يُمثِل الفرق بين s1 و s3 مجموعة الصفحات التي تحتوي على كلمة "java" ولا تحتوي على كلمة "indonesia".

ستكتب في القسم التالي تابعًا يُنفِّذ تلك العمليات.

تمرين 13

ستجد ملفات شيفرة هذا التمرين في مستودع الكتاب:

WikiSearch.java: يُعرِّف كائنًا يحتوي على نتائج البحث ويُطبِّق العمليات عليها.
WikiSearchTest.java: يحتوي على شيفرة اختبار للصنفWikiSearch.
Card.java: يُوضِّح طريقة استخدام التابع sort المُعرَّف بالنوع java.util.Collections.

ستجد أيضًا بعض الأصناف المساعدة التي استخدَمناها من قبل في هذه السلسلة.

انظر بداية تعريف الصنف WikiSearch:

public class WikiSearch {

    // يربط مُحدّدات الموارد التي تحتوي على الكلمة بدرجة الارتباط
    private Map<String, Integer> map;

    public WikiSearch(Map<String, Integer> map) {
        this.map = map;
    }

    public Integer getRelevance(String url) {
        Integer relevance = map.get(url);
        return relevance==null ? 0: relevance;
    }
}

يحتوي كائن النوع WikiSearch على خريطة map تربط مُحدّدات الموارد الموحدة URLs بدرجة الارتباط relevance score، والتي تُمثِل -ضمن سياق استرجاع البيانات- عددًا يشير إلى المدى الذي يستوفي به مُحدِّد الموارد الاستعلام الذي يدخله المُستخدِم. تتوفّر الكثير من الطرائق لحساب درجة الارتباط، ولكنها تعتمد في الغالب على "تردد الكلمة" أي عدد مرات ظهورها في الصفحة. يُعدّ TF-IDF واحدًا من أكثر درجات الارتباط شيوعًا، وتُمثِل الأحرف اختصارًا لعبارة تردد المصطلح term frequency - معكوس تردد المستند inverse document frequency.

إذا احتوى الاستعلام على كلمة بحث واحدة، فإن درجة الارتباط لصفحة معينة تساوي تردّد الكلمة، أي عدد مرات ظهورها في تلك الصفحة.
بالنسبة للاستعلامات التي تحتوي على عدة كلمات، تكون درجة الارتباط لصفحة معينة هي حاصل مجموع تردد الكلمات، أي عدد مرات ظهور أي كلمة منها.

والآن وقد أصبحت مستعدًا لبدء التمرين، نفِّذ الأمر ant build لتصريف ملفات الشيفرة، ثم نفِّذ الأمر ant WikiSearchTest. ستفشل الاختبارات كالعادة لأن ما يزال عليك إكمال بعض العمل.

أكمل متن كلٍّ من التوابع and و or و minus في الملف WikiSearch.java لكي تتمكّن من اجتياز الاختبارات المرتبطة بتلك التوابع. لا تقلق بشأن التابع testSort، فسنعود إليه لاحقًا.

يُمكِنك أن تُنفِّذ WikiSearchTest بدون اِستخدَام Jedis لأنه لا يعتمد على فهرس قاعدة بيانات Redis الخاصة بك، ولكن، إذا أردت أن تَستخِدم الفهرس للاستعلام query، فلا بُدّ أن توفِّر بيانات الخادم في ملف، كما أوضحنا في مقالة "استخدام قاعدة بيانات Redis لتحقيق استمرارية البيانات".

نفِّذ الأمر ant JedisMaker لكي تتأكّد من قدرته على الاتصال بخادم Redis، ثم نفِّذ WikiSearch الذي يَطبَع نتائج الاستعلامات الثلاثة التالية:

"java"
"programming"
"java AND programming"

لن تكون النتائج مُرتَّبة في البداية لأن التابع WikiSearch.sort ما يزال غير مكتمل.

أكمل متن التابع sort لكي تُصبِح النتائج مُرتَّبة تصاعديًا بحسب درجة الارتباط. يُمكِنك الاستعانة بالتابع sort المُعرَّف بالنوع java.util.Collections حيث يُمكِنه ترتيب أي نوع قائمة List. يُمِكنك الاطلاع على توثيق النوع List.

تتوفَّر نسختان من التابع sort:

نسخة أحادية المعامل تَستقبِل قائمةً وتُرتِّب عناصرها باستخدام التابع compareTo، ولذلك ينبغي أن تكون العناصر من النوع Comparable.
نسخة ثنائية المعامل تَستقبِل قائمةً من أي نوع وكائنًا من النوع Comparator، ويُستخدَم التابع compare المُعرَّف ضمن الكائن لموازنة العناصر.

سنتحدث عن الواجهتين Comparable و Comparator في القسم التالي إن لم تكن على معرفة بهما.

الواجهتان `Comparable` و `Comparator`

يتضمَّن مستودع الكتاب الصنف Card الذي يحتوي على طريقتين لترتيب قائمة كائنات من النوع Card. انظر إلى بداية تعريف الصنف:

public class Card implements Comparable<Card> {

    private final int rank;
    private final int suit;

    public Card(int rank, int suit) {
        this.rank = rank;
        this.suit = suit;
    }

تحتوي كائنات الصنف Card على الحقلين rank و suit من النوع العددي الصحيح. يُنفِّذ الصنف Card الواجهة Comparable<Card>‎ مما يَعنِي أنه بالضرورة يُوفِّر تنفيذًا للتابع compareTo:

    public int compareTo(Card that) {
        if (this.suit < that.suit) {
            return -1;
        }
        if (this.suit > that.suit) {
            return 1;
        }
        if (this.rank < that.rank) {
            return -1;
        }
        if (this.rank > that.rank) {
            return 1;
        }
        return 0;
    }

تشير بصمة التابع compareTo إلى أن عليه أن يعيد عددًا سالبًا إذا كان this أقل من that، وعددًا موجبًا إذا كان أكبر منه، وصفرًا إذا كانا متساويين.

إذا استخدمت نسخة التابع Collections.sort أحادية المعامل، فإنها بدورها تَستدعِي التابع compareTo المُعرَّف ضمن العناصر لكي تتمكّن من ترتيبها. على سبيل المثال، تُنشِئ الشيفرة التالية قائمة تحتوي على 52 بطاقة:

    public static List<Card> makeDeck() {
        List<Card> cards = new ArrayList<Card>();
        for (int suit = 0; suit <= 3; suit++) {
            for (int rank = 1; rank <= 13; rank++) {
                Card card = new Card(rank, suit);
                cards.add(card);
            }
        }
        return cards;
    }

ثم تُرتِّبها كالتالي:

        Collections.sort(cards);

تُرتِّب تلك النسخة من التابع sort العناصر وفقًا لما يُطلَق عليه "الترتيب الطبيعي" لأن الترتيب مُحدّد بواسطة العناصر نفسها.

في المقابل، يُمكِننا أيضًا أن نستعين بكائن من النوع Comparator لكي نَفرِض نوعًا مختلفًا من الترتيب. على سبيل المثال، تحتل بطاقات الأص المَرتَبَة الأقلَّ بحسب الترتيب الطبيعي للصنف Card، ومع ذلك، فإنها أحيانًا تحتل المرتبة الأكبر في بعض ألعاب البطاقات، ولذلك، سنُعرِّف كائنًا من النوع Comparator يُعامِل الأصّ على أنّها البطاقة الأكبر ضمن مجموعة بطاقات اللعب. انظر إلى شيفرة ذلك النوع:

        Comparator<Card> comparator = new Comparator<Card>() {
            @Override
            public int compare(Card card1, Card card2) {
                if (card1.getSuit() < card2.getSuit()) {
                    return -1;
                }
                if (card1.getSuit() > card2.getSuit()) {
                    return 1;
                }
                int rank1 = getRankAceHigh(card1);
                int rank2 = getRankAceHigh(card2);

                if (rank1 < rank2) {
                    return -1;
                }
                if (rank1 > rank2) {
                    return 1;
                }
                return 0;
            }

            private int getRankAceHigh(Card card) {
                int rank = card.getRank();
                if (rank == 1) {
                    return 14;
                } else {
                    return rank;
                }
            }
        };

تُعرِّف تلك الشيفرة صنفًا مجهول الاسم anonymous يُنفِّذ التابع compare على النحو المطلوب، ثم تُنشِئ نسخةً منه. يُمكِنك القراءة عن الأصناف مجهولة الاسم Anonymous Classes في لغة جافا إذا لم تكن على معرفة بها.

يُمكِننا الآن أن نُمرِّر ذلك الكائن المنتمي للنوع Comparator إلى التابع sort، كما هو مبين في الشيفرة التالية:

        Collections.sort(cards, comparator);

يُعد الأص البستوني وفقًا لهذا الترتيب البطاقة الأكبر ضمن مجموعة بطاقات اللعب، بينما يُعدّ الثنائي السباتي البطاقة الأصغر.

ستجد شيفرة هذا القسم في الملف Card.java إن كنت تريد تجريبه. قد ترغب أيضًا في كتابة كائن آخر من النوع Comparator يُرتِّب العناصر بناءً على قيمة rank أولًا ثم قيمة suit، وبالتالي، تصبح جميع بطاقات الأصّ معًا وجميع البطاقات الثنائية معًا، وهكذا.

ملحقات

إذا تمكَّنت من كتابة الكائن الذي أشرنا إليه في الأعلى، هاك بعض الأفكار الأخرى التي يُمكِنك أن تحاول القيام بها:

اقرأ عن درجة الارتباط TF-IDF ونفِّذها. قد تحتاج إلى تعديل الصنف JavaIndex لكي تجعله يَحسِب قيمة ترددات المستند أي عدد مرات ظهور كل كلمة في جميع الصفحات الموجودة بالفهرس.
بالنسبة للاستعلامات المكوَّنة من أكثر من كلمةٍ واحدة، يُمكِنك أن تَحسِب درجة الارتباط الإجمالية لكل صفحة بحساب مجموع درجة الارتباط لجميع الكلمات. فكر متى يُمكِن لهذه النسخة المبسطة أن تَفشَل وجرِّب بدائل أخرى.
أنشِئ واجهة مُستخدِم تَسمَح للمُستخدِمين بإدخال استعلامات تحتوي على عوامل operators منطقية. حلِّل الاستعلامات المُدْخَلة، وولِّد النتائج، ثم رتِّبها بحسب درجة الارتباط، واعرض مُحدِّدات الموارد التي أحرزت أعلى درجات. حاول أيضًا أن تُولِّد مقطع شيفرة يَعرِض مكان ظهور كلمات البحث في الصفحة. إذا أردت أن تُنشِئ تطبيق ويب لواجهة المُستخدِم التي أنشأتها، فإن منصة Heroku تُعدّ خيارًا بسيطًا لتطوير تطبيقات الويب ونشرها باستخدام جافا.

ترجمة -بتصرّف- للفصل Chapter 16: Boolean search من كتاب Think Data Structures: Algorithms and Information Retrieval in Java.