هياكل البيانات 101 استخدام خريطة ومجموعة لبناء مفهرس Indexer

انتهينا من بناء زاحف الانترنت crawler في مقالة "تنفيذ أسلوب البحث بالعمق أولًا باستخدام الواجهتين Iterables و Iterators"، وسننتقل الآن إلى الجزء التالي من تطبيق محرك البحث، وهو الفهرس. يُعدّ الفهرس -في سياق البحث عبر الإنترنت- هيكل بياناتٍ data structure يُسهِّل من العثور على الصفحات التي تحتوي على كلمة معينة، كما يساعدنا على معرفة عدد مرات ظهور الكلمة في كل صفحة، مما يُمكِّننا من تحديد الصفحات الأكثر صلة.

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

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

والآن وقد فهمنا ما يعنيه الفهرس والعمليات التي يُنفذّها، يُمكِننا أن نُصمم هيكل بياناتٍ يُمثِّله.

اختيار هيكل البيانات

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

والطريقة البديلة عن تجميعة الصفحات collection هي الخريطة map، والتي هي عبارة عن هيكل بيانات يتكون من مجموعة من أزواج، حيث يتألف كل منها من مفتاح وقيمة key-value.

تُوفِّر الخريطة طريقةً سريعةً للبحث عن مفتاح معين والعثور على قيمته المقابلة. سنُنشِئ مثلًا الخريطة TermCounter، بحيث تربُط كل كلمة بحث بعدد مرات ظهور تلك الكلمة في كل صفحة، وستُمثِل المفاتيح كلمات البحث، بينما ستُمثِل القيم عدد مرات الظهور (أو تكرار الظهور).

تُوفِّر جافا الواجهة Map التي تُخصِّص التوابع methods المُفترَض توافرها في أيّ خريطة، ومن أهمها ما يلي:

• get(key)‎: يبحث هذا التابع عن مفتاح معين ويعيد قيمته المقابلة.
• put(key, value)‎: يضيف هذا التابع زوجًا جديدًا من أزواج مفتاح/قيمة إلى خريطة من النوع Map، أو يستبدل القيمة المرتبطة بالمفتاح في حالة وجوده بالفعل.

تُوفِّر جافا عدة تنفيذاتٍ للواجهة Map، ومن بينها التنفيذان HashMap وTreeMap اللذان سنناقشهما في مقالات قادمة ونُحلّل أداء كُلٍّ منهما.

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

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

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

• add(element)‎: يضيف هذا التابع عنصرًا إلى مجموعة. وإذا كان العنصر موجودًا فعليًا ضمن المجموعة، فإنه لا يفعل شيئًا.
• contains(element)‎: يَفحَص هذا التابع ما إذا كان العنصر المُمرَّر موجودًا في المجموعة.

تُوفِّر جافا عدة تنفيذات للواجهة Set، ومن بينها الصنفان HashSet وTreeSet.

الآن وقد صممنا هياكل البيانات من أعلى لأسفل، فإننا سنُنفِّذها من الداخل إلى الخارج بدءًا من الصنف TermCounter.

الصنف TermCounter

يُمثِل الصنف TermCounter ربطًا بين كلمات البحث مع عدد مرات حدوثها في الصفحات، وتَعرِض الشيفرة التالية الجزء الأول من تعريف الصنف:

public class TermCounter {

    private Map<String, Integer> map;
    private String label;

    public TermCounter(String label) {
        this.label = label;
        this.map = new HashMap<String, Integer>();
    }
}

يربط متغير النسخة map الكلمات بعدد مرات حدوثها، بينما يُحدّد المتغير label المستند الذي يحتوي على تلك الكلمات، وسنَستخدِمه لتخزين محددات الموارد الموحدة URLs.

يُعدّ الصنف HashMap أكثر تنفيذات الواجهة Map شيوعًا، وسنَستخدِمه لتنفيذ عملية الربط، كما سنتناول طريقة عمله ونفهم سبب شيوع استخدامه في المقالات القادمة.

