Halo, Habr! Pelajari cara menerapkan algoritma yang efisien berdasarkan pada struktur data paling penting dalam bahasa Java, dan bagaimana mengukur kinerja algoritma ini. Setiap bab disertai dengan latihan untuk membantu mengkonsolidasikan materi.
- Belajar bekerja dengan struktur data, misalnya, dengan daftar dan kamus, pahami cara kerjanya.
- Tulis aplikasi yang membaca halaman Wikipedia, mem-parsing, dan menyediakan navigasi melalui pohon data yang dihasilkan.
- Analisis kode dan pelajari cara memprediksi seberapa cepat akan bekerja dan berapa banyak memori yang akan dikonsumsi.
- Tulis kelas yang mengimplementasikan antarmuka Peta, dan gunakan tabel hash dan pohon pencarian biner.
- Buat mesin pencarian web sederhana dengan mesin pencari sendiri: itu akan mengindeks halaman web, menyimpan konten mereka dan mengembalikan hasil yang diinginkan.
Kutipan "Tree Walk"
Dalam bab ini, kita akan melihat aplikasi mesin pencari yang akan kita kembangkan sepanjang sisa buku ini. Saya (penulis) menjelaskan elemen-elemen mesin pencari dan menyajikan aplikasi pertama, robot pencarian yang mengunduh dan menganalisis halaman dari Wikipedia. Bab ini juga memperkenalkan implementasi pencarian mendalam rekursif dan implementasi berulang menggunakan Deque dari Jawa untuk mengimplementasikan stack "last in, first out".
Mesin pencari
Mesin pencari seperti Google Search atau Bing menerima serangkaian istilah pencarian dan mengembalikan daftar halaman web yang relevan dengan istilah-istilah ini.
Anda dapat membaca lebih lanjut di
thinkdast.com , tetapi saya akan menjelaskan apa yang Anda butuhkan saat Anda pergi.
Pertimbangkan komponen utama mesin pencari.
- Pengumpulan data (perayapan). Anda membutuhkan program yang dapat memuat halaman web, menganalisisnya, dan mengekstrak teks dan tautan apa pun ke halaman lain.
- Pengindeksan Kami membutuhkan indeks yang memungkinkan kami menemukan kueri penelusuran dan halaman yang memuatnya.
- Cari (pengambilan). Anda memerlukan cara untuk mengumpulkan hasil dari indeks dan menentukan halaman yang paling relevan dengan istilah pencarian.
Mari kita mulai dengan robot pencarian. Tujuannya adalah untuk mendeteksi dan memuat sekumpulan halaman web. Untuk mesin pencari seperti Google dan Bing, tantangannya adalah menemukan semua halaman web, tetapi seringkali robot ini terbatas pada domain yang lebih kecil. Dalam kasus kami, kami hanya akan membaca halaman dari Wikipedia.
Sebagai langkah pertama, kami akan membuat robot pencarian yang membaca halaman Wikipedia, menemukan tautan pertama, membuka halaman lain dan mengulangi langkah-langkah sebelumnya. Kami akan menggunakan mesin pencari ini untuk menguji hipotesis Getting to Philosophy. Dikatakan:
"Dengan mengeklik tautan huruf kecil pertama di teks utama artikel Wikipedia dan kemudian mengulangi tindakan ini untuk artikel selanjutnya, Anda kemungkinan besar akan dibawa ke halaman dengan artikel tentang filsafat."
Anda dapat
melihat hipotesis ini dan sejarahnya di
thinkdast.com/getphil .
Menguji hipotesis akan memungkinkan Anda untuk membuat bagian utama robot pencarian tanpa perlu mem-bypass seluruh Internet atau bahkan seluruh Wikipedia. Dan saya pikir latihan ini cukup menarik!
Dalam beberapa bab, kami akan mengerjakan pengindeks, dan kemudian beralih ke mesin pencari.
Penguraian HTML
Saat Anda memuat halaman web, isinya ditulis dalam HyperText Markup Language (HTML). Misalnya, berikut ini adalah dokumen HTML sederhana:
<!DOCTYPE html> <html> <head> <title>This is a title</title> </head> <body> <p>Hello world!</p> </body> </html>
Frase Ini adalah judul dan Halo dunia! ("Halo dunia!") - teks yang benar-benar muncul di halaman; elemen lainnya adalah tag yang menunjukkan bagaimana teks harus ditampilkan.
Saat memuat halaman, robot kami perlu mengurai kode HTML untuk mengekstrak teks dan menemukan tautan. Untuk melakukan ini, kita akan menggunakan jsoup, perpustakaan Java open source yang dirancang untuk memuat dan mem-parsing (mem-parsing) HTML.
Hasil parsing HTML adalah pohon DOM (Document Object Model) yang berisi elemen dokumen, termasuk teks dan tag.
Pohon adalah struktur data terkait yang terdiri dari simpul yang mewakili teks, tag, dan elemen lain dari dokumen.
Hubungan antara simpul ditentukan oleh struktur dokumen. Pada contoh sebelumnya, simpul pertama, yang disebut root, adalah tag yang menyertakan tautan ke dua simpul yang dikandungnya dan; simpul-simpul ini adalah anak-anak dari simpul akar.
Sebuah simpul memiliki satu simpul anak, dan sebuah simpul memiliki simpul satu anak
(paragraf, dari bahasa Inggris. paragraf). Dalam gbr. 6.1 adalah representasi grafis dari pohon ini.
Setiap dhuwur menyertakan tautan ke simpul turunannya; selain itu, setiap node berisi tautan ke induknya, sehingga Anda dapat memindahkan naik turun pohon dari sembarang simpul. Pohon DOM untuk halaman nyata biasanya lebih kompleks daripada contoh yang dijelaskan.
Sebagian besar browser memiliki alat untuk memeriksa DOM dari halaman yang Anda lihat. Di Chrome, Anda dapat mengklik kanan pada bagian mana pun dari halaman web dan memilih item Lihat kode di menu yang muncul. Di Firefox, Anda dapat mengklik kanan dan memilih Jelajahi Item dari menu konteks. Safari menyediakan alat Web Inspector, yang terletak di
thinkdast.com/safari . Instruksi untuk Internet Explorer dapat dibaca dengan mengklik tautan:
thinkdast.com/explorer .
Dalam gbr. Gambar 6.2 menunjukkan tangkapan layar pohon DOM untuk halaman Wikipedia tentang
Java . Elemen yang disorot adalah paragraf pertama dari tubuh artikel, yang terkandung dalam elemen <div> dengan id = "mw-content-text". Kami akan menggunakan pengidentifikasi elemen ini untuk menentukan isi setiap artikel yang kami unggah.
Aplikasi Jsoup
Pustaka jsoup memudahkan memuat dan menganalisis halaman web dan menavigasi pohon DOM. Sebagai contoh:
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");
Elemen Jsoup.connect menerima URL sebagai string dan membuat koneksi ke server web; Metode get memuat kode HTML, mem-parsingnya, dan mengembalikan objek Dokumen, yang merupakan DOM.
Objek ini mencakup metode untuk menavigasi pohon dan memilih node. Bahkan, ia menyediakan begitu banyak metode yang bisa membingungkan. Contoh berikut menunjukkan dua cara untuk memilih node.
- getElementByld mengambil parameter tipe string dan mencari pohon untuk elemen dengan bidang id yang sesuai. Setelah menemukannya, ia memilih simpul <div id = "mw-content-text" lang = "en" dir = "ltr" class = "mw-content-ltr">, yang muncul di setiap halaman Wikipedia untuk mengidentifikasi elemen <div> yang berisi isi halaman, tidak seperti bilah navigasi samping dan elemen lainnya.
- pilih mengambil String, melintasi pohon, dan mengembalikan semua elemen dengan Tag yang cocok dengan String. Dalam contoh ini, ia mengembalikan semua tag paragraf yang muncul dalam konten. Nilai kembali adalah objek tipe Elemen.
Sebelum melanjutkan, Anda harus meninjau dokumentasi untuk kelas-kelas ini untuk mengetahui tindakan apa yang dapat mereka lakukan. Kelas yang paling penting adalah Elemen, Elemen, dan Node, yang dapat Anda baca dengan mengklik tautan
thinkdast.com/jsoupelt ,
thinkdast.com/jsoupelts, dan
thinkdast.com/jsoupnode .
Kelas Node adalah yang teratas di pohon DOM. Ada beberapa subclass yang memperpanjang Node, termasuk Elemen, TextNode, DataNode, dan Komentar. Kelas Elemen adalah kumpulan objek bertipe Elemen.
Dalam gbr. 6.3 adalah diagram kelas UML yang menunjukkan hubungan di antara mereka. Baris dengan panah kosong menunjukkan ekstensi dari satu kelas ke kelas lain. Misalnya, bagan ini menunjukkan bahwa Elemen memperluas ArrayList. Kami akan kembali ke diagram kelas UML di bagian dengan nama yang sama di Bab 11.
Iterate di atas pohon DOM
Untuk membuat hidup Anda lebih mudah, saya menyediakan kelas WikiNodelterable yang memungkinkan Anda berjalan melalui pohon DOM. Berikut ini adalah contoh yang menunjukkan cara menggunakan kelas ini:
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); } }
Contoh ini dimulai dengan saat di mana yang sebelumnya berhenti. Dia memilih paragraf pertama dalam paragraf dan kemudian membuat kelas WikiNodeIterable yang mengimplementasikan antarmuka Iterable. Kelas ini mencari secara mendalam, membuat simpul sesuai urutan kemunculannya pada halaman.
Dalam contoh saat ini, kami menampilkan Node hanya jika itu adalah TextNode, dan mengabaikan tipe lainnya, khususnya, objek tipe Elemen yang mewakili tag. Hasilnya adalah teks paragraf HTML biasa tanpa markup. Kesimpulannya:
Java adalah bahasa pemrograman komputer tujuan umum yang konkuren, berbasis kelas, berorientasi objek, [13] dan dirancang khusus ...
Java adalah bahasa pemrograman komputer universal, yang merupakan bahasa berorientasi objek berdasarkan kelas, dengan kemungkinan pemrograman paralel [13] dan dirancang khusus ...
Pencarian Kedalaman
Ada beberapa cara untuk melintasi pohon secara cerdas. Kami mulai dengan pencarian mendalam-pertama (DFS). Pencarian dimulai dengan akar pohon dan memilih simpul anak pertama. Jika yang terakhir memiliki anak, maka simpul anak pertama dipilih lagi. Ketika puncak tanpa anak-anak menemukan, Anda harus kembali, memindahkan pohon ke simpul orangtua, di mana anak berikutnya dipilih, jika ada. Jika tidak, Anda harus kembali lagi. Ketika simpul akar anak terakhir diperiksa, traversal selesai.
Ada dua cara yang diterima secara umum untuk menerapkan pencarian mendalam: rekursif dan berulang. Implementasi rekursif sederhana dan elegan:
private static void recursiveDFS(Node node) { if (node instanceof TextNode) { System.out.print(node); } for (Node child: node.childNodes()) { recursiveDFS(child); } }
Metode ini dipanggil untuk setiap Node di pohon, mulai dari root. Jika Node adalah TextNode, maka isinya akan dicetak. Jika Node memiliki anak-anak, ia memanggil recursiveDFS untuk masing-masing dari mereka secara berurutan.
Dalam contoh saat ini, kami mencetak konten dari setiap TextNode sebelum mengunjungi simpul turunannya, yaitu, ini adalah contoh dari traversal langsung (pre-order). Anda dapat membaca tentang
penyelesaian langsung, mundur (pasca-pesanan) dan simetris (berurutan)
dengan masuk ke tautan
thinkdast.com/treetrav . Untuk aplikasi ini, urutan perayapan tidak masalah.
Saat
melakukan panggilan rekursif, recursiveDFS menggunakan tumpukan panggilan (lihat
thinkdast.com/callstack ) untuk melacak simpul anak dan memprosesnya dalam urutan yang benar. Atau, Anda dapat menggunakan struktur data tumpukan untuk melacak node sendiri; ini akan menghindari rekursi dan beralih ke pohon berulang-ulang.
Tumpukan di Jawa
Sebelum menjelaskan versi pencarian kedalaman yang berulang, saya akan melihat struktur data stack. Kita mulai dengan konsep umum stack, dan kemudian berbicara tentang dua antarmuka Java yang mendefinisikan metode stack: Stack dan Deque.
Tumpukan adalah struktur data seperti daftar: tumpukan adalah kumpulan yang mempertahankan urutan elemen. Perbedaan utama antara tumpukan dan daftar adalah bahwa yang pertama mencakup lebih sedikit metode. Secara konvensional, stack menyediakan metode:
- dorong, menambahkan elemen ke bagian atas tumpukan;
- pop, yang melakukan penghapusan dan mengembalikan nilai elemen paling atas dari tumpukan;
- mengintip, mengembalikan elemen paling atas dari tumpukan tanpa mengubah tumpukan itu sendiri;
- isEmpty, yang menunjukkan apakah tumpukan kosong.
Karena pop selalu mengembalikan elemen paling atas, stack juga disebut LIFO, yang berarti "last in, first out". Alternatif tumpukan adalah antrian yang mengembalikan item dalam urutan yang sama dengan yang ditambahkan, yaitu, "masuk pertama, keluar pertama", atau FIFO.
Sekilas, tidak jelas mengapa tumpukan dan antrian berguna: mereka tidak menyediakan fitur khusus yang tidak dapat diperoleh dari daftar; pada kenyataannya, mereka bahkan memiliki lebih sedikit peluang. Jadi mengapa tidak mendaftar selalu? Ada dua alasan untuk membenarkan tumpukan dan antrian.
1. Jika Anda membatasi diri Anda pada serangkaian kecil metode (yaitu, API kecil), maka kode Anda akan lebih mudah dibaca dan lebih sedikit rawan kesalahan. Misalnya, saat menggunakan daftar untuk mewakili tumpukan, Anda dapat secara tidak sengaja menghapus item dalam urutan yang salah. Dengan stack API, kesalahan semacam itu benar-benar mustahil. Dan cara terbaik untuk menghindari kesalahan adalah membuatnya menjadi tidak mungkin.
2. Jika struktur data menyediakan API kecil, maka lebih mudah untuk diterapkan secara efisien. Misalnya, cara sederhana untuk mengimplementasikan tumpukan adalah dengan menggunakan satu daftar. Mendorong item ke tumpukan, kami menambahkannya ke bagian atas daftar; muncul elemen, kami menghapusnya dari awal. Untuk daftar tertaut, menambah dan menghapus dari awal adalah operasi waktu yang konstan, sehingga implementasi ini efektif. Sebaliknya, API besar lebih sulit untuk diterapkan secara efisien.
Ada tiga cara untuk mengimplementasikan tumpukan di Jawa.
1. Terapkan ArrayList atau LinkedList. Saat menggunakan ArrayList, Anda harus ingat untuk menambah dan menghapus dari ujung sehingga operasi ini dilakukan dalam waktu yang konstan. Hindari menambahkan item ke tempat yang salah atau menghapusnya dengan urutan yang salah.
2. Java memiliki kelas Stack yang menyediakan serangkaian metode stack standar. Tetapi kelas ini adalah bagian lama dari Java: tidak kompatibel dengan Java Collections Framework, yang muncul kemudian.
3. Mungkin pilihan terbaik adalah menggunakan salah satu implementasi dari antarmuka Deque, misalnya ArrayDeque.
Deque dibentuk dari antrian berujung dua, yang berarti "antrian dua arah." Di Java, antarmuka Deque menyediakan metode push, pop, peek, dan isEmpty, sehingga dapat digunakan sebagai stack. Ini berisi metode lain, informasi yang tersedia di
thinkdast.com/deque , tetapi untuk saat ini kami tidak akan menggunakannya.
Pencarian Kedalaman Iteratif
Berikut ini adalah versi berulang DFS yang menggunakan ArrayDeque untuk mewakili tumpukan objek tipe Node:
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); } } }
Parameter root adalah root dari pohon yang ingin kita bypass, jadi kita mulai dengan membuat stack dan menambahkan parameter ini ke dalamnya.
Loop berlanjut hingga tumpukan kosong. Setiap pass mendorong Node keluar dari stack. Jika TextNode diterima, isinya akan dicetak. Kemudian, simpul anak ditambahkan ke tumpukan. Untuk memproses keturunan dalam urutan yang benar, Anda harus mendorong mereka ke tumpukan dengan urutan terbalik; ini dilakukan dengan menyalin simpul anak ke dalam ArrayList, mengatur ulang elemen di tempatnya, dan kemudian mengulangi ArrayList yang terbalik.
Salah satu keuntungan dari versi pencarian mendalam adalah bahwa lebih mudah untuk diterapkan sebagai Iterator di Jawa; bagaimana melakukan ini dijelaskan pada bab berikutnya.
Tapi pertama-tama, catatan terakhir pada antarmuka Deque: selain ArrayDeque, Java menyediakan implementasi lain dari Deque, teman lama kami LinkedList. Yang terakhir mengimplementasikan kedua antarmuka: Daftar dan Deque. Antarmuka yang dihasilkan tergantung pada penggunaannya. Misalnya, ketika menetapkan LinkedList ke variabel Deque:
Deqeue<Node> deque = new LinkedList<Node>();
Anda dapat menerapkan metode dari antarmuka Deque, tetapi tidak semua metode dari antarmuka Daftar. Dengan menugaskannya ke Daftar variabel:
List<Node> deque = new LinkedList<Node>();
Anda dapat menggunakan metode Daftar, tetapi tidak semua metode Deque. Dan menugaskan mereka sebagai berikut:
LinkedList<Node> deque = new LinkedList<Node>();
semua metode dapat digunakan. Tetapi ketika menggabungkan metode dari antarmuka yang berbeda, kodenya akan lebih mudah dibaca dan lebih rentan kesalahan.
»Informasi lebih lanjut tentang buku ini dapat ditemukan di
situs web penerbit»
Isi»
Kutipan20% diskon kupon untuk
Java Fermentor -
Jawa