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

الزاحف 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/". قد يتضمَّن ذلك بعض الصفحات التي لا نرغب في فهرستها مثل بعض الصفحات الوصفية لموقع ويكيبيديا، كما قد يستثني ذلك بعض الصفحات التي نريدها مثل روابط الصفحات المكتوبة بلغات أخرى غير الإنجليزية، ومع ذلك، تُعدّ تلك الطريقة جيدة بالقدر الكافي كبداية.

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

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

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

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

يُطلَق على تلك العمليات وما يشابهها اسم استرجاع المعلومات 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.

اقرأ أيضًا

• المقال التالي: نظرة سريعة على بعض خوارزميات الترتيب
• المقال السابق: فهرسة الصفحات وتحليل زمن تشغيلها باستخدام قاعدة بيانات Redis
• استخدام أشجار البحث الثنائية والأشجار المتزنة balanced trees لتنفيذ الخرائط
• تحليل زمن تشغيل الخرائط المنفذة باستخدام شجرة بحث ثنائية TreeMap في جافا

تكون دالةُ ‎h()‎ دالةَ تقطيع Hash Functions إذا كانت تأخذ عنصرًا ‎x ∈ X‎ من أيّ حجم، وتعيد قيمة ‎y ∈ Y‎ من حجمٍ ثابت ‎y‎ = h (x)‎‎.

تتميز دوّال التقطيع النموذجية بالخصائص التالية:

• تتصرف مثل توزِيعات منتظمة uniform distribution
• دوال التقطيع حتمية deterministic، حيث ينبغي أن تعيد الدالة ‎h(x)‎ القيمة نفسها دائمًا لعنصر ‎x‎ محدد.
• ينبغي أن تكون سريعة الحساب (ذات تعقيد زمني O (1)‎‎).

حجم قيمة التقطيع عمومًا أصغر من حجم البيانات المُدخلة: ‎|y| < |x|‎، علاوة على أنّ دوال التقطيع غير قابلة للعكس، لأنه يجوز أن تكون لقيمتين مختلفتين قيمة التقطيع نفسها، أو بتعبير رياضي:

∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2)

قد تكون المجموعة X منتهية أو غير منتهية، أما ‎Y‎ فهي دائمًا مجموعة منتهية. وتُستخدم دوال التقطيع في الكثير من مجالات الحوسبة مثل هندسة البرمجيات والتشفير وقواعد البيانات والشبكات وتعلُُّم الآلة ونحو ذك، وهناك العديد من أنواع دوال التقطيع، ولكل منها خصائص مميزة.

تكون قيمة التقطيع عددًا صحيحًا في الغالب، ومعظم لغات البرمجة لديها توابع ودوال خاصة لحساب قيم التقطيع، مثل الدالة GetHashCode()‎ في لغة C#‎‎ التي تعيد قيمة من النوع ‎Int32‎ (عدد صحيح من 32 بتة) لكل الأنواع. وكذلك في لغة جافا هناك تابع ‎hashCode()‎ يحسب قيمة التقطيع -من النوع int- لكل صنف من أصناف جافا.

طرق تعريف دوال التقطيع Hash methods

هناك عدة طرق لتعريف دوال التقطيع، يمكننا أن نفترض دون الإخلال بالعمومية، أنّ المجموعة X تساوي مجموعة الأعداد الصحيحة الموجبة، وx عنصر منها: أي ‎x ∈ X = {z ∈ ℤ: z ≥‎ 0}‎‎. وليكن m عددًا، ويُفضّل أن يكون أوليًا (شرط أن لا تكون قيمته قريبة جدًا من أي قوّة للعدد 2).

فيما يلي طريقتان لحساب قيم التقطيع الخاصة بعناصر X:

جداول التقطيع

تُستخدم دوال التقطيع مع جداول التقطيع hash tables لحساب الفهارس في مصفوفة من الحجرات array of slots، وجدول التقطيع هي هيكلية بيانات لتنفيذ القواميس dictionaries وهي بيانات من نوع مفتاح-قيمة.

التعقيد الزمني لتطبيقات لجداول التقطيع يساوي في العادة O (1)‎‎ للعمليات التالية:

• إدراج البيانات بحسب قيمة المفتاح.
• حذف البيانات بحسب قيمة المفتاح.

يمكن أن يكون لعدة مفاتيح نفس التقطيع (الحجرة)، وعندئذ فهناك طريقتان لحل هذه المشكلة:

• السلسلة Chaining: تُستخدم القوائم المترابطة لتخزين العناصر التي لها نفس قيمة التقطيع في الحجرة.
• العنونة المفتوحة Open addressing: يُخزّن عنصر واحد على الأكثر في كل حجرة.

تُستخدم الطرق التالية لحساب تسلسلات المسبار probe sequences المطلوبة في العنونة المفتوحة:

الدوال h"(x)‎‎ و h1(x)‎‎ و h2(x)‎‎ هي دوال مساعدة، وi ينتمي إلى المجموعة {0, 1, ..., m-1}، وc1 و c2 ثابتتان موجبتان.

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

لنأخذ المثال التالي، ليكن ‎x ∈ U{1, 1000}‎‎ و h = x mod m‎. يوضح الجدول التالي قيم التقطيع في حالة كان العدد m أوليا أو غير أولي، تشير النصوص الغليظة إلى قيم التقطيع المتساوية.

قيم التقطيع للأنواع الشائعة في C#‎‎

سنستعرض في هذه الفقرة قيم التقطيع hash codes التي ينتجها التابع ‎GetHashCode()‎ لأنواع C#‎‎المضمّنة في فضاء الاسم ‎System‎. يمكنك الاطلاع على توثيقات هذه الأنواع من github.

القيم المنطقية Boolean

1 إذا كانت القيمة صحيحة true، أو 0 خلاف ذلك.

الأنواع Byte و UInt16 و Int32 و UInt32 و Single

قيمة العنصر (تُحوّل عند الضرورة إلى النوع Int32).

النوع SByte

((int)m_value ^ (int)m_value << 8);

النوع Char

(int)m_value ^ ((int)m_value << 16);

النوع Int16

((int)((ushort)m_value) ^ (((int)m_value) << 16));

النوعان Int64 و Double

تطبيق المعامل Xor بين أدنى 32 بتّة وأعلى 32 بتة في العدد المؤلف من 64 بتة.

(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));

الأنواع UInt64 و DateTime و TimeSpan

((int)m_value) ^ (int)(m_value >> 32);

النوع Decimal

((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];

Object

النوع Object هو الصنف الجذري الذي تنحدر منه جميع الكائنات.

RuntimeHelpers.GetHashCode(this);

استخدمنا التطبيق الافتراضي فهرس كتلة المزامنة sync block index.

السلاسل النصية String

يعتمد حساب قيمة التقطيع على نوع نظام التشغيل (Win32 أو Win64)، وإمكانية استخدام تقطيع السلاسل النصية العشوائية randomized string hashing، إضافة إلى الإصدار ووضعية المنقّح.

في حالة المنصة Win64:

int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
   hash1 = ((hash1 << 5) + hash1) ^ c;
   c = s[1];
   if (c == 0)
       break;
   hash2 = ((hash2 << 5) + hash2) ^ c;
   s += 2;
}
return hash1 + (hash2 * 1566083941);

ValueType

يتم البحث عن أول حقل غير ساكن non-static field، وتُحسب قيمة التقطيع خاصته، إذا لم يكن للنوع أيّ حقل غير ساكن، تُعاد قيمة التقطيع الخاصة بذلك النوع. لا يمكن الاعتماد على قيمة التقطيع الخاصة بمتغير عضو ساكن static member، لأنه قد تنتجُ حلقة أبدية إذا كان نوع ذلك العضو يساوي النوع الأصلي.

النوع Nullable‎‎

return hasValue ? value.GetHashCode() : 0;

المصفوفات Array

int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++)
{
    ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}

ترجمة -بتصرّف- للفصل 43 من كتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• المقال السابق: أمثلة على أشهر خوارزميات المخططات والأشجار
• مدخل إلى الخوارزميات
• أمثلة عن أنواع الخوارزميات
• تعقيد الخوارزميات Algorithms Complexity

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

البحث بالعرض أولا Breadth-First Search

سنحاول استعمال هذه الخوارزمية في عدة تطبيقات عمليات بحث.

البحث عن أقصر مسار من المصدر إلى العقد الأخرى

خوارزمية البحث بالعرض أولا BFS هي خوارزمية لتسلق مخطط أو البحث فيها. تبدأ الخوارزمية من جذر الشجرة (أو أيّ عقدة من المخطط، ويُشار إليها أحيانًا باسم "مفتاح البحث" - search key)، ثمّ تستكشف العقد المجاورة أولاً قبل الانتقال إلى المستوى التالي من العقد.

اكتُشفت خوارزمية BFS في أواخر الخمسينيات من قبل إدوارد فورست مور Edward Forrest Moore، الذي استخدمها للعثور على أقصر مسار للخروج من متاهة، وقد اكتُشفت أيضًا بشكل مستقل من قبل CY Lee الذي استخدمها في مجال التوجيه السلكي في عام 1961.

تفترض خوارزمية BFS الأمور التالية:

1. لن نجتاز أي عقدة أكثر من مرة.
2. تقع العقدة المصدرية (أي العقدة التي نبدأ منها) في المستوى 0.
3. العقد التي يمكننا الوصول إليها مباشرة من العقدة المصدرية ستكون في المستوى 1، والعقد التي يمكننا الوصول إليها مباشرة من عقد المستوى 1 ستكون في المستوى 2 وهكذا دواليك.
4. يشير مستوى عقدة ما إلى أقصر مسار يصل إلى تلك العقدة انطلاقًا من المصدر.

انظر المثال التالي:

لنفترض أنّ هذا المخطط يمثل طرقا بين عدة مدن حيث تمثل كل عقدة مدينة واحدة، فيما يشير كل ضلع بين عقدتين إلى طريق يربط بينهما، ونحن نريد الانتقال من العقدة 1 إلى العقدة 10. ستكون العقدة 1 هي المصدر، وهذا يجعلها في المستوى 0. نحدد (نلوّن) العقدة 1 لنشير إلى أننا زرناها.
يمكننا الذهاب إلى العقدة 2 أو العقدة 3 أو العقدة 4 من العقدة المصدر، أي العقدة 1، لذلك ستكون هناك 3 عقد من المستوى 1. نحدد هذه العقد لنبيّن أنّها مُزارة، ثمّ نعمل عليها.