يُوفِّر الصنف TermCounter التابعين put وget المُعرَّفين على النحو التالي:

    public void put(String term, int count) {
        map.put(term, count);
    }

    public Integer get(String term) {
        Integer count = map.get(term);
        return count == null ? 0 : count;
    }

يَعمَل التابع put بمثابة تابع مُغلِّف، فعندما تستدعيه، سيَستدعِي بدوره التابع put المُعرَّف في الخريطة المُخزَّنة داخله.

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

يُساعدنا تعريف التابع get بتلك الطريقة على تعريف التابع incrementTermCount بسهولة، ويَستقبِل ذلك التابع كلمةً ويزيد العدّاد الخاصَّ بها بمقدار 1.

    public void incrementTermCount(String term) {
        put(term, get(term) + 1);
    }

إذا لم تكن الكلمة موجودةً ضمن الخريطة، فسيعيد get القيمة 0، ونزيد العداد بمقدار 1، ثم نَستخدِم التابع put لإضافة زوج مفتاح/قيمة key-value جديد إلى الخريطة. في المقابل، إذا كانت الكلمة موجودةً في الخريطة فعلًا، فإننا نسترجع قيمة العداد القديم، ونزيدها بمقدار 1، ثم نُخزِّنها بحيث تَستبدِل القيمة القديمة.

يُعرِّف الصنف TermCounter توابع أخرى للمساعدة على فهرسة صفحات الإنترنت:

    public void processElements(Elements paragraphs) {
        for (Node node: paragraphs) {
            processTree(node);
        }
    }

    public void processTree(Node root) {
        for (Node node: new WikiNodeIterable(root)) {
            if (node instanceof TextNode) {
                processText(((TextNode) node).text());
            }
        }
    }

    public void processText(String text) {
        String[] array = text.replaceAll("\\pP", " ").
                              toLowerCase().
                              split("\\s+");

        for (int i=0; i<array.length; i++) {
            String term = array[i];
            incrementTermCount(term);
        }
    }

• processElements: يَستقبِل هذا التابع كائنًا من النوع Elements الذي هو تجميعة من كائنات Element. يمرّ التابع عبر التجميعة ويَستدعِي لكل كائنٍ منها التابع processTree.
• processTree: يَستقبِل عقدةً تُمثِّل عقدة جذر شجرة DOM، ويَمرّ التابع عبر الشجرة، ليعثر على العقد التي تحتوي على نص، ثم يَستخرِج منها النص ويُمرِّره إلى التابع processText.
• processText: يَستقبِل سلسلةً نصيةً من النوع String تحتوي على كلمات وفراغات وعلامات ترقيم وغيرها. يَحذِف التابع علامات الترقيم باستبدالها بفراغات، ويُحوِّل الأحرف المتبقية إلى حالتها الصغرى، ثم يُقسِّم النص إلى كلمات. يَمرّ التابع عبر تلك الكلمات، ويَستدِعي التابع incrementTermCount لكُلٍّ منها، ويَستقبِل التابعان replaceAll وsplit تعبيرات نمطية regular expression مثل معاملات.

وأخيرًا، انظر إلى المثال التالي الذي يُوضِّح طريقة استخدام الصنف TermCounter:

    String url = "http://en.wikipedia.org/wiki/Java_(programming_language)";
    WikiFetcher wf = new WikiFetcher();
    Elements paragraphs = wf.fetchWikipedia(url);

    TermCounter counter = new TermCounter(url);
    counter.processElements(paragraphs);
    counter.printCounts();

يَستخدِم هذا المثال كائنًا من النوع WikiFetcher لتحميل صفحةٍ من موقع ويكيبيديا، ثم يُحلّل النص الرئيسيَّ الموجودَ بها، ويُنشِئ كائنًا من النوع TermCounter ويَستخدِمه لعدّ الكلمات الموجودة في الصفحة.

يُمكِنك تشغيل الشيفرة في القسم التالي، واختبار فهمك لها بإكمال متن التابع غير المكتمل.

تمرين 6

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

