هياكل البيانات 101 فهرسة الصفحات وتحليل زمن تشغيلها باستخدام قاعدة بيانات Redis

سنُقدِّم في هذه المقالة حل تمرين مقالة استخدام قاعدة بيانات Redis لحفظ البيانات. بعد ذلك، سنُحلِّل أداء خوارزمية فهرسة صفحات الإنترنت، ثم سنبني زاحفَ ويب Web crawler بسيطًا.

المفهرس المبني على قاعدة بيانات Redis

سنُخزِّن هيكلي البيانات التاليين في قاعدة بيانات Redis:

• سيُقابِل كلَّ كلمة بحثٍ كائنٌ من النوع URLSet هو عبارةٌ عن مجموعة Set في قاعدة بيانات Redis تحتوي على مُحدِّدات الموارد الموحدة URLs التي تحتوي على تلك الكلمة.
• سيُقابِل كل مُحدّد موارد موحد كائنًا من النوع TermCounter يُمثّل جدول Hash في قاعدة بيانات Redis يربُط كل كلمة بحث بعدد مرات ظهورها.

يُمكِنك مراجعة أنواع البيانات التي ناقشناها في المقالة المشار إليها، كما يُمكِنك قراءة المزيد عن المجموعات والجداول بقاعدة بيانات Redis من توثيقها الرسمي.

يُعرِّف الصنف JedisIndex تابعًا يَستقبِل كلمة بحثٍ ويعيد مفتاح كائن الصنف URLSet المقابل في قاعدة بيانات Redis:

private String urlSetKey(String term) {
    return "URLSet:" + term;
}

كما يُعرِّف الصنفُ المذكور التابع termCounterKey، والذي يستقبل مُحدّد موارد موحدًا ويعيد مفتاح كائن الصنف TermCounter المقابل في قاعدة بيانات Redis:

private String termCounterKey(String url) {
    return "TermCounter:" + url;
}

يَستقبِل تابع الفهرسة indexPage محددَ موارد موحدًا وكائنًا من النوع Elements يحتوي على شجرة DOM للفقرات التي نريد فهرستها:

public void indexPage(String url, Elements paragraphs) {
    System.out.println("Indexing " + url);

    // أنشئ كائنًا من النوع‫ TermCounter وأحصِ كلمات الفقرات النصية

    TermCounter tc = new TermCounter(url);
    tc.processElements(paragraphs);

    // أضف محتويات الكائن إلى قاعدة بيانات‫ Redis
    pushTermCounterToRedis(tc);
}

سنقوم بالتالي لكي نُفهرِّس الصفحة:

1. نُنشِئ كائنًا من النوع TermCounter يُمثِل محتويات الصفحة باستخدام شيفرة تمرين المقال المشار إليه بالأعلى.
2. نُضيف محتويات ذلك الكائن في قاعدة بيانات Redis.

تُوضِّح الشيفرة التالية طريقة إضافة كائنات النوع TermCounter إلى قاعدة بيانات Redis:

public List<Object> pushTermCounterToRedis(TermCounter tc) {
    Transaction t = jedis.multi();

    String url = tc.getLabel();
    String hashname = termCounterKey(url);

    // إذا كانت الصفحة مفهرسة مسبقًا، احذف الجدول القديم
    t.del(hashname);


    // أضف مدخلًا جديدًا في كائن الصنف‫ TermCounter وعنصرًا جديدًا إلى الفهرس
    // لكل كلمة بحث
    for (String term: tc.keySet()) {
        Integer count = tc.get(term);
        t.hset(hashname, term, count.toString());
        t.sadd(urlSetKey(term), url);
    }
    List<Object> res = t.exec();
    return res;
}

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

يمرّ التابع عبر العناصر الموجودة في كائن الصنف TermCounter، ويُنفِّذ التالي من أجل كل عنصرٍ منها:

1. يبحث عن كائنٍ من النوع TermCounter -أو ينشئه إن لم يجده- في قاعدة بيانات Redis، ثم يضيف حقلًا فيه يُمثِل العنصر الجديد.
2. يبحث عن كائنٍ من النوع URLSet -أو ينشئه إن لم يجده- في قاعدة بيانات Redis، ثم يضيف إليه محدّد الموارد الموحد الحالي.

إذا كنا قد فهرَسنا تلك الصفحة من قبل، علينا أن نحذف كائن الصنف TermCounter القديم الذي يمثلها قبل أن نضيف المحتويات الجديدة.

هذا هو كل ما نحتاج إليه لفهرسة الصفحات الجديدة.

طلبَ الجزءُ الثاني من التمرين كتابةَ التابع getCounts الذي يَستقبِل كلمة بحثٍ ويعيد خريطةً تربط محددات الموارد الموحدة التي ظهرت فيها تلك الكلمة بعدد مرات ظهورها فيها. انظر إلى تنفيذ التابع:

    public Map<String, Integer> getCounts(String term) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        Set<String> urls = getURLs(term);
        for (String url: urls) {
            Integer count = getCount(url, term);
            map.put(url, count);
        }
        return map;
    }

يَستخدِم هذا التابعُ تابعين مساعدين:

• getURLs: يَستقبِل كلمة بحثٍ ويعيد مجموعةً من النوع Set تحتوي على محددات الموارد الموحدة التي ظهرت فيها الكلمة.
• getCount: يَستقبِل محدد موارد موحدًا URI وكلمة بحث، ويعيد عدد مرات ظهور الكلمة بمحدد الموارد المُمرَّر.

انظر تنفيذات تلك التوابع:

    public Set<String> getURLs(String term) {
        Set<String> set = jedis.smembers(urlSetKey(term));
        return set;
    }

    public Integer getCount(String url, String term) {
        String redisKey = termCounterKey(url);
        String count = jedis.hget(redisKey, term);
        return new Integer(count);
    }

تَعمَل تلك التوابع بكفاءةٍ نتيجةً للطريقة التي صمّمّنا بها المُفهرِس.

تحليل أداء عملية البحث

لنفترض أننا فهرسنا عددًا مقداره N من الصفحات، وتوصلنا إلى عددٍ مقداره M من كلمات البحث. كم الوقت الذي سيستغرقه البحث عن كلمةٍ معينةٍ؟ فكر قبل أن تكمل القراءة.

سنُنفِّذ التابع getCounts للبحث عن كلمةٍ، يُنفِّذ ذلك التابع ما يلي:

1. يُنشِئ خريطةً من النوع HashMap.
2. يُنفِّذ التابع getURLs ليسترجع مجموعة مُحدِّدات الموارد الموحدة.
3. يَستدعِي التابع getCount لكل مُحدِّد موارد، ويضيف مُدْخَلًا إلى الخريطة.

يستغرق التابع getURLs زمنًا يتناسب مع عدد محددات الموارد الموحدة التي تحتوي على كلمة البحث. قد يكون عددًا صغيرًا بالنسبة للكلمات النادرة، ولكنه قد يكون كبيرًا -قد يَصِل إلى N- في حالة الكلمات الشائعة.

سنُنفِّذ داخل الحلقة التابعَ getCount الذي يبحث عن كائنٍ من النوع TermCounter في قاعدة بيانات Redis، ثم يبحث عن كلمةٍ، ويضيف مُدخْلًا إلى خريطةٍ من النوع HashMap. تستغرق جميع تلك العمليات زمنًا ثابتًا، وبالتالي، ينتمي التابع getCounts في المجمل إلى المجموعة O(N)‎ في أسوأ الحالات، ولكن عمليًا، يتناسب زمن تنفيذه مع عدد الصفحات التي تحتوي على تلك الكلمة، وهو عادةً عددٌ أصغر بكثيرٍ من N.