نلوّن العقد المُزارة، حيث نلوّن العقد التي نعمل عليها حاليًا باللون الوردي، تذكّر أنّنا لن نزور العقدة نفسها مرتين. يمكننا الذهاب إلى العقد 6 و 7 و 8 عبر كل من العقدة 2 والعقدة 3 والعقدة 4، وسنحددهذه العقد لنبيّن أنّها مُزارة. مستوى هذه العقد سيساوي (1 +1) = 2.

يشير مستوى العقد إلى أقصر مسافة بينها وبين المصدر. على سبيل المثال: بما أن العقدة 8 موجودة في المستوى 2، فهذا يعني أنّ المسافة من المصدر إلى العقدة 8 هي 2.

لم نصل بعدُ إلى العقدة المستهدفة وهي العقدة 10، لذا ننتقل إلى العقد التالية. نستطيع الانطلاق من أيّ من عقد المستوى 2، وهي العقدة 6 والعقدة 7 والعقدة 8.

ها قد وجدنا العقدة 10 عند المستوى 3، هذا يعني أنّ أقصر مسار من المصدر إلى العقدة 10 هو 3، وقد بحثنا في كل مستوى من مستويات المخطط إلى أن وجدنا أقصر مسار، وإذ ذاك سنمسح الأضلاع التي لم نستخدمها:

بعد إزالة تلك الأضلاع التي لم نستخدمها نحصل على شجرة تُسمى شجرة البحث بالعرض أولًا BFS. تُظهر هذه الشجرة أقصر مسار من المصدر إلى جميع العقد الأخرى.

مهمتنا الآن هي الانتقال من العقدة المصدر إلى العقد الموجودة في المستوى 1، ثم من عقد المستوى 1 إلى عقد المستوى 2، وهكذا حتى نصل إلى وجهتنا. يمكننا استخدام الطوابير Queues لتخزين العقد التي سنعالجها. لكل عقدة نعمل عليها فإننا ندفع (نضيف) إلى الطابور جميع العُقد الأخرى التي من الممكن اجتيَازها مباشرة لكنّنا لم نفعل بعد.

هذه محاكاة للمثال:

أولاً، ندفع العقدة المصدر إلى الطابور، فيبدو هكذا:

 front
+-----+
|  1    |
+-----+

مستوى العقدة 1 يساوي 0، أي level[1] = 0، نبدأ الآن البحث بالعرض أولا BFS.

في البداية، ننزع عقدة من الطابور فنحصل على العقدة 1، يمكننا -انطلاقًا من هذه العقدة- أن نذهب إلى العقدة 4 أو 3 أو 2، لهذا فهذه العقد الثلاث من المستوى الأول، أي level[4] = level[3] = level[2] = level[1] + 1 = 1. سنحددالآن هذه العقد لنبيّن أنّها مُزارَة، ثمّ ندفعها إلى الطابور.

                          front
+-----+  +-----+  +-----+
|   2   |   |  3   |   |   4   |
+-----+  +-----+  +-----+

ننزع الآن العقدة 4 من الطابور ونعالجها، نستطيع الذهاب منها إلى العقدة 7، لهذا يكون لدينا: level[7] = level[4] + 1 = 2. والآن نحددالعقدة 7، ثمّ ندفعها إلى الطابور.

                          front
+-----+  +-----+  +-----+
|    7  |   |  2   |   |   3  |
+-----+  +-----+  +-----+

من العقدة 3، يمكننا الذهاب إلى العقدة 7 أو العقدة 8، وبما أن العقدة 7 محددة من قبل (أي مُزارة سابقًا)، فإننا نحدد العقدة 8، ونضع level[8] = level[3] + 1 = 2. والآن ندفع العقدة 8 إلى الطابور.

                         front
+-----+  +-----+  +-----+
|   6   |   |   7   |  |   2  |
+-----+  +-----+  +-----+

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

انظر المثال التوضيحي لهذا:

Procedure BFS(Graph, source):
Q = queue();
level[] = infinity
level[source] := 0
Q.push(source)
while Q is not empty
   u -> Q.pop()
   for all edges from u to v in Adjacency list
       if level[v] == infinity
           level[v] := level[u] + 1
           Q.push(v)
       end if
   end for
end while
Return level

يمكننا معرفة المسافة التي تفصل كل عقدة عن المصدر من خلال التكرار عبر مصفوفة المستويات، على سبيل المثال: المسافة إلى العقدة 10 من المصدر مخزّنة في level[10]‎‎.

قد نريد أحيانًا أن نعرف المسارات الأخرى التي يمكن أن تُوصلنا إلى العقدة انطلاقًا من المصدر، وذلك إلى جانب المسار الأقصر. لفعل هذا نحتاج إلى مصفوفة جديدة نسميها parent، قيمة parent[source]‎‎ ‏(source هنا تعني العقدة المصدر‏) ستكون معدومة ‎‎NULL‎‎. نضيف التعليمة ‎parent[v] := u‎ إلى المثال الوهمي عند كل تحديث لمصفوفة المستويات level في حلقة for.

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

هذا مثال توضيحي يستخدم العودية recursion:

Procedure PrintPath(u):
if parent[u] is not equal to null    
   PrintPath(parent[u])                  
end if                                
print -> u                           

وهذا مثال لا يستخدمها وإنما يستخدم التكرارية فقط iteration:

Procedure PrintPath(u):
S =  Stack()
while parent[u] is not equal to null
     S.push(u)
     u := parent[u]
end while
while S is not empty
     print -> S.pop
end while

تعقيد الخوارزمية: سوف نزور كل عقدة وكل ضلع مرّة واحدة بالضبط، لذا سيكون تعقيد الخوارزمية الزمني O (V + E)‎‎، حيث يمثل V عدد العقد، ويمثّل E عدد الأضلاع.

البحث عن أقصر مسار ينطلق من المصدر في مخطط ثنائية الأبعاد

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

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

في مثل هذه الحالات، يمكننا تحويل المربعات أو الخلايا إلى عقد، ونحل هذه المشكلة بسهولة باستخدام خوارزمية البحث بالعرض أولًا BFS. ستكون المصفوفات visited و parent و level جميعها مصفوفات ثنائية الأبعاد.

نأخذ جميع التحركات الممكنة لكل عقدة، ونحسب المسافة إلى العقد الأخرى عبر تحليل مسارات التحرك، ثم نضيف مصفوفة أخرى نسميها direction، والتي ستخزّن جميع التركيبات الممكنة للاتجاهات التي يمكننا الذهاب إليها. مثلا، هذه مصفوفة الاتجاهات الخاصة بالتحركات الأفقية والعمودية:

+----+-----+-----+-----+-----+
| dx  |  1   |  -1  |  0   |  0   |
+----+-----+-----+-----+-----+
| dy  |  0   |   0  |  1   |  -1  |
+----+-----+-----+-----+-----+

تمثل dx الحركة على المحور الأفقي x بينما تمثل dy الحركة على المحور العمودي y، ولا شك أن هناك طرق أخرى لتمثيل اتجاهات الحركة لكن يُفضل استخدام مصفوفة الاتجاهات لأنها أسهل وأبسط. كذلك هناك الكثير من التركيبات الممكنة للحركة، إذ يمكن أن تكون التحركات قُطرية أو قد تكون أكثر تعقيدًا مثل تحركات الحصان على رقعة الشطرنج.

وينبغي أن نضع في حسباننا الأمور التالية:

• إذا كانت أيّ من الخلايا محظورة فسيكون علينا أن نتحقق في كل حركة محتملة مما إذا كانت الخلية الحالية محظورة أم لا.
• علينا أن نتحقق أيضًا ممّا إذا كنا قد تجاوزنا الحدودَ، أي حدودَ المصفوفة.
• سنُعطى عدد الصفوف والأعمدة.

انظر المثال التوضيحي التالي:

Procedure BFS2D(Graph, blocksign, row, column):
for i from 1 to row
   for j from 1 to column
       visited[i][j] := false
   end for
end for
visited[source.x][source.y] := true
level[source.x][source.y] := 0
Q = queue()
Q.push(source)
m := dx.size
while Q is not empty
   top := Q.pop
   for i from 1 to m
       temp.x := top.x + dx[i]
       temp.y := top.y + dy[i]
       if temp is inside the row and column and top doesn't equal to blocksign
           visited[temp.x][temp.y] := true
           level[temp.x][temp.y] := level[top.x][top.y] + 1
           Q.push(temp)
       end if
   end for
end while
Return level

ناقشنا سابقًا أن خوارزمية البحث بالعرض أولا BFS لا تصلح إلا للمخططات غير الموزونة unweighted graphs، أما بالنسبة للمخططات الموزونة فسنحتاج إلى خوارزمية ديكسترا. وبالنسبة لدورات الأضلاع السلبية negative edge cycles فسنحتاج إلى خوارزمية بِِلمان - فورد. هناك مسألة أخرى ينبغي الانتباه إليها، وهي أنّ هذه الخوارزمية مخصّصة لإيجاد أقصر مسار من مصدر واحد، فإذا أردت العثور على المسافة من كل عقدة إلى جميع العقد الأخرى ستحتاج إلى استخدام خوارزمية بِلمان - فورد كذلك.

البحث عن المكونات المتصلة لمخطط غير موجهة باستخدام خوارزمية BFS

يمكن استخدام خوارزمية BFS للعثور على المكونات المتصلة connected components في مخطط غير موجه، ويمكن استخدامها أيضًا للتحقق مما إذا كان المخطط متصلًا أم لا، وسنفترض فيما يلي أنّنا نتعامل مع مخططات غير موجهة.

تعريف: يكون المخطط متصلًا connected إذا كان هناك مسار بين كل زوج من الحروف في المخطط. هذا مثال على مخطط متصل:

المخطط التالي غير متصل، ولكن يحتوي على مكوّنتين متصلتين:

1. المكونة المتصل الأولى: {a، b، c، d، e} .
2. المكون المتصلة الثانية: {f}

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

boolean isConnected(Graph g)
{ 
 BFS(v) // هي عقدة مصدرية v 
   if(allVisited(g))
   {
      return true;
   }
   else return false;
}

وهذا تطبيق بلغة C للتحقق مما إذا كان مخططًا متصلًأ غير موجّه أم لا:

