Bonjour, Habr! Apprenez à implémenter des algorithmes efficaces basés sur les structures de données les plus importantes du langage Java et à mesurer les performances de ces algorithmes. Chaque chapitre est accompagné d'exercices pour aider à consolider le matériel.
- Apprenez à travailler avec des structures de données, par exemple, avec des listes et des dictionnaires, à comprendre comment elles fonctionnent.
- Écrivez une application qui lit les pages Wikipedia, analyse et fournit une navigation dans l'arborescence de données résultante.
- Analysez le code et apprenez à prédire à quelle vitesse il fonctionnera et combien de mémoire il consommera.
- Écrivez des classes qui implémentent l'interface Map et utilisez une table de hachage et un arbre de recherche binaire.
- Créez un moteur de recherche Web simple avec son propre moteur de recherche: il indexera les pages Web, enregistrera leur contenu et renverra les résultats souhaités.
Extrait "Tree Walk"
Dans ce chapitre, nous examinerons une application de moteur de recherche que nous développerons dans le reste du livre. Je (l'auteur) décris les éléments d'un moteur de recherche et présente la première application, un robot de recherche qui télécharge et analyse des pages de Wikipédia. Ce chapitre présente également une implémentation de recherche approfondie récursive et une implémentation itérative utilisant Deque de Java pour implémenter une pile «dernier entré, premier sorti».
Moteurs de recherche
Un moteur de recherche tel que Google Search ou Bing accepte un ensemble de termes de recherche et renvoie une liste de pages Web pertinentes pour ces termes.
Vous pouvez en savoir plus sur
thinkdast.com , mais je vous expliquerai ce dont vous avez besoin au fur et à mesure.
Considérez les principaux composants d'un moteur de recherche.
- Collecte de données (exploration). Vous aurez besoin d'un programme capable de charger une page Web, de l'analyser et d'extraire du texte et des liens vers d'autres pages.
- Indexation Nous avons besoin d'un index qui nous permet de trouver une requête de recherche et les pages qui la contiennent.
- Recherche (récupération). Vous avez besoin d'un moyen de collecter les résultats de l'index et de déterminer les pages les plus pertinentes pour les termes de recherche.
Commençons par le robot de recherche. Son but est de détecter et de charger un ensemble de pages Web. Pour les moteurs de recherche tels que Google et Bing, le défi est de trouver toutes les pages Web, mais souvent ces robots sont limités à un domaine plus petit. Dans notre cas, nous ne lirons que les pages de Wikipédia.
Dans un premier temps, nous allons créer un robot de recherche qui lit la page Wikipédia, trouve le premier lien, va sur une autre page et répète les étapes précédentes. Nous utiliserons ce moteur de recherche pour tester l'hypothèse de la philosophie. Il dit:
"En cliquant sur le premier lien en minuscules dans le texte principal de l'article Wikipédia, puis en répétant cette action pour les articles suivants, vous êtes le plus susceptible d'être redirigé vers une page avec un article sur la philosophie."
Vous pouvez
consulter cette hypothèse et son histoire sur
thinkdast.com/getphil .
Tester une hypothèse vous permettra de créer les principales parties d'un robot de recherche sans avoir à contourner tout Internet ou même Wikipédia. Et je pense que cet exercice est assez intéressant!
Dans plusieurs chapitres, nous allons travailler sur l'indexeur, puis passer au moteur de recherche.
Analyse HTML
Lorsque vous chargez une page Web, son contenu est écrit dans le langage HTML (HyperText Markup Language). Par exemple, ce qui suit est un simple document HTML:
<!DOCTYPE html> <html> <head> <title>This is a title</title> </head> <body> <p>Hello world!</p> </body> </html>
Phrases Ceci est un titre et Bonjour tout le monde! ("Bonjour tout le monde!") - le texte qui apparaît vraiment sur la page; d'autres éléments sont des balises indiquant comment le texte doit être affiché.
Lors du chargement d'une page, notre robot doit analyser le code HTML pour extraire le texte et trouver des liens. Pour ce faire, nous utiliserons jsoup, une bibliothèque Java open source conçue pour charger et analyser (analyser) du HTML.
Le résultat de l'analyse HTML est une arborescence DOM (modèle d'objet document) contenant des éléments de document, y compris du texte et des balises.
Un arbre est une structure de données associée composée de sommets qui représentent du texte, des balises et d'autres éléments d'un document.
La relation entre les sommets est déterminée par la structure du document. Dans l'exemple précédent, le premier nœud, appelé racine, est une balise qui inclut des liens vers les deux sommets qu'il contient et; ces nœuds sont des enfants du nœud racine.
Un nœud a un sommet enfant et un nœud a un sommet enfant
(paragraphe, de l'anglais. paragraphe). Dans la fig. 6.1 est une représentation graphique de cet arbre.
Chaque sommet comprend des liens vers ses nœuds enfants; en outre, chaque nœud contient un lien vers son parent, vous pouvez donc vous déplacer vers le haut et vers le bas de l'arborescence depuis n'importe quel nœud. L'arbre DOM pour les pages réelles est généralement plus complexe que l'exemple décrit.
La plupart des navigateurs disposent d'outils pour vérifier le DOM de la page que vous consultez. Dans Chrome, vous pouvez cliquer avec le bouton droit sur n'importe quelle partie de la page Web et sélectionner l'élément Afficher le code dans le menu qui apparaît. Dans Firefox, vous pouvez cliquer avec le bouton droit et sélectionner Explorer l'élément dans le menu contextuel. Safari fournit l'outil Web Inspector, qui se trouve sur
thinkdast.com/safari . Les instructions pour Internet Explorer peuvent être lues en cliquant sur le lien:
thinkdast.com/explorer .
Dans la fig. La figure 6.2 montre une capture d'écran de l'arborescence DOM pour la page Wikipedia sur
Java . L'élément en surbrillance est le premier paragraphe du corps de l'article, qui est contenu dans l'élément <div> avec id = "mw-content-text". Nous utiliserons cet identifiant d'élément pour déterminer le corps de chaque article que nous téléchargeons.
Application Jsoup
La bibliothèque jsoup facilite le chargement et l'analyse des pages Web et la navigation dans l'arborescence DOM. Par exemple:
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");
L'élément Jsoup.connect accepte l'URL en tant que chaîne et établit une connexion au serveur Web; La méthode get charge le code HTML, le paralyse et renvoie un objet Document, qui est un DOM.
Cet objet comprend des méthodes de navigation dans un arbre et de sélection de nœuds. En fait, il fournit tellement de méthodes qu'il peut être déroutant. L'exemple suivant montre deux façons de sélectionner des nœuds.
- getElementByld prend un paramètre de type chaîne et recherche un arbre pour l'élément avec le champ id correspondant. L'ayant trouvé, il sélectionne le nœud <div id = "mw-content-text" lang = "en" dir = "ltr" class = "mw-content-ltr"> qui apparaît sur chaque page Wikipédia pour identifier l'élément Un <div> contenant le corps de la page, contrairement à la barre de navigation latérale et aux autres éléments.
- select prend une chaîne, traverse l'arborescence et renvoie tous les éléments dont les balises correspondent à la chaîne. Dans cet exemple, il renvoie toutes les balises de paragraphe qui apparaissent dans le contenu. La valeur de retour est un objet de type Elements.
Avant de continuer, vous devez consulter la documentation de ces classes pour savoir quelles actions elles peuvent effectuer. Les classes les plus importantes sont Element, Elements et Node, que vous pouvez consulter en cliquant sur les
liens thinkdast.com/jsoupelt ,
thinkdast.com/jsoupelts et
thinkdast.com/jsoupnode .
La classe Node est le sommet de l'arborescence DOM. Il existe plusieurs sous-classes qui étendent Node, notamment Element, TextNode, DataNode et Comment. La classe Elements est une collection d'objets de type Element.
Dans la fig. 6.3 est un diagramme des classes UML montrant les relations entre elles. Une ligne avec une flèche vide indique l'extension d'une classe à une autre. Par exemple, ce graphique indique que Elements étend ArrayList. Nous reviendrons sur les diagrammes de classes UML dans la section du même nom au chapitre 11.
Itérer sur une arborescence DOM
Pour vous faciliter la vie, je propose une classe WikiNodelterable qui vous permet de parcourir l'arborescence DOM. Voici un exemple qui montre comment utiliser cette classe:
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); } }
Cet exemple commence par le moment où le précédent s'est arrêté. Il sélectionne le premier paragraphe dans les paragraphes, puis crée une classe WikiNodeIterable qui implémente l'interface Iterable. Cette classe recherche en profondeur, créant des nœuds dans l'ordre dans lequel ils apparaissent sur la page.
Dans l'exemple actuel, nous affichons Node uniquement s'il s'agit d'un TextNode et ignorons ses autres types, en particulier les objets de type Element qui représentent des balises. Le résultat est un texte de paragraphe HTML brut sans aucun balisage. Sa conclusion:
Java est un langage de programmation informatique à usage général qui est simultané, basé sur une classe, orienté objet, [13] et spécialement conçu ...
Java est un langage de programmation informatique universel, qui est un langage orienté objet basé sur des classes, avec la possibilité de programmation parallèle [13] et est spécialement conçu ...
Recherche de profondeur
Il existe plusieurs façons de parcourir intelligemment un arbre. Nous commençons par une recherche en profondeur (DFS). La recherche commence par la racine de l'arborescence et sélectionne le premier nœud enfant. Si ce dernier a des enfants, le premier nœud enfant est à nouveau sélectionné. Lorsqu'un pic sans enfants apparaît, vous devez revenir en remontant l'arborescence jusqu'au nœud parent, où l'enfant suivant est sélectionné, le cas échéant. Sinon, vous devez revenir. Lorsque le dernier nœud racine enfant est examiné, la traversée est terminée.
Il existe deux façons généralement acceptées de mettre en œuvre la recherche approfondie: récursive et itérative. L'implémentation récursive est simple et élégante:
private static void recursiveDFS(Node node) { if (node instanceof TextNode) { System.out.print(node); } for (Node child: node.childNodes()) { recursiveDFS(child); } }
Cette méthode est appelée pour chaque nœud de l'arborescence, en commençant à la racine. Si Node est un TextNode, son contenu est imprimé. Si Node a des enfants, il appelle récursifDFS pour chacun d'eux dans l'ordre.
Dans l'exemple actuel, nous imprimons le contenu de chaque TextNode avant de visiter ses nœuds enfants, c'est-à-dire qu'il s'agit d'un exemple de traversée directe (précommande). Vous pouvez lire sur les
solutions de contournement directes, inverses (post-commande) et symétriques (dans l'ordre)
en allant sur le lien
thinkdast.com/treetrav . Pour cette application, l'ordre d'exploration n'a pas d'importance.
Lors des appels récursifs, recursiveDFS utilise la pile d'appels (voir
thinkdast.com/callstack ) pour suivre les sommets enfants et les traiter dans le bon ordre. Vous pouvez également utiliser la structure de données de la pile pour suivre vous-même les nœuds; cela évitera la récursivité et itérera sur l'arbre de manière itérative.
Piles en Java
Avant d'expliquer la version itérative de la recherche en profondeur, j'examinerai la structure des données de la pile. Nous commençons par le concept général de la pile, puis parlons de deux interfaces Java qui définissent les méthodes de la pile: Stack et Deque.
Une pile est une structure de données de type liste: c'est une collection qui maintient l'ordre des éléments. La principale différence entre la pile et la liste est que la première inclut moins de méthodes. Par convention, la pile fournit des méthodes:
- pousser, en ajoutant un élément en haut de la pile;
- pop, qui effectue la suppression et renvoie la valeur de l'élément le plus haut de la pile;
- jeter un œil, renvoyant l'élément le plus haut de la pile sans changer la pile elle-même;
- isEmpty, qui indique si la pile est vide.
Étant donné que pop renvoie toujours l'élément le plus haut, la pile est également appelée LIFO, ce qui signifie «dernier entré, premier sorti». Une alternative à la pile est une file d'attente qui renvoie les éléments dans le même ordre dans lequel ils ont été ajoutés, c'est-à-dire «premier entré, premier sorti» ou FIFO.
À première vue, la raison pour laquelle les piles et les files d'attente sont utiles n'est pas claire: elles ne fournissent aucune fonctionnalité spéciale qui ne pourrait pas être obtenue à partir des listes; en fait, ils ont encore moins de possibilités. Alors pourquoi ne pas toujours appliquer des listes? Il y a deux raisons pour justifier les piles et les files d'attente.
1. Si vous vous limitez à un petit ensemble de méthodes (c'est-à-dire une petite API), votre code sera plus lisible et moins sujet aux erreurs. Par exemple, lorsque vous utilisez une liste pour représenter une pile, vous pouvez accidentellement supprimer un élément dans le mauvais ordre. Avec l'API de pile, une telle erreur est littéralement impossible. Et la meilleure façon d'éviter les erreurs est de les rendre impossibles.
2. Si la structure de données fournit une petite API, il est plus facile de l'implémenter efficacement. Par exemple, un moyen simple d'implémenter une pile consiste à utiliser une seule liste. En poussant un élément sur la pile, nous l'ajoutons en haut de la liste; popping un élément, nous le supprimons dès le début. Pour une liste chaînée, l'ajout et la suppression depuis le début est une opération à temps constant, donc cette implémentation est efficace. Inversement, les grandes API sont plus difficiles à implémenter efficacement.
Il existe trois façons d'implémenter la pile en Java.
1. Appliquez ArrayList ou LinkedList. Lorsque vous utilisez ArrayList, vous devez vous rappeler d'ajouter et de supprimer à la fin afin que ces opérations soient effectuées en temps constant. Évitez d'ajouter des éléments au mauvais endroit ou de les supprimer dans le mauvais ordre.
2. Java a une classe Stack qui fournit un ensemble standard de méthodes de pile. Mais cette classe est une ancienne partie de Java: elle est incompatible avec le Java Collections Framework, qui est apparu plus tard.
3. Le meilleur choix est probablement d'utiliser l'une des implémentations de l'interface Deque, par exemple ArrayDeque.
Deque est formé à partir d'une file d'attente à double extrémité, ce qui signifie «file d'attente bidirectionnelle». En Java, l'interface Deque fournit des méthodes push, pop, peek et isEmpty, de sorte qu'elle peut être utilisée comme une pile. Il contient d'autres méthodes, dont les informations sont disponibles sur
thinkdast.com/deque , mais pour l'instant nous ne les utiliserons pas.
Recherche de profondeur itérative
Voici une version itérative de DFS qui utilise ArrayDeque pour représenter une pile d'objets de type 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); } } }
Le paramètre racine est la racine de l'arbre que nous voulons contourner, nous commençons donc par créer une pile et y ajouter ce paramètre.
La boucle continue jusqu'à ce que la pile soit vide. Chaque passe pousse Node hors de la pile. Si un TextNode est reçu, son contenu est imprimé. Ensuite, les sommets enfants sont ajoutés à la pile. Pour traiter les descendants dans le bon ordre, vous devez les pousser sur la pile dans l'ordre inverse; cela se fait en copiant les sommets enfants dans une ArrayList, en réorganisant les éléments en place, puis en itérant la ArrayList inversée.
L'un des avantages de la version approfondie de la recherche approfondie est qu'elle est plus facile à implémenter en tant qu'itérateur en Java; comment procéder est décrit dans le chapitre suivant.
Mais d'abord, une dernière note sur l'interface Deque: outre ArrayDeque, Java fournit une autre implémentation de Deque, notre vieil ami LinkedList. Ce dernier implémente les deux interfaces: List et Deque. L'interface résultante dépend de son utilisation. Par exemple, lors de l'attribution d'une LinkedList à une variable Deque:
Deqeue<Node> deque = new LinkedList<Node>();
Vous pouvez appliquer des méthodes à partir de l'interface Deque, mais pas toutes les méthodes de l'interface List. En l'affectant à la variable List:
List<Node> deque = new LinkedList<Node>();
vous pouvez utiliser les méthodes List, mais pas toutes les méthodes Deque. Et en les affectant comme suit:
LinkedList<Node> deque = new LinkedList<Node>();
toutes les méthodes peuvent être utilisées. Mais lors de la combinaison de méthodes provenant de différentes interfaces, le code sera moins lisible et plus sujet aux erreurs.
»Plus d'informations sur le livre sont disponibles sur
le site Web de l'éditeur»
Contenu»
Extrait20% de réduction sur le coupon pour
les fermenteurs
Java -
Java