{"cells":[{"cell_type":"markdown","metadata":{"id":"mfCAo2t7wCnb"},"source":[" 📗 Introduction à la recherche textuelle (partie 1)"]},{"cell_type":"markdown","metadata":{"id":"QepPJFQjv-vq"},"source":["## 1. Comment chercher un \"mot\" dans un texte ?"]},{"cell_type":"markdown","metadata":{"id":"Vw_CRUwAv-vr"},"source":["On sait déjà chercher un **caractère** dans une chaîne de caractères. \n","Par exemple : écrivez ci-dessous une fonction trouve_lettre(c, texte) qui renvoie le premier indice où l'on a trouvé la lettre `c` dans la chaîne de caractères `texte`, et qui renvoie `None` si la lettre cherchée ne s'y trouve pas."]},{"cell_type":"markdown","metadata":{"id":"DAJD2K3tFKis"},"source":["### 💻 A vous de jouer 1"]},{"cell_type":"code","execution_count":null,"metadata":{"id":"cEBeCRPsv-vs","trusted":true},"outputs":[],"source":["def trouve_lettre(c, texte):\n"," \"\"\"renvoie l'indice de la première occurrence de c dans texte\n"," ou renvoie None par convention sinon\"\"\"\n","\n"," ...\n","\n","assert trouve_lettre('j', 'bonjour') == 3\n","assert trouve_lettre('j', 'alphabet') is None\n"]},{"cell_type":"markdown","metadata":{"id":"KkG3s-vsv-vu"},"source":["Le problème est plus difficile quand il faut chercher non plus un seul caractère mais un **mot** dans le texte.\n","\n","#### Vocabulaire : \n","- on ne parlera pas de 'mot' mais de **motif**, ce qui est plus général.\n","- quand on trouve le motif cherché à un endroit du texte, on dira qu'il s'agit d'une **occurrence** du motif dans le texte : cela désignera l'indice `i` tel que texte[i:i+1] == motif\n","\n","Rappel : la notation chaine[i:j] désigne la *tranche* de la chaîne comprise entre `i` inclus et `j` exclu. On parle de *slicing*.\n"]},{"cell_type":"markdown","metadata":{"id":"I6aGzbVnEJOZ"},"source":[""]},{"cell_type":"code","execution_count":null,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"9M1nEJLKv-vu","outputId":"a77acccb-8895-4289-c5a8-9214a2aefedd","trusted":true},"outputs":[],"source":["# Exemple\n","texte = \"Cher monsieur Gaboriot, bonjour, votre abonnement est fini\"\n","motif = \"bo\"\n","print(texte[16: 18])\n","# Une occurrence du motif cherché est donc 16\n","# Il y en a d'autres..."]},{"cell_type":"markdown","metadata":{"id":"WJPwH1JSv-vx"},"source":["### 1.1. La fonction `find` de Python\n","\n","Python dispose d'une méthode find() attachée aux objets chaînes de caractère qui permet justement de trouver un motif dans la chaîne"]},{"cell_type":"markdown","metadata":{"id":"S0LrsfWcv-vy"},"source":["Pour corser un peu l'affaire, on peut prendre un texte très long. Typiquement, on peut chercher un mot ou une phrase dans tout le texte d’un roman.\n","\n","Le site http://www.gutenberg.org/browse/languages/fr propose les grands classiques de la littérature qui sont\n","tombés dans le domaine public. On peut par exemple y trouver le texte intégral du roman Le rouge et le noir de Stendhal dans\n","l’encodage UTF-8 : http://www.gutenberg.org/ebooks/798.txt.utf-8\n","\n","\n","### 💻 A vous de jouer 2 \n","Télécharger ce roman sur votre ordinateur, vérifiez l'encodage, puis ouvrir ce fichier texte avec Python et charger l'intégralité du fichier texte dans une variable nommée stendhal"]},{"cell_type":"markdown","metadata":{"id":"LfwiqSuaF00H"},"source":["Pour lire ce fichier vous pourrez trouver de la documentation ici : [python doctor](https://python.doctor/page-lire-ecrire-creer-fichier-python)"]},{"cell_type":"code","execution_count":null,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"83XOKN_ev-vz","outputId":"7ceaf193-70fe-4ebd-a7f0-b2c5f9393ae4","trusted":true},"outputs":[],"source":["fichier = open('pg798.txt', 'r', encoding = 'utf-8')\n","stendhal = fichier.read()\n","fichier.close()\n","print(stendhal[0: 800])"]},{"cell_type":"code","execution_count":null,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"_UEaQ9RIJ7gT","outputId":"1e29e09b-29d9-4035-8c59-4fb04dee4aaa","trusted":true},"outputs":[],"source":["print(len(stendhal))"]},{"cell_type":"markdown","metadata":{"id":"aQ3hw5nKv-vz"},"source":["On peut chercher ensuite si le motif 'Julien trembla' apparaît quelque part dans le roman."]},{"cell_type":"code","execution_count":null,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"RuIa7s3bv-vz","outputId":"e8721afb-0b42-4ab2-dd62-9490641b8398","trusted":true},"outputs":[],"source":["stendhal.find('Julien trembla')"]},{"cell_type":"markdown","metadata":{"id":"LjzhvBNov-v2"},"source":["La méthode find a renvoyé un entier correspondant à l'indice de la première occurrence du motif dans le texte. D'ailleurs, on peut vérifier en faisant afficher la suite :"]},{"cell_type":"code","execution_count":null,"metadata":{"colab":{"base_uri":"https://localhost:8080/","height":35},"id":"ZidmRisUv-v2","outputId":"5520b903-fe8f-4b21-e28a-d0793422f0aa","trusted":true},"outputs":[],"source":["stendhal[162926: 162973]"]},{"cell_type":"markdown","metadata":{"id":"Dyn9IyAHv-v4"},"source":["La méthode `find` renvoie -1 si le motif cherché n'apparaît pas dans le texte. Par exemple stendhal.find('Joséphine') renvoie −1 : le prénom Joséphine n’apparaît jamais dans le roman.\n","\n","\n","### 💻 A vous de jouer 3 \n","\n","Une variante de la méthode `find` a deux arguments, le deuxième précise la **position de départ de la recherche**\n","\n","1. En utilisant ce deuxième argument, trouvez s'il y a une occurrence suivante du motif : 'Julien trembla' "]},{"cell_type":"markdown","metadata":{},"source":[]},{"cell_type":"code","execution_count":null,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"HWZw4sZ_v-v4","outputId":"154728a0-d97b-4ba7-f454-bb660d063004","trusted":true},"outputs":[],"source":["# Ecrire le test. Vous devez trouver une réponse négative.\n","..."]},{"cell_type":"markdown","metadata":{"id":"0_mZeGAqv-v5"},"source":["2. Trouvez les deux premières occurrences du mot : 'Julien' dans le roman"]},{"cell_type":"code","execution_count":null,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"oYI9sOJFv-v5","outputId":"9b27eeb9-f07e-496d-de11-aba7fdc5358a","trusted":true},"outputs":[],"source":["occur_1 = ...\n","occur_2 = ...\n","print(\"1ere occurence : \", occur_1)\n","print(\"2eme occurence : \", occur_2)"]},{"cell_type":"markdown","metadata":{"id":"qd5PRmLDv-v5"},"source":["### 1.2. Application de la fonction `find` : compter le nombre d'occurrences"]},{"cell_type":"markdown","metadata":{"id":"TfNOZJ6qv-v6"},"source":["En utilisant la méthode `find`, il est relativement facile de compter les occurrences d'un motif dans un texte. \n","\n","### 💻 A vous de jouer 4 \n","\n","1. Complétez ci-dessous le code de la fonction nb_occurrences(texte, motif).\n","\n","2. Trouvez combien de fois le mot \"mort\" apparaît dans le roman."]},{"cell_type":"code","execution_count":null,"metadata":{"id":"zHZaqdzHSq7y","trusted":true},"outputs":[],"source":["def nb_occurrences(texte, motif):\n"," \"\"\"renvoie le nombre de fois où motif apparaît dans texte \"\"\" \n"," \n"," ...\n","\n"]},{"cell_type":"code","execution_count":null,"metadata":{"id":"cx-j_bJKbUhQ","trusted":true},"outputs":[],"source":["# Quelques tests\n","assert nb_occurrences('bonjour monsieur gaboriot votre abonnement est fini', 'bo') == 3\n","assert nb_occurrences(stendhal, 'Julien') == 1908 \n","assert nb_occurrences(stendhal, 'amour') == 225\n","assert nb_occurrences(stendhal, 'informatique') == 0"]},{"cell_type":"markdown","metadata":{"id":"VRXNpMUdRRJN"},"source":["Autre réponse possible avec une fonction récursive."]},{"cell_type":"code","execution_count":null,"metadata":{"id":"JkuNiiyeDHx_","trusted":true},"outputs":[],"source":["import sys\n","sys.setrecursionlimit(2000)\n","\n","def nb_occurrences_rec(texte, motif, i=0):\n"," occurence = texte.find(motif, i)\n"," if occurence == -1 :\n"," ...\n"," else :\n"," ...\n","\n"]},{"cell_type":"code","execution_count":null,"metadata":{"id":"kVpSCL3cE0zu","trusted":true},"outputs":[],"source":["# Quelques tests\n","assert nb_occurrences_rec('bonjour monsieur gaboriot votre abonnement est fini', 'bo') == 3\n","assert nb_occurrences_rec(stendhal, 'Julien') == 1908\n","assert nb_occurrences_rec(stendhal, 'amour') ==225\n","assert nb_occurrences_rec(stendhal, 'informatique') == 0"]},{"cell_type":"markdown","metadata":{"id":"Wcn9EB6RLdrT"},"source":["---\n","Auteur : Marine Méra - Modification par François Hallé, Jean-Louis Thirot (Lycée Bertrand d'Argentré) et Mireille Coilhac (lycée Saint-Aspais à Melun)\n","\n","\n","![\"Creative](\"https://i.creativecommons.org/l/by-nc-sa/4.0/88x31.png\")
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.\n","\n","\n","---"]}],"metadata":{"colab":{"collapsed_sections":[],"name":"BoyerMoore1_corrigé.ipynb","provenance":[]},"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.7.6"}},"nbformat":4,"nbformat_minor":2}