{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"provenance":[],"authorship_tag":"ABX9TyPJw5CVHlw9KPPo0L9KwCge"},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"markdown","source":["#Un Algoritmo di Correzione per un Motore di Ricerca\n","\n","Progetto di *Fabrizio Ferla*\n","\n","##Obiettivo del Progetto\n","L'obiettivo è sviluppare un algoritmo di correzione automatica per il motore di ricerca di Searchify. Questo algoritmo dovrà:\n","\n","* 1. Rilevare automaticamente gli errori di digitazione o le parole non valide.\n","* 2. Suggerire la parola corretta più probabile.\n","* 3. Restituire risultati pertinenti basati sulla correzione suggerita.\n","\n","L'implementazione di questa funzionalità migliorerà notevolmente l'esperienza utente, aumentando l'efficienza del motore di ricerca e la soddisfazione dei clienti."],"metadata":{"id":"Nd6YmIoqAzPK"}},{"cell_type":"code","source":["#Costanti\n","\n","PUNCTUATION = \"!\\\"#$%&'()*+,-./:;<=>?@[\\\\]^_`{|}~\"\n","SPACE = \" \""],"metadata":{"id":"VoMOJfxaEsvG","executionInfo":{"status":"ok","timestamp":1780084218561,"user_tz":-120,"elapsed":27,"user":{"displayName":"Fabrizio Ferla","userId":"15328954300085185958"}}},"execution_count":1,"outputs":[]},{"cell_type":"markdown","source":["Verifica valori in input e rimuove eventuali caratteri speciali all'interno della query"],"metadata":{"id":"TaNDaLQ-Kart"}},{"cell_type":"code","source":["def validate_query(query):\n","  \"\"\"\n","  Verifica che il parametro 'query' sia una stringa.\n","  Se non lo è, viene sollevata una eccezione TypeError.\n","  \"\"\"\n","  if not isinstance(query, str):\n","    raise TypeError(\"La query deve essere una stringa\")\n","\n","def validate_dictionary(dictionary):\n","  \"\"\"\n","  Verifica che il parametro 'dictionary' sia una lista.\n","  Se non lo è, viene sollevata una eccezione TypeError.\n","  \"\"\"\n","  if not isinstance(dictionary, list):\n","    raise TypeError(\"Dictionary deve essere una lista\")\n","\n","def validate_input(query, dictionary):\n","  \"\"\"\n","  Controlla la validità degli input per la funzione suggestion_correction.\n","  Se query non è una stringa o dictionary non è una lista, viene sollevata una eccezione TypeError.\n","  \"\"\"\n","  validate_query(query) # Chiamata a funzione di controllo query\n","  validate_dictionary(dictionary) # Chiamata a funzione di controllo dictionary\n","\n","def remove_puntuation(query):\n","  \"\"\"\n","  Rimuove la punteggiatura da una stringa.\n","  Restituisce la stringa senza punteggiatura.\n","  \"\"\"\n","  for char in PUNCTUATION: # Cicla tutti i caratteri speciali\n","    query = query.replace(char, SPACE) # Sostituisce il carattere speciale con uno spazio\n","  return query #Restituisce la query senza caratteri speciali\n","\n","def normalize_input(query,dictionary):\n","  \"\"\"\n","  Normalizza gli input convertendo tutto in minuscolo.\n","  Rimuove la punteggiatura dalle query e converte il dizionario in minuscolo.\n","  Ritorna tuple di tipo (query_normalizzata, dictionary_normalizzato)\n","  \"\"\"\n","  query = query.lower() # Converte tutti i caratteri della parola in minuscolo\n","  query = remove_puntuation(query) # Rimuove i caratteri speciali\n","  dictionary = [word.lower() for word in dictionary]  # Converte tutti i caratteri del dizionario in minuscolo\n","  return query, dictionary # Ritorna sia la query che il dizionario in minuscolo"],"metadata":{"id":"rP894fCUArmz","executionInfo":{"status":"ok","timestamp":1780084218570,"user_tz":-120,"elapsed":13,"user":{"displayName":"Fabrizio Ferla","userId":"15328954300085185958"}}},"execution_count":2,"outputs":[]},{"cell_type":"markdown","source":["##L'algoritmo di Levenshtein\n","\n","L'algoritmo di Levenshtein permette di misurare la somiglianza tra due stringhe.\n","\n","Date due stringhe *s1* e *s2*, l'algoritmo permette di misrare le modifche minime necessarie per trasformare la stringa *s1* in *s2*.\n","\n","Le operazione permesse sono:\n","\n","* Eliminazione di un carattere\n","* Sostituzione di un carattere con un altro\n","* Inserimento di un nuovo carattere\n","\n"],"metadata":{"id":"RvODnLbxAwCx"}},{"cell_type":"code","execution_count":3,"metadata":{"id":"tZd0ypzVy98O","executionInfo":{"status":"ok","timestamp":1780084218614,"user_tz":-120,"elapsed":24,"user":{"displayName":"Fabrizio Ferla","userId":"15328954300085185958"}}},"outputs":[],"source":["def levenshtein_distance(s1, s2):\n","  \"\"\"\n","  Calcola la distanza di Levenshtein tra due stringhe.\n","\n","  La distanza di Levenshtein rappresenta il numero minimo di operazioni\n","  (inserimento, cancellazione, sostituzione) necessarie per trasformare\n","  una stringa nell'altra.\n","  \"\"\"\n","  n = len(s1) # Lunghezza della prima stringa\n","  m = len(s2) # Lunghezza della seconda stringa\n","\n","  # Creazione della matrice (n+1) x (m+1)\n","  matrix = [[0] * (m + 1) for _ in range(n + 1)]\n","\n","  # Inizializzazione prima colonna (cancellazioni)si\n","  for i in range(1,n+1):\n","    matrix[i][0]=i\n","\n","  # Inizializzazione prima riga (inserimenti)\n","  for j in range(1,m+1):\n","    matrix[0][j]=j\n","\n","  # Riempimento della matrice\n","  for i in range(n+1):\n","    for j in range(m+1):\n","\n","      # Se i caratteri sono uguali, costo = 0 altrimenti costo = 1\n","      if (s1[i-1]==s2[j-1]):\n","        subcost = 0\n","      else:\n","        subcost=1\n","      k = min(\n","          matrix[i-1][j]+1, # - cancellazione\n","          matrix[i][j-1]+1, # - inserimento\n","          matrix[i-1][j-1]+subcost # - sostituzione\n","      )\n","      matrix[i][j]=k\n","  #Restituisce le modifiche minime necessarie per trasformare la stringa *s1* in *s2*.\n","  distance = matrix[n][m]\n","  return distance"]},{"cell_type":"code","source":["def is_numeric_word(word):\n","    \"\"\"\n","    Controlla se la parola passata come argomento è un numero.\n","    Se la parola è un numero la funzione restitusce True, False altrimenti\n","    \"\"\"\n","    return word.isdigit()\n","\n","def is_word_in_dictionary(word, dictionary):\n","    \"\"\"\n","    Controlla se la parola passata come argomento è contenuta all'interno del dizionario.\n","    Se la parola è contenuta nel dizionario la funione restituisce True, False altrimenti\n","    \"\"\"\n","    return word in dictionary\n","\n","\n","def suggest_correction(query, dictionary):\n","  \"\"\"\n","  Trova la parola simile alla query all'interno di un dizionario.\n","\n","  Usa la distanza di Levenshtein per determinare la parola più vicina\n","\n","  - Se la query è già presente nel dizionario → la restituisce\n","  - Altrimenti → restituisce la parola più simile alla query\n","  \"\"\"\n","  validate_input(query, dictionary) #Verifica i parametri in ingresso\n","  query, dictionary = normalize_input(query, dictionary)\n","  words = query.split() # la parola viene divisa in tante parti\n","  corrected_words = [] #Lista delle parole corrette\n","\n","  for word in words:\n","      if is_numeric_word(word): #Verifica se word è un numero\n","        corrected_words.append(word) #Inserisce il numero senza modificarlo\n","        continue\n","\n","      if is_word_in_dictionary(word,dictionary): #Verifia se la parola è contunuta nel dizionario\n","          corrected_words.append(word) # Se la parola è presente la inserisce nelle parole corrette\n","          continue\n","\n","      result = word\n","      min_distance = float('inf')\n","\n","      for suggestion in dictionary:\n","          distance = levenshtein_distance(word, suggestion) # Calcola la distanza minima tra la parola presente nella query e quelle del dizionario\n","\n","          if distance < min_distance: # Confronta la minima distanza trovata con la distanza della parola corrente\n","              min_distance = distance\n","              result = suggestion\n","\n","      if min_distance > 2:\n","          corrected_words.append(word)\n","      else:\n","          corrected_words.append(result)\n","\n","  return SPACE.join(corrected_words) #Ritorna la query corretta"],"metadata":{"id":"AQglIz95Br7M","executionInfo":{"status":"ok","timestamp":1780084218615,"user_tz":-120,"elapsed":16,"user":{"displayName":"Fabrizio Ferla","userId":"15328954300085185958"}}},"execution_count":4,"outputs":[]},{"cell_type":"markdown","source":["Dizionario base contenente 50 parole."],"metadata":{"id":"b_FAWVwDBs7Q"}},{"cell_type":"code","metadata":{"id":"b193c256","executionInfo":{"status":"ok","timestamp":1780084218623,"user_tz":-120,"elapsed":22,"user":{"displayName":"Fabrizio Ferla","userId":"15328954300085185958"}}},"source":["dictionary = [\n","    \"casa\", \"sole\", \"mare\", \"amore\", \"cielo\", \"pane\", \"acqua\", \"vino\", \"libro\", \"tempo\",\n","    \"giorno\", \"notte\", \"amico\", \"felice\", \"grande\", \"piccolo\", \"bello\", \"verde\", \"rosso\", \"blu\",\n","    \"mangiare\", \"dormire\", \"parlare\", \"studiare\", \"lavorare\", \"viaggiare\", \"leggere\", \"scrivere\", \"correre\", \"camminare\",\n","    \"famiglia\", \"scuola\", \"città\", \"paese\", \"strada\", \"storia\", \"futuro\", \"presente\", \"rapporto\", \"musica\",\n","    \"arte\", \"sport\", \"felicità\", \"tristezza\", \"speranza\", \"coraggio\", \"pace\", \"guerra\", \"natura\", \"mondo\"\n","]\n","\n"],"execution_count":5,"outputs":[]},{"cell_type":"markdown","source":["Test di funzionamento con 10 casi d'uso (inclusi errori comuni e query corrette)."],"metadata":{"id":"RSj4xS2IBvi8"}},{"cell_type":"code","metadata":{"id":"b59463c7","executionInfo":{"status":"ok","timestamp":1780084218624,"user_tz":-120,"elapsed":21,"user":{"displayName":"Fabrizio Ferla","userId":"15328954300085185958"}}},"source":["test_queries = [\n","    \"casa\", \"sote\", \"mare\",\n","    \"raporto natura 2023\",\n","    \"studiare informatica\",\n","    \"acua vio pane\"\n","]\n"],"execution_count":6,"outputs":[]},{"cell_type":"markdown","source":["Test di funzionamento con casi d'uso e dizionario\n","\n","Per ogni valore presente nella lista *test_queries* chiama la funzione *suggest_correction* e retrituisce il suggerimento della stessa parola"],"metadata":{"id":"iyULt2hXBwMy"}},{"cell_type":"code","source":["for query in test_queries:\n","    correction = suggest_correction(query, dictionary)\n","    print(f\"Input: {query} -> Suggerimento: {correction}\")"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"KJVZwJgdIDjf","executionInfo":{"status":"ok","timestamp":1780084218657,"user_tz":-120,"elapsed":25,"user":{"displayName":"Fabrizio Ferla","userId":"15328954300085185958"}},"outputId":"9dc00111-2e4b-48a4-e465-18f5a4f55ce1"},"execution_count":7,"outputs":[{"output_type":"stream","name":"stdout","text":["Input: casa -> Suggerimento: casa\n","Input: sote -> Suggerimento: sole\n","Input: mare -> Suggerimento: mare\n","Input: raporto natura 2023 -> Suggerimento: rapporto natura 2023\n","Input: studiare informatica -> Suggerimento: studiare informatica\n","Input: acua vio pane -> Suggerimento: acqua vino pane\n"]}]},{"cell_type":"markdown","source":["Prende in input la stringa dell'utente e restituisce la parola corretta più probabile o la query originale se è già valida."],"metadata":{"id":"CKm_RsdiBty-"}},{"cell_type":"code","source":["query = input(\"Inserisci una query: \") # Richiede all'utente di inserire una query\n","correction = suggest_correction(query, dictionary) # Restituisce la query corretta\n","print(f\"Input: {query} -> Suggerimento: {correction}\") #Stampa a video la query inserita e il suggerimento"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"vwlyNxGGz_ly","executionInfo":{"status":"ok","timestamp":1780084244412,"user_tz":-120,"elapsed":25764,"user":{"displayName":"Fabrizio Ferla","userId":"15328954300085185958"}},"outputId":"803687b7-2fe5-46ce-fbb0-415d5d5c68c2"},"execution_count":8,"outputs":[{"output_type":"stream","name":"stdout","text":["Inserisci una query: Celo\n","Input: Celo -> Suggerimento: cielo\n"]}]},{"cell_type":"markdown","source":["#Conclusione\n","\n","Grazie e questo codice è possibile :\n","\n","* Rilevare automaticamente gli errori di digitazione o le parole non valide.\n","\n","* Suggerire la parola corretta più probabile.\n","\n","* Restituire risultati pertinenti basati sulla correzione suggerita.\n","\n","Il codice è stato scritto utilizzando le regole del *Clean Codig*:\n","\n","* Nomi di variabili parlanti\n","\n","* Nomi di funzioni e variabili rispettano la convenzione *snake_case*\n","\n","* Codice documentato che spiega il funzionamento dell'intero flusso e dell'algoritmo proposto dal testo\n","\n","* Codice testato con casi d'uso\n","\n","* Ogni funzione è responsabile di una sola azione **(Singola Responsabilità)**\n","\n","* Gestione degli errori per i valori in input\n","\n","\n"],"metadata":{"id":"P2Ji_vdn7Zze"}}]}