وأما فيما يتعلق بتحليل الخوارزميات، فإن تلك الخوارزمية تتميز بأقصى قدرٍ من الكفاءة، ولكنها مع ذلك بطيئةٌ لأنها ترسل الكثير من العمليات الصغيرة إلى قاعدة بيانات Redis. من الممكن تحسين أدائها باستخدام معاملةٍ من النوع Transaction. يُمكِنك محاولة تنفيذ ذلك أو الاطلاع على الحل في الملف RedisIndex.java (انتبه إلى أن اسمه في المستودع JedisIndex.java والله أعلم).

تحليل أداء عملية الفهرسة

ما الزمن الذي تستغرقه فهرسة صفحةٍ عند استخدام هياكل البيانات التي صمّمْناها؟ فكر قبل أن تكمل القراءة.

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

نزيد العدّاد ضمن خريطة النوع HashMap لكل كلمة بحثٍ ضمن الصفحة، وهو ما يَستغرِق زمنًا ثابتًا، ما يَجعَل الصنف TermCounter يَستغرِق زمنًا يتناسب مع عدد الكلمات الموجودة في الصفحة.

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

1. نضيف عنصرًا إلى كائنٍ من النوع URLSet.
2. نضيف عنصرًا إلى كائنٍ من النوع TermCounter.

تَستغرِق العمليتان السابقتان زمنًا ثابتًا، وبالتالي، يكون الزمن الكليُّ المطلوبُ لإضافة كائنٍ من النوع TermCounter خطيًا مع عدد كلمات البحث الفريدة.

نستخلص مما سبق أنّ زمن تنفيذ الصنف TermCounter يتناسب مع عدد الكلمات الموجودة في الصفحة، وأن إضافة كائنٍ ينتمي إلى النوع TermCounter إلى قاعدة بيانات Redis تتطلَّب زمنًا يتناسب مع عدد الكلمات الفريدة.

ولمّا كان عدد الكلمات الموجودة في الصفحة يتجاوز عادةً عدد كلمات البحث الفريدة، فإن التعقيد يتناسب طردًا مع عدد الكلمات الموجودة في الصفحة، ومع ذلك، قد تحتوي صفحةٌ ما نظرًيًا على جميع كلمات البحث الموجودة في الفهرس، وعليه، ينتمي الأداء في أسوأ الحالات إلى المجموعة O(M)‎، ولكننا لا نتوقَّع حدوث تلك الحالة عمليًّا.

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

تتجنَّب غالبية محركات البحث فهرسةَ الكلماتِ الشائعةِ التي يطلق عليها اسم الكلمات المهملة stop words ضمن هذا السياق.

اجتياز بيان graph

إذا أكملت تمرين مقالة "تنفيذ أسلوب البحث بالعمق أولًا باستخدام الواجهتين Iterables و Iterators"، فلديك بالفعل برنامجٌ يقرأ صفحةً من موقع ويكيبيديا، ويبحث عن أول رابطٍ فيها، ويَستخدِمه لتحميل الصفحة التالية، ثم يكرر العملية. يُعدّ هذا البرنامج بمنزلةِ زاحفٍ من نوع خاص، فعادةً عندما يُذكرُ مصطلح "زاحف إنترنت" Web crawler، فالمقصود برنامج يُنفِّذ ما يلي:

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

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

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

تُحدِّد التجميعة التي سنَستخدِمها لتخزين محددات الموارد المحددة نوع الاجتياز الذي يُنفِّذه الزاحف:

• إذا كانت التجميعة رتلًا queue، أي تتبع أسلوب "الداخل أولًا، يخرج أولًا" FIFO، فإن الزاحف يُنفِّذ اجتياز السّعة أولًا breadth-first.
• إذا كانت التجميعة مكدسًا stack، أي تتبع أسلوب "الداخل آخرًا، يخرج أولًا" LIFO، فإن الزاحف يُنفِّذ اجتياز العمق أولًا depth-first.
• من الممكن تحديد أولويّاتٍ لعناصر التجميعة. على سبيل المثال، قد نرغب في إعطاء أولوية أعلى للصفحات التي لم تُفهرَس منذ فترة طويلة.

تمرين 12

والآن، عليك كتابة الزاحف، ستجد ملفات الشيفرة التالية الخاصة بالتمرين في مستودع الكتاب:

• WikiCrawler.java: يحتوي على شيفرة مبدئيّة للزاحف.
• WikiCrawlerTest.java: يحتوي على اختبارات وحدة للصنف WikiCrawler.
• JedisIndex.java: يحتوي على حلِّ تمرينِ مقالة استخدام قاعدة بيانات Redis لحفظ البيانات.

ستحتاج أيضًا إلى الأصناف المساعدة التالية التي استخدَمناها في تمارين المقالات السابقة:

• JedisMaker.java
• WikiFetcher.java
• TermCounter.java
• WikiNodeIterable.java

سيتعيّن عليك توفير ملفٍّ يحتوي على بيانات خادم Redis قبل تنفيذ الصنف JedisMaker. إذا أكملت تمرين المقالة مقالة استخدام قاعدة بيانات Redis لحفظ البيانات، فقد جهّزت كل شيء بالفعل، أما إذا لم تكمله، فستجد التعليمات الضرورية لإتمام ذلك في نفس المقالة.

نفِّذ الأمر ant build لتصريف ملفات الشيفرة، ثم نفِّذ الأمر ant JedisMaker لكي تتأكّد من أنه مهياٌ للاتصال مع خادم Redis الخاص بك.

والآن، نفِّذ الأمر ant WikiCrawlerTest. ستجد أن الاختبارات قد فشلت؛ لأن ما يزال عليك إتمام بعض العمل أولًا.

انظر إلى بداية تعريف الصنف WikiCrawler:

public class WikiCrawler {

    public final String source;
    private JedisIndex index;
    private Queue<String> queue = new LinkedList<String>();
    final static WikiFetcher wf = new WikiFetcher();

    public WikiCrawler(String source, JedisIndex index) {
        this.source = source;
        this.index = index;
        queue.offer(source);
    }

    public int queueSize() {
        return queue.size();
    }

يحتوي هذا الصنف على متغيرات النسخ instance variables التالية:

• source: مُحدّد الموارد الموحد الذي ستبدأ منه.
• index: مفهرِس -من النوع JedisIndex- ينبغي أن تُخزَّن النتائج فيه.
• queue: عبارة عن قائمة من النوع LinkedList. يُفترَض أن تُخزَّن فيها كلُّ محددات الموارد التي عثرت عليها، ولكن لم تُفهرِسها بعد.
• wf: عبارة عن كائن من النوع WikiFetcher. عليك أن تَستخدِمه لقراءة صفحات الإنترنت وتحليلها.

عليك الآن أن تكمل التابع crawl. انظر إلى بصمته:

    public String crawl(boolean testing) throws IOException {}

ينبغي أن تكون قيمة المعامل testing مساويةً للقيمة true إذا كان مستدعيه هو الصنف WikiCrawlerTest، وأن تكون مساويةً للقيمة false في الحالات الأخرى.

عندما تكون قيمة المعامل testing مساويةً للقيمة true، يُفترَض أن يُنفِّذ التابع crawl ما يلي:

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

في المقابل، عندما تكون قيمة المعامل testing مساويةً للقيمة false، يُفترَض له أن يُنفِّذ ما يلي:

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

يُحمِّل الصنف WikiCrawlerTest رتلًا يحتوي على 200 رابط، ثم يَستدعِي التابع crawl ثلاث مرّات، ويفحص في كلِّ استدعاء القيمةَ المعادة والطولَ الجديد للرتل.

إذا أكملت زاحف الإنترنت الخاص بك بشكل صحيح، فينبغي أن تنجح الاختبارات.

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

اقرأ أيضًا

• المقال التالي: البحث الثنائي Boolean search ودمج نتائج البحث وترتيبها
• المقال السابق: استخدام قاعدة بيانات Redis لحفظ البيانات
• تحليل زمن تشغيل الخرائط المنفذة باستخدام مصفوفة في جافا
• شرح الفروقات بين قواعد بيانات SQL ونظيراتها NoSQL
• كيفية استيراد وتصدير قواعد بيانات MySQL أو MariaDB