#include<stdio.h>
#include<stdlib.h>
#define MAXVERTICES 100   
void enqueue(int);
int deque();
int isConnected(char **graph,int noOfVertices);
void BFS(char **graph,int vertex,int noOfVertices);   
int count = 0;
struct node
{
   int v;
   struct node *next;
};
typedef struct node Node;
typedef struct node *Nodeptr;
Nodeptr Qfront = NULL;
Nodeptr Qrear = NULL;
char *visited;// مصفوفة لتتبع العقد المُزارة
int main()
{
   int n,e;// ‫ يمثل n عدد الحروف، ويمثل e عدد الأضلاع
   int i,j;
   char **graph;//adjacency matrix
   printf("Enter number of vertices:");
   scanf("%d",&n);
   if(n < 0 || n > MAXVERTICES)
   {
    fprintf(stderr, "Please enter a valid positive integer from 1 to %d",MAXVERTICES);
    return -1;
   }
   graph = malloc(n * sizeof(char *));
   visited = malloc(n*sizeof(char));
   for(i = 0;i < n;++i)
   {
       graph[i] = malloc(n*sizeof(int));
       visited[i] = 'N';// في البداية، تكون جميع العقد غير مزارة
       for(j = 0;j < n;++j)
           graph[i][j] = 0;
   }
   printf("enter number of edges and then enter them in pairs:");
   scanf("%d",&e);
   for(i = 0;i < e;++i)
   {
       int u,v;
       scanf("%d%d",&u,&v);
       graph[u-1][v-1] = 1;
       graph[v-1][u-1] = 1;
   }   

   if(isConnected(graph,n))
       printf("The graph is connected");
   else printf("The graph is NOT connected\n");     
}
void enqueue(int vertex)
{
   if(Qfront == NULL)
   {
       Qfront = malloc(sizeof(Node));
       Qfront->v = vertex;
       Qfront->next = NULL;
       Qrear = Qfront;
   }
   else
   {
       Nodeptr newNode = malloc(sizeof(Node));
       newNode->v = vertex;
       newNode->next = NULL;
       Qrear->next = newNode;
       Qrear = newNode;
   }
}
int deque()
{
   if(Qfront == NULL)
   {
       printf("Q is empty , returning -1\n");
       return -1;
   }
   else
   {
       int v = Qfront->v;
       Nodeptr temp= Qfront;
       if(Qfront == Qrear)
       {
           Qfront = Qfront->next;
           Qrear = NULL;
       }
       else
           Qfront = Qfront->next;
       free(temp);
       return v;
   }
}
int isConnected(char **graph,int noOfVertices)
{
   int i;
   // نختار العقدة 0 لتكون عقدة مصدرية
   BFS(graph,0,noOfVertices);
   for(i = 0;i < noOfVertices;++i)
       if(visited[i] == 'N')
        return 0;//0 implies false;
   return 1;//1 implies true;
}
void BFS(char **graph,int v,int noOfVertices)
{       
   int i,vertex;
   visited[v] = 'Y';
   enqueue(v);   
   while((vertex = deque()) != -1)
   {           
       for(i = 0;i < noOfVertices;++i)
           if(graph[vertex][i] == 1 && visited[i] == 'N')
           {
               enqueue(i);
               visited[i] = 'Y';
           }
   }
}

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

هذا هو السطر الأول، المتغير count هو متغير عام مهيء على القيمة 0، وهذا السطر يوضع في بداية دالة BFS:

printf("\nConnected component %d\n",++count); 

وهذا هو السطر الثاني، اجعله في بداية حلقة while في دالة BFS:

printf("%d ",vertex+1); 

نعرّف الآن الدالة التالية:

void listConnectedComponents(char **graph,int noOfVertices)
{
   int i;
   for(i = 0;i < noOfVertices;++i)
   {
       if(visited[i] == 'N')
           BFS(graph,i,noOfVertices);
   }
}

خوارزمية البحث بالعمق أولا Depth First Search

خوارزمية البحث بالعمق أولًا DFS هي خوارزمية لتسلق مخطط أو البحث فيها، وتبدأ من الجذر وتستكشف العقد على طول كل فرع وتتعمق فيه إلى آخر حدّ قبل أن ترتد backtrack، وقد استُخدِمت نسخة أولية من هذه الخوارزمية من قبل عالم الرياضيات الفرنسي تشارلز بيير Tr‎é‎maux في القرن التاسع عشر لإيجاد حلول للمتاهات.

البحث بالعمق أولًا هي طريقة تحاول العثور على جميع العقد التي يمكن الوصول إليها من العقدة المصدر، وتجتاز خوارزمية DFS عقد مُكوّنة متصلة connected component ما من مخطط خوارزمية البحث بالعرض أولًا، ثم تعرّف شجرة ممتدة spanning tree. كذلك تستكشف خوارزمية البحث بالعمق أولا كل الأضلاع بطريقة منهجية. إذ تبدأ من العقدة المصدرية، وبمجرد الوصول إلى عقدة من المخطط تبدأ خوارزمية DFS في الاستكشاف انطلاقًا منها (على عكس خوارزمية BFS، التي تضعها في طابور لأجل استكشافها لاحقًا).

انظر المثال التالي:

نجتاز المخطط باستخدام القواعد التالية:

• نبدأ من المصدر.
• لن نزور أيّ عقدة مرتين.
• نلوّن العقد التي لم نزرها بعد باللون الأبيض.
• نلوّن بالرمادي العقد التي زرناها ولكن لم نزر بعد جميع العقد المتفرّعة منها.
• نلوّن بالأسود العقد التي اجتزناها بالكامل هي والعقد المتفرعة منها.

تبيّن الرسوم التالية هذه الخطوات:

الكلمة المفتاحية التي تهمنا والتي نراها فيما سبق هي الضلع الخلفي backedge، فالضلع 5-1 هو ضلع خلفي backedge، لأننا لم ننته بعد من العقدة 1، فالعودة إلى العقدة المصدرية 1 يعني وجود دورة في المخطط. إذا كنا نستطيع الانتقال من عقدة رمادية إلى أخرى في خوارزمية البحث بالعمق أولا، فذلك دليل على أنّ المخطط يحتوي على دورة، وهذه إحدى طرق رصد الدورات في المخططات.

يمكننا أن نجعل أيّ ضلع في الدورة كضلع خلفي اعتمادًا على العقدة المصدرية، وترتيب زيارة العقد. على سبيل المثال: لو انتقلنا إلى العقد 5 من العقدة 1 أولا، لوجدنا أنّ الضلع 2-1 أصبح ضلعًا خلفيًا.

تسمى الأضلاع التي تنتقل من عقدة رمادية إلى عقدة بيضاء أضلاع الشجرة أو أضلاعًا شجرية tree edge، وإذا أبقينا على أضلاع الشجرة وحذفنا الأضلاع الأخرى، فسوف نحصل على شجرة البحث بالعمق أولا DFS.

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

أيضًا، في خوارزمية البحث بالعمق أولا، نستطيع تخزين علامات زمنية timestamps لكل عقدة، تخزن هذه العلامات الزمنية معلومات عما حدث للعقد أثناء المعالجة، ونخزّنها في مصفوفتين، مصفوفة f لتخزين أوقات الانتهاء، ومصفوفة d لتخزين أوقات استكشاف العقد:

1. عندما يتغيّر لون العقدة v من الأبيض إلى الرمادي نسجّل الوقت في الموضع d[v]‎‎.
2. عند يتغيّر لون عقدة v من الرمادي إلى الأسود، نسجّل الوقت في f [v]‎‎.

سيبدو المثال التوضيحي لتخزين العلامات الزمنية كما يلي:

Procedure DFS(G):
for each node u in V[G]
   color[u] := white
   parent[u] := NULL
end for
time := 0
for each node u in V[G]
   if color[u] == white
       DFS-Visit(u)
   end if
end for
Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
   if color[v] == white
       parent[v] := u
       DFS-Visit(v)
   end if
end for
color[u] := black
time := time + 1
f[u] := time

التعقيد: تُزار كل عقدة وكل ضلع مرة واحدة، لذا فإن تعقيد خوارزمية DFS هو O (V + E)‎‎، حيث يمثّل V عدد العقد في المخطط، ويمثل E عدد الأضلاع.

التطبيقات على خوارزمية البحث بالعمق أولًا كثيرة، منها على سبيل المثال لا الحصر:

• العثور على أقصر مسار بين كل زوج من العقد في مخطط غير موجه.
• رصد الدورات في المخططات.
• العثور على المسارات.
• الترتيب التخطيطي (الطوبولوجي).
• التحقق ممّا إذا كان المخطط ثنائي التجزئة.
• العثور على المكونات شديدة الاتصال Strongly Connected Component.
• حل الألغاز التي لها حل واحد.

خوارزمية البائع المتجول

إن إنشاء مسار يمر عبر كل رأس من رؤوس المخطط مرة واحدة يكافئ ترتيبًا يرتّب حروف ذلك المخطط، ويمكننا استغلال هذه الخاصية لحساب التكلفة الدنيا لعبور كل رأس مرة واحدة بالضبط عبر تجريب كل التبديلات لمجموعة الأعداد من ‎1‎ إلى ‎N‎، وعددها ‎N!‎. انظر الشيفرة العامة لهذا:

minimum = INF
for all permutations P   // كل التبديلات
   current = 0                               
   for i from 0 to N-2
       // أضف تكلفة الانتقال من عقدة إلى إلى أخرى
       current = current + cost[P[i]][P[i+1]]  

   // أضف تكلفة الانتقال من العقدة الأخيرة إلى إلى العقدة الأولى
   current = current + cost[P[N-1]][P[0]]      

   if current < minimum                       // إن كان ذلك ضروريا minimum  حدِّث
       minimum = current

output minimum

التعقيد الزمني: هناك ‎N!‎ تبديلة ينبغي معالجتها، وحساب تكلفة كل مسار تستغرق ‎O(N)‎، من ثم فإنّ هذه الخوارزمية تستغرق مدة O ‎(‎N ‎*‎ N!)‎.

استخدام البرمجة الديناميكية

انظر المسار:

(1,2,3,4,6,0,5,7)

والمسار

(1,2,3,5,0,6,7,4)

تبقى تكلفة الانتقال من العقدة ‎1‎ إلى العقدة ‎2‎ ثمّ إلى العقدة ‎3‎ كما هي، لذا ليس علينا إعادة حسابها، إذ يمكن أن نحفظ هذه النتيجة لاستخدامها لاحقًا.

لنفترض أنّ ‎dp[bitmask][vertex]‎ تمثل الحد الأدنى لتكلفة المسارات التي تعبر جميع الحروف التي قيمة البتّات المقابلة لها فيها ‎bitmask‎ تساوي ‎1‎، والتي تنتهي عند الحرف ‎vertex‎. على سبيل المثال:

dp[12][2]

   12   =   1 1 0 0
               ^ ^
vertices: 3 2 1 0

