هياكل البيانات 101 تنفيذ أسلوب البحث بالعمق أولا باستخدام الواجهتين Iterables وIterators

سنبني في هذه المقالة زاحفَ إنترنت crawler يختبر صحة فرضيّة "الطريق إلى مقالة الفلسفة" في موقع ويكيبيديا التي شرحنا معناها في مقالة تنفيذ أسلوب "البحث بالعمق أولًا" تعاوديًا وتكراريًا.

البداية

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

1. WikiNodeExample.java: يحتوي على شيفرة التنفيذ التعاودي recursive والتكراري iterative لتقنية البحث بالعمق أولًا depth-first search.
2. WikiNodeIterable.java: يحتوي على صنف ممتدٍّ من النوع Iterable بإمكانه المرور عبر شجرة DOM.
3. WikiFetcher.java: يحتوي على صنفٍ يُعرِّف أداةً تَستخدِم مكتبة jsoup لتحميل الصفحات من موقع ويكيبيديا. ويضع الصنف حدًّا لسرعة تحميل الصفحات امتثالًا لشروط الخدمة في موقع ويكيبيديا، فإذا طلبت أكثر من صفحة في الثانية الواحدة، فإنه ينتظر قليلًا قبل أن يُحمِّل الصفحة التالية.
4. WikiPhilosophy.java: يحتوي على تصوّرٍ مبدئيٍّ عن الشيفرة التي ينبغي أن تكملها في هذا التمرين، وسنناقشها في الأسفل.

ستجد أيضًا ملف البناء build.xml، حيث ستَعمَل الشيفرة المبدئية إذا نفَّذت الأمر ant WikiPhilosophy.

الواجهتان Iterables وIterators

تناولنا في مقالة أسلوب "البحث بالعمق أولًا" تنفيذًا تكراريًا له، وذكرنا وجه تفضيله على التنفيذ التعاودي من جهة سهولة تضمينه في كائنٍ من النوع Iterator. سنناقش في هذا المقال طريقة القيام بذلك.

يُمكِنك القراءة عن الواجهتين Iterator وIterable إذا لم تكن على معرفة بهما.

ألقِ نظرةً على محتويات الملف WikiNodeIterable.java. يُنفِّذ الصنف الخارجيُّ WikiNodeIterable الواجهة Iterable<Node>‎، ولذا يُمكِننا أن نَستخدِمه ضمن حلقة تكرار loop على النحو التالي:

    Node root = ...
    Iterable<Node> iter = new WikiNodeIterable(root);
    for (Node node: iter) {
        visit(node);
    }

يشير root إلى جذر الشجرة التي ننوي اجتيازها، بينما يُمثِل visit التابع الذي نرغب في تطبيقه عند مرورنا بعقدةٍ ما.

يَتبِع التنفيذ WikiNodeIterable المعادلة التقليدية:

1. يَستقبِل الباني constructor مرجعًا إلى عقدة الجذر.
2. يُنشِئ التابع iterator كائنًا من النوع Iterator ويعيده.

انظر إلى شيفرة الصنف:

public class WikiNodeIterable implements Iterable<Node> {

    private Node root;

    public WikiNodeIterable(Node root) {
        this.root = root;
    }

    @Override
    public Iterator<Node> iterator() {
        return new WikiNodeIterator(root);
    }
}