• TermCounter.java: يحتوي على شيفرة القسم السابق.
• TermCounterTest.java: يحتوي على شيفرة اختبار الملف TermCounter.java.
• Index.java: يحتوي على تعريف الصنف الخاص بالجزء التالي من التمرين.
• WikiFetcher.java: يحتوي على الصنف الذي استخدمناه في التمرين السابق لتحميل صفحة إنترنت وتحليلها.
• WikiNodeIterable.java: يحتوي على الصنف الذي استخدمناه لاجتياز عقد شجرة DOM.

ستَجِد أيضًا ملف البناء build.xml.

نفِّذ الأمر ant build لتصريف ملفات الشيفرة، ثم نفِّذ الأمر ant TermCounter لكي تُشغِّل شيفرة القسم السابق. تَطبَع تلك الشيفرة قائمة بالكلمات وعدد مرات ظهورها، وينبغي أن تحصُل على خرجٍ مشابهٍ لما يلي:

genericservlet, 2
configurations, 1
claimed, 1
servletresponse, 2
occur, 2
Total of all counts = -1

قد تجد ترتيب ظهور الكلمات مختلفًا عندما تُشغِّل الشيفرة، وينبغي أن يَطبَع السطر الأخير المجموعَ الكلّيَّ لعدد مرات ظهور جميع الكلمات، ولكنه يعيد القيمة -1 في هذا المثال لأن التابع size غير مكتمل. أكمل متن هذا التابع، ثم نفِّذ الأمر ant TermCounter مرةً أخرى، حيث ينبغي أن تحصل على القيمة 4798.

نفِّذ الأمر ant TermCounterTest لكي تتأكَّد من أنك قد أكملت جزء التمرين ذاك بشكلٍ صحيح.

بالنسبة للجزء الثاني من التمرين، فسنُوفِّر تنفيذًا لكائنٍ من النوع Index، وسيكون عليك إكمال متن التابع غيرِ المكتمل. انظر إلى تعريف الصنف:

public class Index {

    private Map<String, Set<TermCounter>> index = 
        new HashMap<String, Set<TermCounter>>();

    public void add(String term, TermCounter tc) {
        Set<TermCounter> set = get(term);

        // أنشئ مجموعةً جديدةً إذا كنت ترى الكلمة للمرة الأولى
        if (set == null) {
            set = new HashSet<TermCounter>();
            index.put(term, set);
        }
        // إذا كنت قد رأيت الكلمة من قبل، عدِّل المجموعة الموجودة
        set.add(tc);
    }

    public Set<TermCounter> get(String term) {
        return index.get(term);
    }

يُمثِل متغير النسخة index خريطةً map تربط كل كلمة بحثٍ بمجموعةِ كائناتٍ تنتمي إلى النوع TermCounter، ويُمثِّل كل كائنٍ منها صفحةً ظهرت فيها تلك الكلمة.

يضيف التابع add كائنًا جديدًا من النوع TermCounter إلى المجموعة الخاصة بكلمةٍ معينة. وعندما نُفهرس كلمةً لأول مرة، سيكون علينا أن نُنشِئ لها مجموعةً جديدة، أما إذا كنا قد قابلنا الكلمة من قبل، فسنضيف فقط عنصرًا جديدًا إلى مجموعة تلك الكلمة، أي يُعدِّل التابع set.add عندما تكون المجموعة موجودةً بالفعل داخل index ولا يُعدِّل index ذاته، حيث إننا سنضطر إلى تعديل index فقط عند إضافة كلمةٍ جديدة.

وأخيرًا، يستقبل التابع get كلمة بحثٍ، ويعيد مجموعة كائنات الصنف TermCounter المقابلة للكلمة.

يُعَدّ هيكل البيانات هذا مُعقدًا بعض الشيء. ولاختصاره، يمكن القول أن كائن النوع Index يحتوي على خريطةٍ من النوع Map تربط كل كلمة بحثٍ بمجموعةٍ من النوع Set، المكوَّنةٍ من كائناتٍ تنتمي إلى النوع TermCounter، حيث يُمثِل كلّ كائنٍ منها خريطةً تربط كلماتِ البحث بعدد مرات ظهور تلك الكلمات.

تَعرِض الصورة السابقة رسمًا توضيحيًّا لتلك الكائنات، حيث يحتوي كائن الصنف Index على متغير نسخة اسمه index يشير إلى كائن الصنف Map، الذي يحتوي -في هذا المثال- على سلسلةٍ نصيّةٍ واحدةٍ Java مرتبطةٍ بمجموعةٍ من النوع Set تحتوي على كائنين من النوع TermCounter؛ بحيث يكون واحدًا لكل صفحة قد ظهرت فيها كلمة Java.

يتضمَّن كلّ كائنٍ من النوع TermCounter على متغيرَ النسخة label الذي يُمثِل مُحدّد الموارد الموحد URL الخاص بالصفحة، كما يتضمَّن المتغيرَ map الذي يحتوي على الكلمات الموجودة في الصفحة، وعدد مرات حدوث كلّ كلمةٍ منها.

يُوضِّح التابع printIndex طريقة قراءة هيكل البيانات ذاك:

    public void printIndex() {
        // مرّ عبر كلمات البحث
        for (String term: keySet()) {
            System.out.println(term);

            // لكل كلمة، اطبع الصفحات التي ظهرت فيها الكلمة وعدد مرات ظهورها
            Set<TermCounter> tcs = get(term);
            for (TermCounter tc: tcs) {
                Integer count = tc.get(term);
                System.out.println("    " + tc.getLabel() + " " + count);
            }
        }
    }

تمرّ حلقة التكرار الخارجية عبر كلمات البحث، بينما تمرّ حلقة التكرار الداخلية عبر كائنات الصنف TermCounter.

نفِّذ الأمر ant build لكي تتأكَّد من تصريف ملفات الشيفرة، ثم نفِّذ الأمر ant Index. سيُحمِّل صفحتين من موقع ويكيبيديا ويُفهرسهما، ثم يَطبَع النتائج، ولكنك لن ترى أي خرجٍ عند تشغيله لأننا تركنا أحد التوابع فارغًا.

دورك الآن هو إكمال التابع indexPage الذي يَستقبِل مُحدّد موارد موحّدًا URL (عبارة عن سلسلةٍ نصيةٍ)، وكائنًا من النوع Elements، ويُحدِّث الفهرس. تُوضِّح التعليقات ما ينبغي أن تفعله:

public void indexPage(String url, Elements paragraphs) {
    // أنشئ كائنًا من النوع‫ TermCounter وعدّ الكلمات بكل فقرة

    // لكل كلمة في كائن النوع‫ TermCounter، أضفه إلى index
}

نفِّذ الأمر ant Index . وبعد الانتهاء، إذا كان كل شيء سليمًا، فستحصل على الخرج التالي:

...
configurations
    http://en.wikipedia.org/wiki/Programming_language 1
    http://en.wikipedia.org/wiki/Java_(programming_language) 1
claimed
    http://en.wikipedia.org/wiki/Java_(programming_language) 1
servletresponse
    http://en.wikipedia.org/wiki/Java_(programming_language) 2
occur
    http://en.wikipedia.org/wiki/Java_(programming_language) 2

ضع في الحسبان أنه عند إجرائك للبحث قد يختلف ترتيب ظهور كلمات البحث.

وأخيرًا، نفِّذ الأمر ant TestIndex لكي تتأكَّد من اكتمال هذا الجزء من التمرين على النحو المطلوب.

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

اقرأ أيضًا

• المقال التالي: تحليل زمن تشغيل الخرائط المنفذة باستخدام مصفوفة في جافا
• المقال السابق: تنفيذ أسلوب البحث بالعمق أولا باستخدام الواجهتين Iterables وIterators
• تحليل زمن تشغيل القوائم المنفذة باستخدام قائمة ازدواجية الترابط
• كيف تتعلم البرمجة
• ما هي البرمجة ومتطلبات تعلمها؟