نظرًا لأنّ ‎1100‎ هي التمثيل الثنائي لـ 12، فإنّ ‎dp[12][2]‎ تمثل الانتقال عبر الحرفين ‎2‎ و ‎3‎ في المخطط عبر مسار ينتهي عند الحرف 2.

هذا تطبيق على الخوارزمية بلغة C++‎:

int cost[N][N];                        // إن كان ذلك ضروريا N تعديل قيمة
int memo[1 << N][N];                   // -1 تهيئة كل العناصر بالقيمة
int TSP(int bitmask, int pos){
   int cost = INF;
   if (bitmask == ((1 << N) - 1)){      // استكشاف كل العقد
       return cost[pos][0];             // تكلفة الرجوع
   }
   if (memo[bitmask][pos] != -1){       // إن كنا قد حسبنا هذه القيمة سابقا
       return memo[bitmask][pos];       // فسنعيد القيمة السابقة، فلا داعي لإعادة حسابها
   }
   for (int i = 0; i < N; ++i){     
       if ((bitmask & (1 << i)) == 0){  //إن لم تُكن العقدة مُزارة بعد
           cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);   // زيارة العقدة
       }
   }
   memo[bitmask][pos] = cost;           // حفظ النتيجة
   return cost;
}
//Call TSP(1,0)

قد يكون هذا السطر مبهمًا، لذا سنفصِّله من أجل التوضيح:

cost = min(cost,TSP(bitmask | (1 << i) , i) + cost[pos][i]);

هنا، تعيّن العبارة ‎bitmask | (1 << i)‎ البتة رقم i في ‎bitmask‎ وتعطيها القيمة 1 دلالة على أنّ الحرف رقم i قد تمت زيارته.

تمثّل i الموضوعة بعد الفاصلة قيمة الموضع pos الجديد في هذا الاستدعاء، والذي يمثل الحرف الأخير الجديد. وتضيف العبارة‎cost[pos][i‎]‎ تكلفة الانتقال من الحرف الموجود في الموضع pos إلى الحرف i.

يُحدّث هذا السطر قيمة ‎cost‎، ويعطيها أدنى قيمة ممكنة للمرور عبر كل الحروف الأخرى التي لم تُزر بعد.

التعقيد الزمني: هناك ‎2^N‎ قيمة ممكنة لـ ‎bitmask‎ و ‎N‎ قيمة ممكنة لـ ‎pos‎ في الدالة ‎TSP(bitmask,pos)‎. ويستغرق تنفيذ كل دالة ‎O(N)‎ (الحلقة for). وبالتالي يستغرق هذا التطبيق إجمالا مدة ‎O(N^2 * 2^N)‎ لإيجاد الحل النهائي.

خوارزمية كثيرة الحدود ومقيدة زمنيًا للعثور على أصغر غطاء رأسي

تعريف: ليكن G مخطط، و C مجموعة من حروفها، فنقول أنّ C غطاء رأسي للمخطط G إن كانت تحتوي طرفًا واحدًا على الأقل من كل ضلع من أضلاع المخطط. وفي هذه الفقرة نستعرض خوارزمية كثيرة الحدود للحصول على أصغر غطاء رأسي vertex cover لمخطط متصل غير موجّه.

التعقيد الزمني لهذه الخوارزمية يساوي O (n2)‎‎.

هذا مثال توضيحي لخوارزمية أصغر غطاء رأسي، إذ نُدخل إليها مخططًا متصلًا G لتعيد لنا مجموعة C تمثّل أصغر غطاء رأسي لهذا المخطط.

Set C <- new Set<Vertex>()
Set X <- new Set<Vertex>()
X <- G.getAllVerticiesArrangedDescendinglyByDegree()
for v in X do
   List<Vertex> adjacentVertices1 <- G.getAdjacent(v)
   if !C contains any of adjacentVertices1 then

       C.add(v)
for vertex in C do
   List<vertex> adjacentVertices2 <- G.adjacentVertecies(vertex)
   if C contains any of adjacentVertices2 then

       C.remove(vertex)

return C

يمكنك استخدام ترتيب الدلو لترتيب الحروف بحسب درجاتها، وبما أن القيمة القصوى للدرجات تساوي (n-1)، حيث يمثّل n عدد الحروف، فستستغرق عمليات الترتيب O(n)‎‎.

ترجمة -بتصرّف- للفصول 41 و 42 و 44 و 53 من كتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• المقال السابق: خوارزميات البحث في النصوص
• تطبيقات الخوارزميات الشرهة
• خوارزمية ديكسترا Dijkstra’s Algorithm

هذه المقالة تتمة للمقالة السابقة خوارزميات البحث وآلية عملها، إذ نستعرض فيها بعض خوارزميات البحث، لكننا سنركز هذه المرة على البحث داخل النصوص، وسنستعرض اثنتين من أشهر خوارزميات البحث في النصوص، وهما خوارزمية رابين-كارب وخوارزمية KMP.

خوارزمية KMP

لنفترض أن لدينا نصًّا ونمطًا (سلسلة نصية)، ونريد أن نعرف ما إذا كان النمط موجودًا في النص أم لا. انظر المثال التالي:

+-------+----+----+----+----+----+----+----+----+
| Index  | 0 |  1  |  2  |  3  |  4  |  5  |  6  |  7  |
+-------+----+----+----+----+----+----+----+----+
|  Text  | a  |  b  |  c  |  b  |  c  |  g  |  l    |  x  |
+-------+----+----+----+----+----+----+----+----+

+----------+----+----+----+----+
| Index    | 0   |  1  |  2  |  3  | 
+----------+----+----+----+----+
| Pattern | b   | c   | g   |  l   |
+----------+----+----+----+----+

هذا النمط Pattern موجود فعلًا في النص Text، لذا يجب أن تعيد خوارزمية البحث العدد 3، وهو فهرس الموضع الذي يبدأ منه هذا النمط داخل النص.

الطريقة البدهية هي أن نبدأ من الفهرس 0 في النص والفهرس 0 في النمط، ونوازن Text[0]‎‎ وPattern[0]‎‎. وبما أنهما غير متساويين، سننتقل إلى الفهرس التالي في النص، ونوازن Text[1]‎‎ وPattern[0]‎‎. وبما أنهما متطابقين، فإنّنا نزيد قيمة الفهرس في النمط والنص معًا.

بعد ذلك نوازن Text[2]‎‎ وPattern[1]‎‎ فنجد أنّهما متطابقين، ثم نتابع ونوازن الآن Text[3]‎‎ وPattern[2]‎‎، واللذين نجد أنّهما غير متطابقين، فنبدأ الآن من الموضع حيث بدأ التطابق بين النص والنمط، أي الفهرس 2 في النص، ونوازن بين كل من Text[2]‎‎ وPattern[0]‎‎، وبما أنهما لا يتطابقان، فسنزيد الفهرس النصي، ونوازن بين كل من Text[3]‎‎ وPattern[0]‎‎. واللذان نجد أنهما متطابقان، كما يتطابق كل من:

• Text[4]‎‎.
• Pattern[1]‎‎.
• Text[5]‎‎.
• Pattern[2].
• Text[6]‎‎.
• Pattern[3]‎‎.

لقد استنفدنا حروف النمط، وهذا يعني أنه موجود في النص. نعيد الآن الفهرس الذي بدأ التطابق عنده، وهو 3.

إن لم يكن النمط موجودًا في النص (مثلا إن كان يساوي ‎bcgll‎)، فنتوقّع أن يُرفع اعتراض exception أو يُعاد -1 أو أيّ قيمة أخرى محدّدة مسبقًا.

تستغرق الخوارزمية في أسوأ الحالات ‎O(mn)‎، حيث يمثّل m طول النص، و n طول النمط. السؤال الآن هو: هل هناك خوارزمية أسرع؟ نعم، وهي خوارزمية KMP.

تبحث خوارزمية نوث-موريس-برات Knuth-Morris-Pratt أو KMP اختصارًا، عن ظهور نمط معيّن داخل سلسلة نصّية، وتستغل هذه الخوارزمية حقيقة أنّه عند حدوث عدم التطابق فإنّ الكلمة نفسها تقدّم معلومات كافية لتقدير المكان التالي الذي يمكن أن يبدأ التطابق عنده، وبالتالي تجاوز بعض الحروف التي تحقّقنا منها سابقًا.

صُمِّمت هذه الخوارزمية سنة 1970 على يد دونالد نوث Donuld Knuth وفوهان برات Vaughan Pratt، وبشكل مستقل على يد جيمس مورِس James H. Morris، وقد نَشر هذا الثلاثي بحثًا مشتركًا عنها سنة 1977.

لنوسّع مثالنا السابق كي نفهمه أكثر:

+-------+---+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Index |0  |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+--------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  Text  |a  |b |c |x |a |b |c |d  |a |b | x | a | b | c |d  | a | b | c | d | a | b | c | y |
+--------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

+----------+---+---+---+---+---+---+---+---+
|  Index   | 0  | 1 | 2  | 3  | 4  | 5 | 6 | 7  |
+----------+---+---+---+---+---+---+---+---+
| Pattern | a  | b | c  | d  | a  | b  | c | y  |
+---------+---+---+---+---+---+---+---+---+

في البداية، يتطابق النص والنمط حتى الفهرسَ 2، ثمّ ينهار التطابق عند الفهرس 3، إذ لا تتطابق Text[3]‎‎ وPattern[3]‎‎. ونحن نهدف إلى عدم الرجوع للخلف في النص، إذ لا نريد أن نبدأ المطابقة مرةً أخرى من الموضع الذي بدأنا المطابقة عنده سابقًا في حالة عدم التطابق. ولتحقيق ذلك، نبحث عن لاحقةٍ suffix في الجزء الحالي من النمط قبل انهيار التطابق والتي تكون أيضًا سابقةً في النمط (السلسلة النصية الجزئية abc). على سبيل المثال، بما أنّ جميع الحروف فريدة غير مكرّرة، فلن يكون هناك أيّ سلسلة نصية تكون لاحقة وسابقة في الوقت نفسه في السلسلة النصية الجزئية التي طَابقناها للتو، هذا يعني أنّ الموازنة التالية ستبدأ من الفهرس 0.