في المقابل، يُنجِز الصنف الداخلي WikiNodeIterator العمل الفعلي:

    private class WikiNodeIterator implements Iterator<Node> {

        Deque<Node> stack;

        public WikiNodeIterator(Node node) {
            stack = new ArrayDeque<Node>();
            stack.push(root);
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public Node next() {
            if (stack.isEmpty()) {
                throw new NoSuchElementException();
            }

            Node node = stack.pop();
            List<Node> nodes = new ArrayList<Node>(node.childNodes());
            Collections.reverse(nodes);
            for (Node child: nodes) {
                stack.push(child);
            }
            return node;
        }
    }

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

1. يُهيئ الباني المكدس stack (المُنفَّذ باستخدام كائن من النوع ArrayDeque)، ويُضيف إليه عقدة الجذر.
2. isEmpty: يفحص ما إذا كان المكدس فارغًا.
3. next: يَسحَب العقدة التالية من المكدّس، ويضيف أبناءها بترتيبٍ معاكسٍ إلى المكدّس، ثم يعيد العقدة التي سحبها. وفي حال استدعاء التابع next في كائن Iterator فارغٍ، فإنه يُبلِّغ عن اعتراض exception.

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

الصنف WikiFetcher

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

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

انظر فيما يلي إلى تعريف الصنف WikiFetcher:

public class WikiFetcher {
    private long lastRequestTime = -1;
    private long minInterval = 1000;

    /**
     * حمِّل صفحة محدد موارد موحد وحللها
     * أعد قائمة تحتوي على عناصر تُمثِل الفقرات
     *
     * @param url
     * @return
     * @throws IOException
     */
    public Elements fetchWikipedia(String url) throws IOException {
        sleepIfNeeded();

        Connection conn = Jsoup.connect(url);
        Document doc = conn.get();
        Element content = doc.getElementById("mw-content-text");
        Elements paragraphs = content.select("p");
        return paragraphs;
    }

    private void sleepIfNeeded() {
        if (lastRequestTime != -1) {
            long currentTime = System.currentTimeMillis();
            long nextRequestTime = lastRequestTime + minInterval;
            if (currentTime < nextRequestTime) {
                try {
                    Thread.sleep(nextRequestTime - currentTime);
                } catch (InterruptedException e) {
                    System.err.println(
                        "Warning: sleep interrupted in fetchWikipedia.");
                }
            }
        }
        lastRequestTime = System.currentTimeMillis();
    }
}

يُعدّ fetchWikipedia هو التابع الوحيد المُعرَّف باستخدام المُعدِّل public ضمن ذلك الصنف. يَستقبِل هذا التابع سلسلةً نصيّةً من النوع String وتُمثِل مُحدّد موارد موحّدًا URL، ويعيد تجميعةً من النوع التي Elements تحتوي على عنصر DOM لكل فقرةٍ ضمن المحتوى النصيّ. يُفترَض أن تكون تلك الشيفرة مألوفةً بالنسبة لك.

تقع الشيفرة الجديدة ضمن التابع sleepIfNeeded الذي يفحص الزمنَ المنقضيَ منذ آخر طلبٍ، وينتظر إذا كان الزمن أقلّ من القيمة الدنيا minInterval والمقدّرة بوحدة الميلي ثانية.

هذا هو كل ما يفعله الصنف WikiFetcher. وتُوضِّح الشيفرة التالية طريقة استخدامه:

    WikiFetcher wf = new WikiFetcher();

    for (String url: urlList) {
        Elements paragraphs = wf.fetchWikipedia(url);
        processParagraphs(paragraphs);
    }

افترضنا في هذا المثال أن urlList عبارة عن تجميعة تحتوي على سلاسلَ نصيّة من النوع String وأن التابع processParagraphs يُعالِج بطريقةٍ ما كائن الصنف Elements الذي أعاده التابع fetchWikipedia.

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

اقتباس

ملحوظة: تنفيذنا للصنف WikiFetcher بسيطٌ للغاية، ولكن من السهل إساءة استخدامه بإنشاء عدة نسخٍ منه. يُمكِنك أن تتجنب تلك المشكلة بجعل الصنف WikiFetcher مُتفرِّدًا singleton.

تمرين 5

ستجد في الملف WikiPhilosophy.java تابع main بسيطًا يُوضِّح طريقة استخدام أجزاءٍ من تلك الشيفرة. وبدءًا منه، ستكون وظيفتك هي كتابةُ زاحفٍ يقوم بما يلي:

1. يَستقبِل مُحدّد موارد موحّدًا URL لصفحةٍ من موقع ويكيبيديا، ويُحمِّلها ويُحلِّلها.
2. يجتاز شجرة DOM الناتجة ويعثر على أول رابطٍ صالحٍ. وسنشرح المقصود بكلمة "صالح" في الأسفل.
3. إذا لم تحتوِ الصفحة على أية روابطَ أو كنا قد زرنا أوّل رابطٍ من قبل، فعندئذٍ ينبغي أن ينتهي البرنامج مشيرًا إلى فشله.
4. إذا كان مُحدّد الموارد الموحد يشير إلى مقالة ويكيبيديا عن الفلسفة، فينبغي أن ينتهي البرنامج مشيرًا إلى نجاحه.
5. وفيما عدا ذلك، يعود إلى الخطوة رقم 1.

ينبغي أن يُنشِئ البرنامج قائمةً من النوع List تحتوي على جميع مُحدّدات الموارد التي زارها، ويَعرِض النتائج عند انتهائه، سواءٌ أكانت النتيجة الفشل أم النجاح.

والآن، ما الذي نعنيه برابط "صالح"؟ في الحقيقة لدينا بعض الخيارات، إذ تَستخدِم النسخ المختلفة من نظرية "الوصول إلى مقالة ويكيبيديا عن الفلسفة" قواعدَ مختلفةً نَستعرِض بعضًا منها هنا:

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

ليس من الضروري أن تتقيد بكل تلك القواعد، ولكن يُمكِنك على الأقل معالجة الأقواس والخطوط المائلة والروابط التي تشير إلى الصفحة الحالية.

إذا كنت تظن أن لديك المعلومات الكافية لتبدأ، فابدأ الآن، ولكن لا بأس قبل ذلك بقراءة التلميحات التالية:

1. ستحتاج إلى معالجة نوعين من العقد بينما تجتاز الشجرة، هما الصنفان TextNode وElement. إذا قابلت كائنًا من النوع Element، فلربما قد تضطّر إلى تحويل نوعه typecast لكي تتمكَّن من استرجاع الوسم وغيره من المعلومات.
2. عندما تقابل كائنًا من النوع Element يحتوي على رابط، فعندها يُمكِنك اختبار ما إذا كان مكتوبًا بخطٍ مائلٍ باتباع روابط عقد الأب أعلى الشجرة، فإذا وجدت بينها الوسم <i> أو الوسم <em>، فهذا يَعني أن الرابط مكتوبٌ بخطٍّ مائل.
3. لكي تفحص ما إذا كان الرابط مكتوبًا بين أقواس، ستضطّر إلى فحص النص أثناء اجتياز الشجرة لكي تتعقب أقواس الفتح والغلق (سيكون مثاليًا لو استطاع الحل الخاص بك معالجة الأقواس المتداخلة (مثل تلك)).
4. إذا بدأت من مقالة ويكيبيديا عن جافا، فينبغي أن تصل إلى مقالة الفلسفة بعد اتباع 7 روابط لو لم يحدث تغيير في صفحات ويكيبيديا منذ لحظة بدئنا بتشغيل الشيفرة.

الآن وقد حصلت على كل المساعدة الممكنة، يُمكِنك أن تبدأ في العمل.

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

اقرأ أيضًا

• المقال السابق: تنفيذ أسلوب البحث بالعمق أولا باستخدام طريقتي التعاود والتكرار في جافا
• التعاود recursion والمكدس stack في جافاسكربت
• طريقة عمل الواجهات في لغة جافا