مرحبا يا هبر! تعرف على كيفية تنفيذ الخوارزميات الفعالة بناءً على أهم هياكل البيانات في لغة جافا ، وكيفية قياس أداء هذه الخوارزميات. يرافق كل فصل تمارين للمساعدة في تعزيز المواد.
- تعلم العمل مع هياكل البيانات ، على سبيل المثال ، مع القوائم والقواميس ، وفهم كيفية عملها.
- اكتب تطبيقًا يقرأ صفحات ويكيبيديا ، ويحلل ، ويوفر التنقل عبر شجرة البيانات الناتجة.
- قم بتحليل الكود وتعلم كيفية التنبؤ بمدى سرعة العمل ومقدار الذاكرة التي ستستهلكها.
- اكتب الفئات التي تنفذ واجهة الخريطة ، واستخدم جدول تجزئة وشجرة بحث ثنائية.
- قم بإنشاء محرك بحث ويب بسيط باستخدام محرك البحث الخاص به: سيقوم بفهرسة صفحات الويب وحفظ محتواها وإرجاع النتائج المرجوة.
مقتطفات "ممشى الشجرة"
في هذا الفصل ، سنلقي نظرة على تطبيق محرك بحث سنقوم بتطويره طوال الفترة المتبقية من الكتاب. أنا (المؤلف) أصف عناصر محرك البحث وأقدم التطبيق الأول ، وهو روبوت بحث يقوم بتنزيل وتحليل الصفحات من ويكيبيديا. يقدم هذا الفصل أيضًا تنفيذ بحث متكرر عميقًا وتنفيذًا تكراريًا باستخدام Deque من Java لتنفيذ مكدس "آخر ما يدخل أولاً يخرج".
محركات البحث
يقبل محرك البحث مثل بحث Google أو Bing مجموعة من مصطلحات البحث ويعرض قائمة بصفحات الويب ذات الصلة بهذه المصطلحات.
يمكنك قراءة المزيد على موقع
thinkdast.com ، لكنني سأشرح لك ما تحتاجه أثناء التنقل.
فكر في المكونات الرئيسية لمحرك البحث.
- جمع البيانات (الزحف). ستحتاج إلى برنامج يمكنه تحميل صفحة ويب وتحليلها واستخراج النص وأي روابط لصفحات أخرى.
- الفهرسة نحتاج إلى فهرس يسمح لنا بالعثور على استعلام البحث والصفحات التي تحتوي عليه.
- بحث (استرجاع). أنت بحاجة إلى طريقة لجمع النتائج من الفهرس وتحديد الصفحات الأكثر صلة بعبارات البحث.
لنبدأ بروبوت البحث. الغرض منه هو الكشف عن وتحميل مجموعة من صفحات الويب. بالنسبة لمحركات البحث مثل Google و Bing ، فإن التحدي هو العثور على جميع صفحات الويب ، ولكن غالبًا ما تقتصر هذه الروبوتات على نطاق أصغر. في حالتنا ، سنقرأ فقط صفحات من ويكيبيديا.
كخطوة أولى ، سننشئ روبوت بحث يقرأ صفحة ويكيبيديا ، ويجد الرابط الأول ، ويذهب إلى صفحة أخرى ويكرر الخطوات السابقة. سنستخدم محرك البحث هذا لاختبار فرضية الوصول إلى الفلسفة. تقول:
"بالنقر على الرابط الصغير الأول في النص الرئيسي لمقالة ويكيبيديا ثم تكرار هذا الإجراء للمقالات اللاحقة ، من المرجح أن يتم نقلك إلى صفحة تحتوي على مقالة عن الفلسفة."
يمكنك
عرض هذه الفرضية وتاريخها على
thinkdast.com/getphil .
سيسمح لك اختبار الفرضية بإنشاء الأجزاء الرئيسية من روبوت البحث دون الحاجة إلى تجاوز الإنترنت بالكامل أو حتى ويكيبيديا بأكملها. وأعتقد أن هذا التمرين مثير للاهتمام!
في عدة فصول ، سنعمل على المفهرس ، ثم ننتقل إلى محرك البحث.
تحليل HTML
عند تحميل صفحة ويب ، تتم كتابة محتوياتها بلغة ترميز النص التشعبي (HTML). على سبيل المثال ، ما يلي هو مستند HTML بسيط:
<!DOCTYPE html> <html> <head> <title>This is a title</title> </head> <body> <p>Hello world!</p> </body> </html>
عبارات هذا عنوان ومرحبا بالعالم! ("أهلاً بالعالم!") - النص الذي يظهر حقًا على الصفحة ؛ العناصر الأخرى هي علامات تشير إلى كيفية عرض النص.
عند تحميل صفحة ، يحتاج الروبوت إلى تحليل كود HTML لاستخراج النص والعثور على الروابط. للقيام بذلك ، سوف نستخدم jsoup ، مكتبة جافا مفتوحة المصدر مصممة للتحميل HTML (تحليل) HTML.
نتيجة تحليل HTML هي شجرة DOM (نموذج كائن المستند) تحتوي على عناصر المستند ، بما في ذلك النص والعلامات.
الشجرة هي بنية بيانات ذات صلة تتكون من الذروات التي تمثل النص والعلامات وعناصر أخرى من الوثيقة.
يتم تحديد العلاقة بين القمم من خلال هيكل الوثيقة. في المثال السابق ، العقدة الأولى ، تسمى الجذر ، هي علامة تتضمن روابط إلى الذروتين التي تحتوي عليها و ؛ هذه العقد هي أطفال العقدة الجذرية.
العقدة لها رأس فرعي واحد ، والعقدة لها رأس فرعي واحد
(فقرة من الإنجليزية. فقرة). في الشكل. 6.1 هو تمثيل رسومي لهذه الشجرة.
يتضمن كل قمة روابط إلى العقد التابعة له ؛ بالإضافة إلى ذلك ، تحتوي كل عقدة على رابط إلى أصلها ، بحيث يمكنك التحرك لأعلى ولأسفل الشجرة من أي عقدة. عادةً ما تكون شجرة DOM للصفحات الحقيقية أكثر تعقيدًا من المثال الموضح.
تحتوي معظم المتصفحات على أدوات للتحقق من DOM للصفحة التي تعرضها. في Chrome ، يمكنك النقر بزر الماوس الأيمن على أي جزء من صفحة الويب وتحديد عنصر عرض الرمز في القائمة التي تظهر. في Firefox ، يمكنك النقر بزر الماوس الأيمن وتحديد Explore Item من قائمة السياق. توفر أداة سفاري ويب المفتش المعلومات التي هي في موقع
thinkdast.com/safari . يمكن قراءة تعليمات Internet Explorer بالنقر على الرابط:
thinkdast.com/explorer .
في الشكل. يظهر 6.2 لقطة من شجرة izbrazheniem DOM لصفحة "ويكيبيديا" على
جافا . العنصر المميز هو الفقرة الأولى من نص المقالة ، والمضمن في عنصر <div> بالمعرف = "mw-content-text". سنستخدم معرف العنصر هذا لتحديد نص كل مقالة نقوم بتحميلها.
تطبيق Jsoup
تسهل مكتبة jsoup تحميل صفحات الويب وتحليلها والتنقل عبر شجرة DOM. على سبيل المثال:
String url = "http://en.wikipedia.org/wiki/Java_(programming_language)"; // Connection conn = Jsoup.connect(url); Document doc = conn.get(); // Element content = doc.getElementById("mw-content-text"); Elements paragraphs = content.select("p");
يقبل عنصر Jsoup.connect عنوان URL كسلسلة ويقوم بإنشاء اتصال بخادم الويب ؛ تقوم طريقة get بتحميل تعليمات HTML البرمجية ، وتحليلها ، وإرجاع كائن Document ، وهو DOM.
يتضمن هذا الكائن طرقًا للتنقل في شجرة وتحديد العقد. في الواقع ، يوفر العديد من الطرق التي يمكن أن تكون مربكة. يوضح المثال التالي طريقتين لتحديد العقد.
- يأخذ getElementByld معلمة نوع سلسلة ويبحث عن شجرة للعنصر مع حقل المعرف المقابل. بعد العثور عليه ، اختار العقدة <div id = "mw-content-text" lang = "en" dir = "ltr" class = "mw-content-ltr"> التي تظهر في كل صفحة ويكيبيديا لتحديد العنصر يحتوي <div> على نص الصفحة ، بخلاف شريط التنقل الجانبي والعناصر الأخرى.
- حدد يأخذ سلسلة ، يجتاز الشجرة ، ويعيد جميع العناصر مع علامات مطابقة سلسلة. في هذا المثال ، تقوم بإرجاع كافة علامات الفقرات التي تظهر في المحتوى. القيمة المرجعة هي كائن من النوع Elements.
قبل المتابعة ، يجب عليك مراجعة وثائق هذه الفئات لمعرفة الإجراءات التي يمكنهم القيام بها. أهم الفئات هي Element و Elements و Node ، والتي يمكنك قراءتها عن طريق النقر على
روابط thinkdast.com/jsoupelt و
thinkdast.com/jsoupelts و
thinkdast.com/jsoupnode .
فئة العقدة هي الأعلى في شجرة DOM. هناك العديد من الفئات الفرعية التي تمد العقدة ، بما في ذلك Element و TextNode و DataNode و Comment. إن فئة Elements عبارة عن مجموعة من الكائنات من النوع Element.
في الشكل. 6.3 هو رسم تخطيطي لفئات UML يوضح العلاقات بينهما. يشير الخط بسهم فارغ إلى امتداد فئة إلى أخرى. على سبيل المثال ، يشير هذا المخطط إلى أن العناصر تمد ArrayList. سنعود إلى الرسوم البيانية لفئة UML في القسم الذي يحمل نفس الاسم في الفصل 11.
كرر على شجرة DOM
لجعل حياتك أسهل ، أقدم فئة WikiNodelterable التي تسمح لك بالسير عبر شجرة DOM. فيما يلي مثال يوضح كيفية استخدام هذه الفئة:
Elements paragraphs = content.select("p"); Element firstPara = paragraphs.get(0); Iterable<Node> iter = new WikiNodeIterable(firstPara); for (Node node: iter) { if (node instanceof TextNode) { System.out.print(node); } }
يبدأ هذا المثال باللحظة التي توقف فيها المثال السابق. يقوم بتحديد الفقرة الأولى في الفقرات ثم يقوم بإنشاء فئة WikiNodeIterable التي تطبق واجهة Iterable. يبحث هذا الفصل بعمق ، وينشئ العقد بالترتيب الذي تظهر به على الصفحة.
في المثال الحالي ، لا نعرض العقدة إلا إذا كانت TextNode ، ونتجاهل أنواعها الأخرى ، على وجه الخصوص ، كائنات من النوع Element والتي تمثل العلامات. والنتيجة هي نص فقرة HTML عادي بدون أي ترميز. استنتاجه:
Java هي لغة برمجة كمبيوتر للأغراض العامة متزامنة ، قائمة على الفصل ، موجهة للكائنات ، [13] ومصممة خصيصًا ...
Java هي لغة برمجة كمبيوتر عالمية ، وهي لغة موجهة للكائنات بناءً على الفصول الدراسية ، مع إمكانية البرمجة المتوازية [13] وهي مصممة خصيصًا ...
بحث العمق
هناك عدة طرق لاجتياز شجرة بذكاء. نبدأ ببحث عميق (DFS). يبدأ البحث بجذر الشجرة ويحدد العقدة الفرعية الأولى. إذا كان الأخير لديه أطفال ، فسيتم تحديد العقدة الفرعية الأولى مرة أخرى. عندما تأتي ذروة بدون أطفال ، تحتاج إلى العودة ، والانتقال لأعلى الشجرة إلى العقدة الأم ، حيث يتم تحديد الطفل التالي ، إن وجد. خلاف ذلك ، تحتاج إلى العودة مرة أخرى. عند فحص العقدة الجذرية الفرعية التابعة ، يكتمل الاجتياز.
هناك طريقتان مقبولتان بشكل عام لإجراء بحث متعمق: العودية والتكرارية. تنفيذ العودية بسيط وأنيق:
private static void recursiveDFS(Node node) { if (node instanceof TextNode) { System.out.print(node); } for (Node child: node.childNodes()) { recursiveDFS(child); } }
تسمى هذه الطريقة لكل عقدة في الشجرة ، بدءًا من الجذر. إذا كانت Node هي TextNode ، فستتم طباعة محتوياتها. إذا كان لدى Node أطفال ، فإنه يستدعي تكرار DFS لكل منهم بالترتيب.
في المثال الحالي ، نقوم بطباعة محتويات كل TextNode قبل زيارة العقد الفرعية الخاصة به ، وهذا مثال على اجتياز (طلب مسبق) مباشر. يمكنك أن تقرأ عن
الحلول المباشرة والعكسية (بعد الطلب)
والحلول المتماثلة (بالترتيب)
بالانتقال إلى الرابط
thinkdast.com/treetrav . بالنسبة لهذا التطبيق ، لا يهم ترتيب الزحف.
عند
إجراء مكالمات متكررة ، يستخدم recursiveDFS مكدس الاستدعاءات (انظر
thinkdast.com/callstack ) لتتبع القمم الفرعية ومعالجتها بالترتيب الصحيح. بدلاً من ذلك ، يمكنك استخدام بنية بيانات المكدس لتتبع العقد بنفسك ؛ سيؤدي ذلك إلى تجنب التكرار والتكرار فوق الشجرة بشكل متكرر.
مكدسات في جافا
قبل شرح النسخة التكرارية من البحث العميق ، سوف ألقي نظرة على بنية بيانات المكدس. نبدأ بالمفهوم العام للمكدس ، ثم نتحدث عن واجهات Java التي تحدد طرق المكدس: Stack and Deque.
المكدس هو بنية بيانات تشبه القائمة: هي مجموعة تحافظ على ترتيب العناصر. الفرق الرئيسي بين المكدس والقائمة هو أن الأول يتضمن طرقًا أقل. حسب المكدس ، يوفر المكدس الطرق:
- الدفع ، إضافة عنصر إلى الجزء العلوي من المكدس ؛
- pop ، الذي ينفذ الإزالة ويعيد قيمة العنصر الأعلى في المكدس ؛
- إلقاء نظرة خاطفة ، وإرجاع العنصر الأعلى من المكدس دون تغيير المكدس نفسه ؛
- isEmpty ، مما يشير إلى ما إذا كان المكدس فارغًا.
نظرًا لأن pop دائمًا ما يعرض العنصر الأعلى ، فإن المكدس يُسمى أيضًا LIFO ، وهو ما يعني "آخر مرة ، أول مخرج". بديل للمكدس هو قائمة انتظار تقوم بإرجاع العناصر بنفس الترتيب الذي تمت إضافتها به ، أي "أولاً في ، أولاً يخرج" أو FIFO.
للوهلة الأولى ، ليس من الواضح سبب فائدة المكدسات وقوائم الانتظار: فهي لا توفر أي ميزات خاصة لا يمكن الحصول عليها من القوائم ؛ في الواقع ، لديهم فرص أقل. فلماذا لا تطبق القوائم دائمًا؟ هناك سببان لتبرير مكدسات وقوائم الانتظار.
1. إذا اقتصرت على مجموعة صغيرة من الأساليب (أي واجهة برمجة تطبيقات صغيرة) ، فستكون الشفرة الخاصة بك أكثر قابلية للقراءة وأقل عرضة للأخطاء. على سبيل المثال ، عند استخدام قائمة لتمثيل مكدس ، يمكنك حذف عنصر عن طريق الخطأ في ترتيب خاطئ. مع واجهة برمجة تطبيقات المكدس ، يكون هذا الخطأ مستحيلًا حرفياً. وأفضل طريقة لتجنب الأخطاء هي جعلها مستحيلة.
2. إذا كانت بنية البيانات توفر واجهة برمجة تطبيقات صغيرة ، فمن الأسهل تنفيذها بكفاءة. على سبيل المثال ، تتمثل إحدى الطرق البسيطة لتنفيذ مكدس في استخدام قائمة واحدة. دفع عنصر على المكدس ، نضيفه إلى أعلى القائمة ؛ ظهور عنصر ، نزيله من البداية. للحصول على قائمة مرتبطة ، تعد الإضافة والإزالة من البداية عملية مستمرة للوقت ، لذا فإن هذا التطبيق فعال. على العكس ، فإن واجهات برمجة التطبيقات الكبيرة تكون أكثر صعوبة في التنفيذ بكفاءة.
هناك ثلاث طرق لتطبيق المكدس في Java.
1. تطبيق ArrayList أو LinkedList. عند استخدام ArrayList ، يجب أن تتذكر إضافة وإزالة من النهاية بحيث يتم تنفيذ هذه العمليات في وقت ثابت. تجنب إضافة عناصر إلى المكان الخطأ أو حذفها بترتيب خاطئ.
2. تحتوي Java على فئة مكدس توفر مجموعة قياسية من طرق التكديس. لكن هذا الفصل هو جزء قديم من Java: فهو غير متوافق مع Java Collections Framework ، الذي ظهر لاحقًا.
3. ربما يكون أفضل خيار هو استخدام أحد تطبيقات واجهة Deque ، على سبيل المثال ArrayDeque.
يتكون Deque من قائمة انتظار مزدوجة النهاية ، مما يعني "قائمة انتظار ثنائية الاتجاه". في Java ، توفر واجهة Deque أساليب push و pop و peek و isEmpty ، بحيث يمكن استخدامها ككومة. يحتوي على طرق أخرى ، معلومات متاحة على موقع
thinkdast.com/deque ، ولكن في الوقت الحالي لن نستخدمها.
بحث العمق التكراري
ما يلي هو إصدار تكراري من DFS يستخدم ArrayDeque لتمثيل مجموعة من الكائنات من نوع العقدة:
private static void iterativeDFS(Node root) { Deque<Node> stack = new ArrayDeque<Node>(); stack.push(root); while (!stack.isEmpty()) { Node node = stack.pop(); if (node instanceof TextNode) { System.out.print(node); } List<Node> nodes = new ArrayList<Node>(node. chiidNodesQ); Collections.reverse(nodes); for (Node child: nodes) { stack.push(chiid); } } }
المعلمة الجذر هي جذر الشجرة التي نريد تجاوزها ، لذلك نبدأ بإنشاء مكدس وإضافة هذه المعلمة إليها.
الحلقة مستمرة حتى المكدس فارغ. كل تمرير يدفع العقدة خارج المكدس. إذا تم تلقي TextNode ، تتم طباعة محتوياته. ثم تتم إضافة رؤوس الأطفال إلى المكدس. لمعالجة المتحدرين بالترتيب الصحيح ، تحتاج إلى دفعهم إلى المكدس بالترتيب العكسي ؛ يتم ذلك عن طريق نسخ الرؤوس الفرعية في ArrayList ، وإعادة ترتيب العناصر في مكانها ، ثم تكرار ArrayList المعكوس.
واحدة من مزايا النسخة المتعمقة للبحث المتعمق هي أنه من الأسهل تنفيذه كمتكرر في Java ؛ يتم وصف كيفية القيام بذلك في الفصل التالي.
لكن أولاً ، ملاحظة أخيرة على واجهة Deque: إلى جانب ArrayDeque ، توفر Java تطبيقًا آخر لـ Deque ، صديقنا القديم LinkedList. تطبق الأخيرة كلا الواجهتين: List و Deque. تعتمد الواجهة الناتجة على استخدامه. على سبيل المثال ، عند تعيين LinkedList إلى متغير Deque:
Deqeue<Node> deque = new LinkedList<Node>();
يمكنك تطبيق طرق من واجهة Deque ، ولكن ليس كل الطرق من واجهة List. عن طريق تعيينه في قائمة المتغيرات:
List<Node> deque = new LinkedList<Node>();
يمكنك استخدام أساليب القائمة ، ولكن ليس كل طرق Deque. وتخصيصها على النحو التالي:
LinkedList<Node> deque = new LinkedList<Node>();
يمكن استخدام جميع الطرق. ولكن عند دمج الأساليب من واجهات مختلفة ، سيكون الرمز أقل قابلية للقراءة وأكثر عرضة للخطأ.
»يمكن العثور على مزيد من المعلومات حول الكتاب على
موقع الناشر على الويب»
المحتويات»
مقتطفاتلHabrozhiteley 20٪ قسيمة الخصم -
جافا