سنوازن الآن بين كل من Text[3]‎‎ وPattern[0]‎‎، إلا أنّهما لا يتطابقان. بعد ذلك نجد تطابقًا ابتداءً من الفهرس 4 وحتى الفهرس 9 في النص، ومن الفهرس 0 إلى 5 في النمط. غير أنّ التطابق ينهار بعد ذلك في Text[10]‎‎ وPattern[6]‎‎. نأخذ الآن السلسلة النصية الجزئية المُطابِقة من النمط قبل نقطة الانهيار (أي abcdabc)، ونبحث عن لاحقة فيها تكون أيضًا سابقة للنمط. تستطيع ملاحظة أنّ ab هي لاحقة لهذه السلسلة النصية الجزئية وسابقة لها في الوقت نفسه. وبما أنّ المطابقة السابقة استمرت حتى Text[10]‎‎، فإنّ الحرفين اللذين يسبقان موضع عدم التطابق هما ab.

هنا نستنتج أنّه لما كانت ab أيضًا سابقة للسلسلة النصية الجزئية التي أخذناها، فلن يكون علينا التحقق من ab مرة أخرى، ويمكن أن يبدأ الفحص التالي من Text[10]‎‎ وPattern[2]‎‎، كذلك ليس علينا أن نعود حيث كنا إذ يمكننا أن نبدأ مباشرة من موضع انهيار التطابق.

علينا الآن التحقق من Text[10]‎‎ وPattern[2]‎‎، بما أنّهما غير متطابقتين وليس للجزء المطابَق من النمط أي لاحقة هي نفسها سابقة للنمط، فسيكون علينا أن نتحقق من Text[10]‎‎ وPattern[0]‎‎، ولكنّها لا يتطابقان أيضًا. بعد ذلك نجد تطابقًا ابتداءً من الفهرس 11 وحتى الفهرس 17 في النص، ومن الفهرس 0 إلى 6. لكن ينهار التطابق مجددًا في Text[18]‎‎ وPattern[7]‎‎.

مرّة أخرى علينا التحقق من السلسلة النصية الجزئية قبل انهيار التطابق (أي abcdabc) لنجد أنّ abc هي لاحقة وسابقة في الوقت نفسه، لذا ينبغي أن تكون abc قبل Text[18]‎‎ بما أنّ التطابق السابق استمر حتى الموضع Pattern[7]‎‎، وهذا يعني أننا لسنا بحاجة إلى الموازنة حتى الموضع Text[18]‎‎، إذ ستبدأ الموازنة من Text[18]‎‎ وPattern[3]‎‎. سنجد الآن تطابقًا، ونعيد 15، وهو الفهرس الذي يبدأ عنده التطابق. هذه هي طريقة عمل خوارزمية KMP.

والآن، كيف نتحقّق مما إذا كانت اللاحقة تساوي السابقة، وعند أي نقطة نبدأ التحقق مما إذا كان هناك عدم تطابق للحروف بين النص والنمط؟

لنلق نظرة على المثال التالي:

+-------+----+----+----+----+----+----+----+----+
| Index  | 0 |  1  |  2  |  3  |  4  |  5  |  6  |  7  |
+-------+----+----+----+----+----+----+----+----+
|  Text  | a  |  b  |  c  |  d  |  a  |  b  |  c    |  a  |
+-------+----+----+----+----+----+----+----+----+

سننشئ مصفوفةً تحتوي المعلومات الضرورية وسنسميها المصفوفة S، حجم هذه المصفوفة يساوي طول النمط، ولا يمكن أن يكون الحرف الأول من النمط لاحقة لأيّ سابقة، لذا نضع S[0] = 0.

نأخذ i = 1 و j = 0 في البداية، نوازن في كل خطوة بين ‎Pattern[i‎]‎‎‎ وPattern[j]‎‎ ونزيد قيمة i بواحد، فإذا كان هناك تطابق نضع S[i‎] = j + 1 ونزيد قيمة j، وإن لم يكن فنتحقق من قيمة الموضع السابق لـ j -إن وُجد- ونضع j = S [j-1]‎‎ -إذا كانت j تخالف 0-، ونستمر في هذا إلى أن يحدث عدم تطابق بين S[i‎] [j]‎‎ و S ‎‎، أو تخالف j القيمة 0. في الحالة الأخيرة نضع S[i‎] = 0.

نعود إلى المثال السابق:

              j      i
+-------+----+----+----+----+----+----+----+----+
| Index  | 0 |  1  |  2  |  3  |  4  |  5  |  6  |  7  |
+-------+----+----+----+----+----+----+----+----+
|  Text  | a  |  b  |  c  |  d  |  a  |  b  |  c    |  a  |
+-------+----+----+----+----+----+----+----+----+

لا يتطابق ‎Pattern[i‎]‎ وPattern[j]‎‎، لذا نزيد قيمة i بواحد، وبما أنّ j تساوي 0، فلن نتحقق من القيمة السابقة، وسنضع ‎Pattern[i‎] = 0‎. سنحصل على تطابق عند الموضع i = 4 إذا واصلنا زيادة i، لذلك نضع [i‎] = S[4] = j + 1 = 0 + 1 = 1 ثمّ نزيد قيمتي j و i. ستبدو المصفوفة هكذا:

                     j                           i
+-------+----+----+----+----+----+----+----+----+
| Index  | 0 |  1  |  2  |  3  |  4  |  5  |  6  |  7  |
+-------+----+----+----+----+----+----+----+----+
|  Text  | a  |  b  |  c  |  d  |  a  |  b  |  c    |  a  |
+-------+----+----+----+----+----+----+----+----+
|    S    |  0 |  0   |  0  |  0 |  1  |      |       |      |
+-------+----+----+----+----+----+----+----+----+

بما أن ‎Pattern[5]‎ وPattern[1]‎‎ متطابقتين، فإننا نضع S[i‎] = S [5] = j + 1 = 1 + 1 = 2. إذا تابعنا سنجد عدم تطابق في الموضعين j = 3 و i = 7. وبما أنّ j لا تساوي 0، فإننا نضع j = S [j-1]‎‎ ونوازن الحرفين الموجودين عند الموضعين i و j، ولأنها متماثلان فإننا نضع S[i‎] = j + 1. ستبدو المصفوفة النهائية كما يلي:

+---------+---+---+---+---+---+---+---+---+
|    S      |  0 |  0 |  0 |  0 |  1 |  2 |  3 | 1 |
+---------+---+---+---+---+---+---+---+---+

هذه هي المصفوفة المطلوبة. إن كانت S[i‎]‎‎ تخالف الصفر فذلك يعني أنّ هناك سلسلة نصية طولها S[i‎]‎‎ هي لاحقة وسابقة في الوقت نفسه للسلسلة النصية الجزئية من النمط التي تبدأ من 0 وتنتهي عند i. نبدأ الموازنة التالية من الموضع S[i‎] + 1 في النمط.

هذه شيفرة عامة لخوارزمية توليد المصفوفة:

Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
   if Pattern[i] is equal to Pattern[j]
       S[i] := j + 1
       j := j + 1
       i := i + 1
   else
       if j is not equal to 0
           j := S[j-1]
       else
           S[i] := 0
           i := i + 1
       end if
   end if
end while

التعقيد الزمني لعملية بناء المصفوفة هو ‎O(n)‎، والتعقيد المساحي يساوي أيضًا ‎O(n)‎. للتأكد من أنك قد فهمت الخوارزمية، حاول إنشاء مصفوفة للنمط ‎aabaabaa‎، وتحقق مما إذا كانت النتيجة التي حصلت عليها تتطابق مع هذه النتيجة:

+---------+---+---+---+---+---+---+---+---+---+
|    S      |  0 |  1 |  0 |  1 |  2 | 3 | 4 | 5 | 2 |
+---------+---+---+---+---+---+---+---+---+---+

انظر إلى المثال التالي:

+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|  Index  |  0 |  1 |  2 |  3 | 4 | 5 |  6 |  7 | 8 |  9 |10 |11 | 
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|   Text  |  a |  b |  x |  a |  b |  c |  a |  b |  c |  a |  b |  y | 
+---------+---+---+---+---+---+---+---+---+---+---+---+---+

+---------+---+---+---+---+---+----+
|  Index  |  0 |  1 |  2 |  3 |  4 |  5 | 
+---------+---+---+---+---+---+----+
| Pattern |  a |  b |  c |  a |  b |  y | 
+---------+---+---+---+---+---+----+
|    S      |  0 |  0 |  0 |  1 |  2 |  0 | 
+---------+---+---+---+---+---+----+

لدينا سلسلة نصية ونمط ومصفوفة S محسوبة قبليًا باستخدام الطريقة التي شرحناها سابقًا. سوف نوازن ‎Text[0]‎ وPattern[0]‎‎ وهما متطابقان، كما أنّ ‎Text[1]‎ وPattern[1]‎‎ متطابقان كذلك؛ أمّا ‎Text[2]‎ وPattern[2]‎‎، فهما غير متطابقين.

نتحقق من القيمة الموجودة عند الموضع الذي يسبق موضع عدم التطابق. ولمّا كانت ‎‎S [1] ‎‎ تساوي 0، فذلك يعني أنّه لا توجد لاحقة تطابق سابقة في السلسلة النصية الجزئية الحالية، لذا تبدأ الموازنة عند الموضع S [1]‎‎، وهو 0. وهكذا نجد أنّ ‎Text[2]‎ وPattern[0]‎‎ غير متطابقتين، لذا نستمر لنجد أنّ ‎Text[3]‎ وPattern[0]‎‎ متطابقتان، ويستمر التطابق حتى ‎Text[8]‎ وPattern[5]‎‎.

نعود الآن خطوةً واحدةً إلى الوراء في المصفوفة S لنجد القيمة 2، هذا يعني أنّ هناك سابقة طولها 2 وهي أيضًا لاحقة في السلسلة النصية الجزئية الحالية abcab، وهي ab. هذا يعني أنّ السلسلة النصية ab موجودة قبل ‎Text[8]‎.
وعلى ذلك نستطيع تجاهلPattern[1]‎‎ وPattern[0]‎‎ وبدء الموازنة التالية من الموضعين ‎Text[8]‎ وPattern[2]‎‎.

إذا تابعنا بذلك النسق فسنجد النمط داخل النص، وستبدو الشيفرة لتلك الإجراءات كما يلي:

Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
   if Pattern[j] is equal to Text[i]
       j := j + 1
       i := i + 1
   if j is equal to n
       Return (j-i)
   else if i < m and Pattern[j] is not equal t Text[i]
       if j is not equal to 0
           j = S[j-1]
       else
           i := i + 1
       end if
   end if
end while
Return -1

التعقيد الزمني لهذه الخوارزمية -بصرف النظر عن العمليات الحسابية المتعلقة بحساب مصفوفة اللاحقات- هو ‎O(m)‎، وبما أنّ دالة GenerateSuffixArray تستغرق وقتًا قدره O ‎(n)‎، فإن التعقيد الزمني الإجمالي لخوارزمية KMP هو: O ‎(m+n)‎.

اقتباس

ملاحظة: إذا أردت العثور على كل مواضع ظهور نمط معيّن في النص، يمكنك أن تطبعها أو تحفظها وتعيّن ‎j := S[j-1]‎، وذلك بدلًا من أن إعادة القيمة. كذللك يجب أن تحفظ رايةً ‎flag‎ لتعرف ما إذا كنت قد وجدت أيّ ظهور سابق للنمط أم لا.

خوارزمية رابين كارب Rabin-Karp

خوارزمية رابين-كارب‏ Rabin-Karp هي خوارزمية بحث في السلاسل النصية أُنشِئت على يد ريتشارد كارب Richard M. Karp ومايكل رابِن Michael Rabin، وتستخدم هذه الخوارزمية دالة التعمية hashing للتحقق من وجود مجموعة من الأنماط في نص ما.

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

في خوارزمية Rabin-Karp، سنحسب تجزئة النمط الذي نبحث عنه، ثمّ نتحقق مما إذا كانت هناك تعمية تداولية rolling hash في النص تتوافق مع النمط أم لا، وإذا لم تتطابق فذلك يضمن لنا أنّ النمط غير موجود في النص، أما في حال كان هناك تطابق فربّما يكون النمط موجودًا في النص. دعنا نلقي نظرةً على المثال التالي:

لنفترض أنّ النص يساوي yeminsajid، وأننا نريد أن نعرف إن كان هذا النص يحتوي النمط nsa. لكي نحسب التجزئة والتجزئة التداولية سنحتاج إلى استخدام عدد أولي، ويمكنك هنا اختيار أيّ عدد أولي وليكن العدد Prime = 11.

نحسب قيمة التجزئة باستخدام هذه الصيغة:

(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......

لكل حرف رقم يميزه في قائمة الحروف الهجائية:

a -> 1    g -> 7    m -> 13  s -> 19  y -> 25
b -> 2    h -> 8    n -> 14   t -> 20   z -> 26
c -> 3    i -> 9     o -> 15   u -> 21
d -> 4    j -> 10   p -> 16   v -> 22
e -> 5    k -> 11  q -> 17   w -> 23
f -> 6     l -> 12    r -> 18   x -> 24

قيمة تجزئة nsa هي:

 14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344

الآن نحسب التجزئة التداولية للنص، أي نحسب تجزئة كل سلسلة نصية جزئية مؤلفة من 3 حروف في النص، فإذا تطابقت التجزئة التداولية مع قيمة تجزئة النمط، نتحقق مما إذا كانت السلسلتان النصيّتان متطابقتان أم لا، وبما أنّ النمط يحتوي على 3 أحرف، فإننا نأخذ أوّل ثلاثة أحرف من النص yem ونحسب قيمة تجزئتها، فنحصل على:

25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653

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

مشكلة هذا المنظور هي أنّ حساب التجزئة في كل مرة مكلف جدًا، لكن هناك تقنية يمكن أن تسرّع العملية برمّتها، وخطواتها كالآتي:

1. نطرح قيمة الحرف الأول من السلسلة النصية السابقة (التي حسبنا تجزئتها قبيل قليل) من قيمة التجزئة الحالية، والتي هي فـي هـذه الحالـة y. وسنحصل على ‎1653 - 25 = 1628‎.
2. نقسّم الناتج على العدد الأولي 11 الذي اخترناه سابقًا، وسنحصل على ‎1628 / 11 = 148‎.
3. نضيف ناتج العملية (ترتيب الحرف الجديد) X‏ 11^m-y، حيث يمثّل m طول النمط، أما ترتيب الحرف الجديد فيساوي ترتيب i، وهو 9. نحصل على 112 = 1237‎

قيمة التجزئة الجديدة لا تساوي قيمة التجزئة الخاصة بالنمط، لذا نستمر بالبحث على المنوال نفسه، وبالنسبة للحرف n نحصل على:

Previous String: emi // السلسلة النصية السابقة
First Letter of Previous String: e(5)  // الحرف الأول من السلسلة النصية السابقة
New Letter: n(14)     // الحرف الجديد 
New String: "min"     // السلسلة النصية الجديدة
1237 - 5 = 1232
1232 / 11 = 112
112 + 14 X 11² = 1806

ليس هناك تطابق أيضًا، لذا سنأخذ الآن الحرف s:

Previous String: min  // السلسلة النصية السابقة
First Letter of Previous String: m(13)  // الحرف الأول من السلسلة النصية السابقة
New Letter: s(19)   // الحرف الجديد 
New String: "ins"    // السلسلة النصية الجديدة
1806 - 13 = 1793  
1793 / 11 = 163
163 + 19 X 11² = 2462

ليس هناك تطابق أيضًا. بعد ذلك، نأخذ a فنحصل على:

Previous String: ins   // السلسلة النصية السابقة
First Letter of Previous String: i(9)  // الحرف الأول من السلسلة النصية السابقة
New Letter: a(1)  // الحرف الجديد
New String: "nsa"  // السلسلة النصية الجديدة
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344

هنا حصل تطابق، لذا سنوازن الآن النمط بالسلسلة النصية الحالية، وبما أنّ كلا السلسلتين متطابقتين نستنج أنّ السلسلة النصية الجزئية موجودة في النص، ونعيد موضع بداية السلسلة النصية الجزئية. انظر المثال التوضيحي التالي:

• حساب التجزئة:

Procedure Calculate-Hash(String, Prime, x):
hash := 0               // ‫هنا، تمثل x الطول
for m from 1 to x                      // البحث عن قيمة التجزئة
   hash := hash + (Value of String[m])⁻¹
end for
Return hash

• إعادة حساب التجزئة، ستمثل Curr هنا الحرف الأول من السلسلة النصية السابقة:

Procedure Recalculate-Hash(String, Curr, Prime, Hash):
Hash := Hash - Value of String[Curr] 
Hash := Hash / Prime
m := String.length
New := Curr + m - 1
Hash := Hash + (Value of String[New])⁻¹
Return Hash

• مطابقة السلسلة النصية:

Procedure String-Match(Text, Pattern, m):
for i from m to Pattern-length + m - 1
    if Text[i] is not equal to Pattern[i]
        Return false
    end if
end for
Return true

• منظور رابين كارب:

Procedure Rabin-Karp(Text, Pattern, Prime):
m := Pattern.Length
HashValue := Calculate-Hash(Pattern, Prime, m)
CurrValue := Calculate-Hash(Pattern, Prime, m)
for i from 1 to Text.length - m
   if HashValue == CurrValue and String-Match(Text, Pattern, i) is true
       Return i
   end if
   CurrValue := Recalculate-Hash(String, i+1, Prime, CurrValue)
end for
Return -1

ستعيد الخوارزمية -1 إذا لم تعثر على أي تطابق.

تُستخدم هذه الخوارزمية للكشف عن الانتحال، إذ نعطيها مادةً نصيةً مصدريةً، فتبحث بسرعة في مقالة عما إذا كانت المقالة تحتوي جملًا أو عبارات من المادة المصدرية متجاهلةً تفاصيلًا معينةً من قبيل علامات الترقيم وحالة الحروف (أو تشكيلها). عادةً ما تكون هناك الكثير من السلاسل النصية (الجمل) التي ينبغي أن نبحث عنها، لذا فإنّ خوارزميات البحث التقليدية التي تبحث عن سلسلة نصية واحدة مثل خوارزمية Knuth- Morris-Pratt أو خوارزمية Boyer-Moore String، لن تكون عمليّةً هنا، لهذا يُفضّل استخدام خوارزمية Rabin-Karp. لكن من المهم أن تنتبه إلى أنّ خوارزمية Knuth- Morris-Pratt وخوارزمية Boyer-Moore String أسرع من خوارزمية Rabin-Karp.

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

بالنسبة لنص طوله n، و p نمط مجموع أطوالها يساوي m، فإنّ حالتي التعقيد المتوسطة والفضلى تساويانO (n + m) ‎‎، كما تحتاج الخوازمية إلى مساحة O (p)‎‎؛ أما حالة التعقيد الأسوأ فتُساوي O (nm)‎‎.

هذا تطبيق بلغة بايثون على خوارزمية KMP:

• Haystack: السلسلة النصية التي سنبحث فيها.
• Needle: النمط المراد البحث عنه.
• التعقيد الزمني: التعقيد الزمني للجزء الذي يُجري عمليات البحث (التابع strstr) هو O (n)‎‎، حيث يمثّل ‎n‎ طول الوسيط haystack، ولكن لمّا كان الوسيط needle يُحلَّل قبليا لأجل بناء جدول السوابق prefix table، فسنحتاج مدة O (m)‎‎، وهي المدة المطلوب لبناء الجدول، حيث يمثل ‎m‎ طول needle، وهكذا فإنّ التعقيد الزمني الكلي لخوارزمية KMP يساوي O (n + m)‎‎.
• تعقيد المساحة: تحتاج الخوارزمية إلى مساحة بحجم O (m)‎‎ لأجل بناء جدول السوابق.

اقتباس

ملاحظة: يعيد التقديم التالي موضع بدء التطابق في النص haystack (إذا كان هناك تطابق أصلًا)، أو يعيد العدد -1 في حالة لم يكن needle موجودًا في النص haystack، أو كان أحدهُما فارغًا.

def get_prefix_table(needle):
   prefix_set = set()
   n = len(needle)
   prefix_table = [0]*n
   delimeter = 1
   while(delimeter<n):
       prefix_set.add(needle[:delimeter])
       j = 1
       while(j<delimeter+1):
           if needle[j:delimeter+1] in prefix_set:
               prefix_table[delimeter] = delimeter - j + 1
               break
           j += 1
       delimeter += 1
   return prefix_table
def strstr(haystack, needle):
   # ‫يمثل ‫m الموضع في S حيث يبدأ التطابق القادم لـ W
   # ‫يمثل i فهرس المحرف الحالي W
   haystack_len = len(haystack)
   needle_len = len(needle)
   if (needle_len > haystack_len) or (not haystack_len) or (not needle_len):
       return -1
   prefix_table = get_prefix_table(needle)
   m = i = 0
   while((i<needle_len) and (m<haystack_len)):
       if haystack[m] == needle[i]:
           i += 1
           m += 1
       else:
           if i != 0:
               i = prefix_table[i-1]
           else:
               m += 1
   if i==needle_len and haystack[m-1] == needle[i-1]:
       return m - needle_len
   else:
       return -1
if __name__ == '__main__':
   needle = 'abcaby'
   haystack = 'abxabcabcaby'
   print strstr(haystack, needle)

هذا تطبيق على خوارزمية KMP في لغة C، الوسيط txt يمثل النص، فيما يمثل الوسيط pat النمط، يطبع هذا البرنامج كل ظهور للنمط pat في النص txt. مثلا، إن كان الدخل يساوي:

  txt[] = "THIS IS A TEST TEXT"
  pat[] = "TEST"

فسيطبع البرنامج الخرج التالي:

Pattern found at index 10

بالنسبة للدخل:

  txt[] = "AABAACAADAABAAABAA"
  pat[] = "AABA"

يطبع البرنامج الخرج التالي:

   Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 13

هذا هو المثال التطبيقي على استخدام خورازمية KMP في لغة C:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void computeLPSArray(char *pat, int M, int *lps);
void KMPSearch(char *pat, char *txt)
{
   int M = strlen(pat);
   int N = strlen(txt);

هنا ستنشئ []lps لتخزين أطول قيم سابقة لاحقة للنمط، نتابع …

   int *lps = (int *)malloc(sizeof(int)*M);
   int j  = 0;  // pat[] فهرس لـ

الحساب القبلي للنمط، أي حساب مصفوفة []lps، نتابع …

   computeLPSArray(pat, M, lps);
   int i = 0;  // txt[] فهرس
   while (i < N)
   {
     if (pat[j] == txt[i])
     {
       j++;
       i++;
     }
     if (j == M)
     {
       printf("Found pattern at index %d \n", i-j);
       j = lps[j-1];
     }
     // تطابق j العثور على عدم تطابق بعد
     else if (i < N && pat[j] != txt[i])
     {
       // lps[0..lps[j-1]] لا تحاول التحقق من مطابقة الحروف
       // لأننا نعلم أنها مطابقة
       if (j != 0)
        j = lps[j-1];
       else
        i = i+1;
     }
   }
   free(lps); // لتجنب تسرب الذاكرة
}
void computeLPSArray(char *pat, int M, int *lps)
{
   int len = 0;  //  حجم أطول سابقة-لاحقة حالية
   int i;
   lps[0] = 0; // يساوي 0 دائما lps[0]
   i = 1;
   while (i < M)
   {
      if (pat[i] == pat[len])
      {
        len++;
        lps[i] = len;
        i++;
      }
      else // (pat[i] != pat[len])
      {
        if (len != 0)
        {
          // هنا فخ، انظر المثال التالي
          // AAACAAAA و i = 7.
          len = lps[len-1];
          // هنا i لاحظ أيضا أننا لم نزد قيمة
        }
        else // if (len == 0)
        {
          lps[i] = 0;
          i++;
        }
      }
   }
}

الخرج الناتج هو الآتي:

Found pattern at index 10

ترجمة -بتصرّف- للفصل 40 من الكتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• خوارزميات الترتيب وأشهرها
• أمثلة عن أنواع الخوارزميات
• خوارزميات تحليل المسارات في الأشجار
• خوارزمية ديكسترا Dijkstra’s Algorithm

سوف نستعرض في هذه المقالة خوارِزميتان من خوارزميات البحث الشهيرة، وهما خوارزمية البحث الثنائي، وخوارزمية البحث الخطي، مع تحليلهما وشرح آلية عملهما.

البحث الثنائي Binary Search

خوارزمية البحث الثنائي هي خوارزمية بحث في المصفوفات المرتبة تعتمد منظور فرق تسد، وتحتاج هذه الخوارزمية مدة قدرها ‎O(log n)‎ للعثور على موقع العنصر المبحوث عنه في المصفوفة المرتبة، حيث يمثّل ‎n‎ مساحة المَبحث، أي المصفوفة التي نبحث فيها.

تبدأ خوارزمية البحث الثنائي في كل خطوة بالتحقق من القيمة الموجودة في منتصف المصفوفة mid، فإن كانت تساوي العنصر المبحوث عنه فإنها تتوقف وتعيد فهرسه؛ وإلا تقسّم المصفوفة إلى اثنتين هما مصفوفة [mid,b] ومصفوفة [a,mid]، حيث يمثل a و b طرفي المصفوفة.

وإن كان العنصر المبحوث عنه موجودا في المصفوفة وكان أكبر من mid، فهذا يعني أنّه سيكون لا محالة في الجزء [mid,b] لأنّ المصفوفة مرتبة؛ أما إذا كان العنصر المبحوث عنه أصغر من mid فهذا يعني أنّه سيكون في الجزء [a,mid].

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

إليك مثالًا توضيحيًا؛ لنفترض أنّك خبير اقتصادي وقد تمّ تكليفك بمهمة تحديد سعر التوازن equilibrium price (أي السعر الذي يحقق المعادلة العرض = الطلب) لسلعة الأرز. تذكّر أنه كلما زاد السعر، زاد العرض وقلّ الطلب.

لنفترضّ أنّ الشركة التي تعمل فيها توفر لك جميع المعطيات المتعلقة بالعرض والطلب المتعلقين بالأرز عندما يستقر سعر الأرز عند قيمة معيّنة ‎p‎، فعندئذ تستطيع الحصول على العرض والطلب بوحدات الأرز. ويريد رئيسك أن تحسب سعر التوازن في أسرع وقت ممكن، لكن سينبّهك إلى أنّ سعر التوازن يجب أن يكون عددًا صحيحًا موجبًا لا يتجاوز ‎10^17‎، كما انّه يضمن لك أنّه سيكون هناك حل عددي صحيح موجب واحد بالضبط في هذا النطاق.

يُسمح لك باستدعاء الدالتين ‎getSupply(k)‎ و ‎getDemand(k)‎، وَاللتان تعيدان كمية العرض وحجم الطلب بالنسبة للسعر K على التوالي.

المبحث أو مساحة البحث هنا هي مصفوفة الأعداد الصحيحة من ‎1‎ إلى ‎10^17‎. ويكون البحث الخطي في هذه الحالة غير مناسب لأنّ المصفوفة مرتّبة. لاحظ أنه كلما ارتفعت قيمة ‎k‎، ستزيد قيمة ‎getSupply(k)‎، وتنخفض قيمة ‎getDemand(k)‎، ومن ثم تكون لدينا المتراجحة التالية:

اقتباس

لكل ‎x > y‎ لدينا: getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y)‎‎

أي أن زيادة السعر يصاحبها زيادة في الفرق بين العرض والطلب، وهذا منطقي ومتوقع. أيضًا، بما أنّ مساحة المبحث (المصفوفة) مرتّبة، فيمكننا استخدام خوارزمية البحث الثنائي.

المثال التوضيحي التالي يبين كيفية استخدام خوارزمية البحث الثنائي:

high = 100000000000000000     <- الحد الأقصى لمساحة المبحث
low = 1                       <-  الحد الأدنى لمساحة المبحث
while high - low > 1
   mid = (high + low) / 2    <- خذ القيمة الوسطى
   supply = getSupply(mid) 
   demand = getDemand(mid)
   if supply > demand       
       high = mid             <- الحل موجود في النصف السفلي من مساحة المبحث
   else if demand > supply
       low = mid              <- الحل موجود في النصف العلوي من مساحة المبحث
   else                       <- الشرط: العرض == الطلب
       return mid             <- العثور على الحل

تستغرق هذه الخوارزمية وقتًا مقداره ‎~O(log 10^17)‎. وعمومًا، يساوي تعقيد خوارزمية الترتيب الثنائي ‎~O(log S)‎، حيث يمثّل S حجم مصفوفة البحث، لأنّنا نقلّص مساحة البحث إلى النصف في كل تكرار للحلقة while، (من [low: high] إلى [low: mid] أو [mid: high] ).

فيما يلي تطبيق على خوارزمية البحث الثنائي يستخدم التكرارية، في لغة ?

int binsearch(int a[], int x, int low, int high) {
   int mid;
   if (low > high)
     return -1;
   mid = (low + high) / 2;
   if (x == a[mid]) {
       return (mid);
   } else
   if (x < a[mid]) {
       binsearch(a, x, low, mid - 1);
   } else {
       binsearch(a, x, mid + 1, high);
   }
}

خوارزمية رابِن كارب Rabin Karp

خوارزمية رابِن كارب هي خوارزمية بحث نصية تستخدم دالة تعمية hashing للعثور على نمط معيّن من مجموعة من الأنماط النصية في سلسلة نصية، ومتوسط أوقات تشغيلها وأفضلها يساوي المدة O(n + m)‎‎ في المساحة (O(p، حيث يمثّل n طول السلسلة النصية، فيما يمثّل m طول النمط. بالمقابل، فأسوأ أوقات تشغيلها يساوي O(nm)‎‎.

هذا تطبيق لخوارزمية مطابقة السلاسل النصية في لغة جافا، حيث يمثل q عددًا أوليًا، و p يمثل قيمة التجزئة الخاصة بالنمط، و t قيمة التجزئة الخاصة بالنص، و d يمثل عدد الحروف الأبجدية.

void RabinfindPattern(String text,String pattern){
   int d=128;
   int q=100;
   int n=text.length();
   int m=pattern.length();
   int t=0,p=0;
   int h=1;
   int i,j;
//دالة حساب قيمة التجزئة
   for (i=0;i<m-1;i++)
           h = (h*d)%q;
       for (i=0;i<m;i++){
       p = (d*p + pattern.charAt(i))%q;
       t = (d*t + text.charAt(i))%q;
       }
// البحث عن النمط
   for(i=0;i<end-m;i++){
       if(p==t){
// إن تطابقت قيمة التجزئة، فقارن النمط حرفا حرفا
           for(j=0;j<m;j++)
               if(text.charAt(j+i)!=pattern.charAt(j))
               break;
           if(j==m && i>=start)
               System.out.println("Pattern match found at index "+i);           
       }
       if(i<end-m){
           t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
           if(t<0)
               t=t+q;
       }   
   }                               
}

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

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

t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;

تحليل الحالات التعقيدية لخوارزمية البحث الخطي

كل خوارزمية لها ثلاث حالات تعقيد:

1. أسوأ حالة.
2. الحالة المتوسطة.
3. أفضل حالة.

#include <stdio.h>
// ‫البحث عن x في arr[]‎‎، في حال العثور على x، تعيد الدالة الفهرس
// وإلا أعِد -1
int search(int arr[], int n, int x)
{
   int i;
   for (i=0; i<n; i++)
   {
       if (arr[i] == x)
        return i;
   }
   return -1;
}

برنامج مشغِّل لاختبار الدوال أعلاه:

int main()
{
 int arr[] = {1, 10, 30, 15};
 int x = 30;
 int n = sizeof(arr)/sizeof(arr[0]);
 printf("%d is present at index %d", x, search(arr, n, x));
 getchar();
 return 0;

تحليل أسوأ حالة

عند تحليل الحالة الأسوأ نحسب الحد الأعلى لوقت تشغيل الخوارزمية، ويجب أن نعرف الحالة التي تجعل الخوارزمية تنفّذ أقصى عدد من العمليات. وبالنسبة لخوارزمية البحث الخطي، تحدث أسوأ حالة عندما لا يكون العنصر المبحوث عنه (x) موجودًا في المصفوفة، فحينئذ سوف تقارنه دالة البحث search()‎‎ مع جميع عناصر المصفوفة المبحوث فيها واحدًا تلو الآخر. وعليه، فإنّ أسوأ حالة تعقيدية في خوارزمية البحث الخطي تساوي ‎Θ‎(n)‎‎.

تحليل الحالة التعقيدية المتوسطة

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

لنفترض أنّ جميع الحالات مُوزّعة توزيعًا منتظمًا uniformly distributed -بما في ذلك الحالات التي لا يكون فيها x ضمن المصفوفة-، ثم نجمع جميع تلك الحالات ونقسّم المجموع على (n +1).

هذه صيغة الحالة التعقيدية المتوسطة:

تحليل أفضل حالة

عند تحليل أفضل حالة تعقيدية، نحسب الحد الأدنى لأوقات تشغيل الخوارزمية، ويجب أن نعرف الحالة التي تجعل الخوارزمية تنفّذ أقل عدد من العمليات. تحدث أفضل حالة في مشكلة البحث الخطي عندما يكون x في الموضع الأول، ففي هذه الحالة، سيكون عدد العمليات المُنفّذة ثابتًا (مهما كانت قيمة n)، لذا فإنّ التعقيد الزمني لأفضل حالة يساوي Θ(1)‎‎.

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

في بعض الخوارزميات، تكون جميع الحالات متماثلة تقريبًا، إذ لا توجد حالة أسوأ وحالة فضلى، نجد هذا على سبيل المثال في خوارزمية الترتيب بالدمج، إذ ينفّذ الترتيب بالدمج عدد ‎Θ‎(nLogn)‎ عملية في جميع الحالات.

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

تطبيق خوارزمية البحث الثنائي على أعداد مرتبة

هذا مثال توضيحي لتطبيق خوارزمية البحث الثنائي على الأعداد:

int array[1000] = { sorted list of numbers };
int N = 100;  // عدد المدخلات في مساحة المبحث
int high, low, mid; // قيم مؤقتة
int x; // القيمة المبحوث عنها
low = 0;
high = N -1;
while(low < high)
{
   mid = (low + high)/2;
   if(array[mid] < x)
       low = mid + 1;
   else
       high = mid; 
} 
if(array[low] == x)
   // low العثور على العنصر عند الفهرس
else
   // لم نعثر على العنصر

لا تحاول العودة مبكرًا بموازنة العنصر الأوسط array[mid]‎‎ بـ x، فذلك سيضيف عملية موازنة زائدة تبطئ الخوارزمية. لاحظ أن عليك إضافة 1 إلى قيمة low لتجنب أن يُقرّب ناتج القسمة الصحيحة إلى أسفل rounding down.

يتيح الإصدار أعلاه من البحث الثنائي إمكانية إيجاد أصغر فهرس لظهور x في المصفوفة في حال كانت تحتوي عدة نسخ من x، ويمكن تعديل الخوارزمية لجعلها تعيد أكبر فهرس كما تبيّن الشيفرة التالية:

while(low < high)
   {
       mid = low + ((high - low) / 2);
       if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
           low = mid + 1;
       else
           high = mid; 
   }

لاحظ أنه بدلًا من إجراء العملية التالية:

‎mid = (low + high) / 2‎

فقد يكون الأفضل إجراء العملية الآتية:

‎mid = low + ((high - low) / 2)‎

في التطبيقات التي تستهدف لغات مثل Java لتقليل خطر حصول طفح overflow في حال كانت المدخلات كبيرة الحجم.

البحث الخطي linear search

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

تعقيد هذه الخوارزمية يساوي O(n)‎‎، حيث يمثّل n عدد العناصر. قد تسأل لماذا O(n)‎‎؟ لأنّه في أسوأ حالة، سيكون عليك المرور على جميع عناصر المصفوفة، أي على n عنصر.

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

هذا تطبيق لخوارزمية البحث الخطي بلغة بايثون:

def linear_search(searchable_list, query):
   for x in searchable_list:
       if query == x:
           return True
   return False
linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True

ترجمة -بتصرّف- للفصل 39 من الكتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• أمثلة عن أنواع الخوارزميات
• خوارزمية ديكسترا Dijkstra’s Algorithm
• خوارزميات تحليل المسارات في الأشجار
• الخوارزميات الشرهة Greedy Algorithms

سنتحدث في هذه المقالة عن بعض المفاهيم العامة المتعلقة بخوارزميات الترتيب، ثم نستعرض 10 من أشهر خوارزميات ترتيب المصفوفات.

قبل أن نواصل، سنعطي بعض التعاريف العامة.

• خوارزميات الترتيب المستقرة: تكون خوارزمية ترتيب ما مستقرةً stable إذا كانت تحافظ على الترتيب النسبي للعناصر التي لها نفس قيمة المفتاح الذي يُجرى الترتيب وفقًا له.
• خوارزميات الترتيب الموضعية In place algorithms: نقول أنّ خوارزمية ترتيب ما هي خوارزمية موضعية In place إذا كانت الذاكرة الإضافية التي تستخدمها أثناء الترتيب تساوي ‎O(1)‎ (دون احتساب المصفوفة المراد ترتيبها).
• أسوء حالة تعقيدية Worst case complexity: نقول أنّ أسوء حالة تعقيدية Worst case complexity لخوارزمية تساوي ‎O(T(n))‎ إذا كان وقت تشغيلها لا يزيد عن ‎T(n)‎ مهما كانت المدخلات.
• أفضل حالة تعقيدية Best case complexity: نقول أنّ أفضل حالة تعقيدية Best case complexity لخوارزمية ما تساوي ‎O(T(n))‎ إذا كان وقت تشغيلها لا يقل عن ‎T(n)‎ مهما كانت المدخلات.
• أوسط حالة تعقيدية Average case complexity: نقول أنّ أوسط حالة تعقيدية Average case complexity لخوارزمية ترتيب ما تساوي ‎O(T(n))‎ إذا كان متوسط أوقات تشغيلها بالنسبة لجميع المدخلات الممكنة يساوي ‎T(n)‎.

استقرار الترتيب Stability in Sorting

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

(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)

سنحاول ترتيب المصفوفة حسب العنصر الأول في كل زوج. سيخرج الترتيب المستقر لهذه القائمة ما يلي:

(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)

وهو ترتيبٌ مستقر لأنّ ‎(9, 3)‎ تظهر بعد ‎(9, 7)‎ في المصفوفة الأصلية أيضًا. أما الترتيب غير مستقر فيكون كما يلي:

(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)

قد ينتج عن الترتيب غير المستقر الخرج نفسه الذي يٌنتجه الترتيب المستقر أحيانًا، لكن ليس دائمًا.

هذه بعض أشهر أنواع التراتيب المستقرة:

• الترتيب بالدمج Merge sort.
• الترتيب بالإدراج Insertion sort.
• ترتيب بالجذر Radix sort .
• ترتيب Tim.
• الترتيب بالفقاعات Bubble Sort.

هذه بعض أنواع التراتيب غير المستقرة:

• الترتيب بالكومة Heap sort.
• الترتيب السريع Quick sort.

سوف نستعرض في بقية هذه المقالة 10 خوارزميات ترتيب شهيرة.

الترتيب بالفقاعات Bubble Sort

توازن خوارزمية الفقاعات ‎BubbleSort‎ كل زوج متتالي من العناصر في المصفوفة غير المرتبة، ثمّ تبدل مواضعهما إن كان تَرتيبهما خاطئًا. ويوضّح المثال التالي كيفية عمل خوارزمية الفقاعات على المصفوفة ‎{6,5,3,1,8,7,2,4}‎ (تُحاط الأزواج قيد المقارنة في كل خطوة بالرمز "**"):

{6,5,3,1,8,7,2,4}
{**5,6**,3,1,8,7,2,4} -- 5 < 6 -> تبديل
{5,**3,6**,1,8,7,2,4} -- 3 < 6 -> تبديل
{5,3,**1,6**,8,7,2,4} -- 1 < 6 -> تبديل
{5,3,1,**6,8**,7,2,4} -- 8 > 6 -> لا تبديل
{5,3,1,6,**7,8**,2,4} -- 7 < 8 -> تبديل
{5,3,1,6,7,**2,8**,4} -- 2 < 8 -> تبديل
{5,3,1,6,7,2,**4,8**} -- 4 < 8 -> تبديل

نحصل بعد الدورة الأولى على المصفوفة ‎{5,3,1,6,7,2,4,8}‎، لاحظ أنّ أكبر قيمة غير مرتبة في المصفوفة (8 في هذه الحالة) ستصل دائمًا إلى موضعها النهائي. للتأكد من أنّ المصفوفة مرتّبة ترتيبًا صحيحًا وأنّ كل عناصرها في المواضع الصحيحة، سيكون علينا تكرار هذه العملية n-1 مرّة، حيث يمثّل n طول المصفوفة المراد ترتيبها.

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

الرسم البياني التالي يمثّل آلية عمل خوارزمية الترتيب بالفقاعات:

هذه تطبيقات لخوارزمية الترتيب بالفقاعات بعدة لغات برمجة.

• لغة C++‎:

void bubbleSort(vector<int>numbers)
  {
      for(int i = numbers.size() - 1; i >= 0; i--) {
          for(int j = 1; j <= i; j++) {
              if(numbers[j-1] > numbers[j]) {
                  swap(numbers[j-1],numbers(j));
              }
          }
      }
  }

• لغة C:

void bubble_sort(long list[], long n)
{
 long c, d, t;
 for (c = 0 ; c < ( n - 1 ); c++)
 {
   for (d = 0 ; d < n - c - 1; d++)
   {
     if (list[d] > list[d+1])
     {
       /* تبديل */
       t         = list[d];
       list[d]   = list[d+1];
       list[d+1] = t;
     }
   }
 }
}