A distância de Levenshtein: Usando a distância entre palavras para encontrar tesouros.

Neste texto curto e bem humorado, utilizamos uma história de piratas para apresentar um conceito super importante para Processamento de Linguagem Natural (NLP) e Inteligência Artificial, especialmente a AI Generativa: A distancia de Levenshtein, bem como sua aplicação usando Python.

Pirata Barba Negra por Christian Zambra, feito por edição manual sobre um arquivo gerado por leonardo.ai.

Introdução: Em busca de um tesouro

Nosso pirata Barba Negra está prestes a sair para uma nova aventura. Porém ele é um pirata esquecido. Está em busca do tesouro descrito por Peter Pan, mas não lembra sua localização.

Uma alternativa seria ler o livro de Peter Pan novamente, mas ele não é muito de ler.

A outra é… vamos programar!

Sabendo que existe uma função que calcula a distancia entre palavras, ele vai utilizá-la para encontrar no texto palavras próximas (afinal ele não lembra se era tesouro ou tesouros) e retornar as frases onde estão essas palavras, na esperança de que em uma dessas frases estejam pistas da localização do tesouro.

Distancia de Levenshtein

Conceito muito utilizado na linguagem natural e em Inteligência Artificial, especialmente a AI Generativa, a distância criada pelo soviético Vladimir Levenshtein pode ser conceituada da seguinte maneira:

É a distancia ou diferença entre duas palavras, considerando cada alteração necessária para que uma dada palavra se transforme em outra como 1.

Por exemplo, a distância entre a palavra tesouro e tesoura é 1, pois só é necessário trocar a letra “o” pela letra “a”. Da mesma forma, a distância entra a palavra “tesouro” e “tesouros” é 1, pois só é necessário acrescentar a letra “s”.

Código em Python:

Optei por usar o Google Colab, o link está no final.

Assim, tive que primeiramente instalar as bibliotecas para acessar o .pdf (do livro do Peter Pan) no Google Drive, e para ler PDFs.

# Instalando a biblioteca necessária
!pip install pydrive2 PyPDF2

Logo após, importei as bibliotecas necessárias, e acessei o Google Drive (ao rodar esse bloco, o Colab vai pedir autorização para acessar o seu Drive).

# Importando as bibliotecas
import PyPDF2
from collections import Counter
import re
from unidecode import unidecode

from google.colab import drive
drive.mount('/content/drive')

Aqui, explicito onde está o livro em que vamos pesquisar

# Caminho completo do arquivo PDF no Google Drive
file_path = '/content/drive/MyDrive/levenshtein/PeterPan.pdf'

Aqui, introduzo a função de Levenshtein

# Função para calcular a distância de Levenshtein entre duas strings
def levenshtein_distance(str1, str2):
    len_str1, len_str2 = len(str1), len(str2)
    matrix = [[0] * (len_str2 + 1) for _ in range(len_str1 + 1)]

    for i in range(len_str1 + 1):
        for j in range(len_str2 + 1):
            if i == 0:
                matrix[i][j] = j
            elif j == 0:
                matrix[i][j] = i
            elif str1[i - 1] == str2[j - 1]:
                matrix[i][j] = matrix[i - 1][j - 1]
            else:
                matrix[i][j] = 1 + min(matrix[i - 1][j],      # Deleção
                                       matrix[i][j - 1],      # Inserção
                                       matrix[i - 1][j - 1])  # Substituição

    return matrix[len_str1][len_str2]

Aqui, para um dado texto, buscamos uma palavra_chave, a uma distancia inferior ao limite_distancia. Em nosso exemplo, buscaremos frase a frase a palavra_chave: tesouros e com limite_distancia:1. Assim, poderemos obter frases com “tesouro”, “tesouros”, “tesouras”, “besouros” e assim por diante.

Se tivéssemos certeza da escrita, poderíamos colocar distância 0. Mas não é o caso.

def encontrar_frases_com_palavra_chave(texto, palavra_chave, limite_distancia):
    frases_com_palavra_chave = []

    for i, frase in enumerate(texto.split('.')):
        palavras_frase = frase.strip().lower().split()
        for palavra in palavras_frase:
            distancia = levenshtein_distance(palavra, palavra_chave.lower())

            if distancia <= limite_distancia:
                frases_com_palavra_chave.append((frase, i))
                break  # Apenas uma ocorrência por frase

    return frases_com_palavra_chave

No código abaixo abrimos o livro de acordo com o endereço informado (file_path, acima)

with open(file_path, 'rb') as file:
    pdf_reader = PyPDF2.PdfReader(file)
    num_paginas = len(pdf_reader.pages)
    texto_livro = ''

    for pagina_num in range(num_paginas):
        pagina = pdf_reader.pages[pagina_num]
        texto_livro += pagina.extract_text()

E aqui configuramos a busca, e a executamos.

# Palavra-chave e limite de distância
palavra_chave = "tesouros"
limite_distancia = 1

# Encontrando frases que contêm a palavra-chave com uma distância de Levenshtein específica
frases_com_palavra_chave = encontrar_frases_com_palavra_chave(texto_livro, palavra_chave, limite_distancia)

# Exibindo resultados
print(f"Frases que contêm a palavra '{palavra_chave}' com distância de Levenshtein {limite_distancia}:")
for frase, indice in frases_com_palavra_chave:
    print(f"Frase {indice + 1}: {frase.strip()}")
#    imprimir_contexto(texto_livro.split('.'), indice)
    print("\n")

Os resultados foram:

Frases que contêm a palavra ‘tesouros’ com distância de Levenshtein 1:

Frase 1772: Não me lembro se contei que havia na rocha uma vareta que uns piratas tinham posto ali fazia muitos e muitos anos para marcar o lugar de um tesouro enterrado

Frase 1773: As crianças tinham encontrado o reluzente tesouro e, quando estavam endiabradas, costumavam jogar chuvas de moedas de ouro e de prata e diamantes e pérolas para as gaivotas, que mergulhavam em busca de comida e se afastavam, furiosas com aquele golpe baixo

É importante notar que na primeira frase, que é onde está o que o pirata estava buscando, consta a palavra “tesouro” e não “tesouros”. Ou seja, se a distancia de Levenshtein fosse zero, a frase não seria encontrada (vale testar no colab).

Assim, nosso querido pirata descobriu que a indicação do tesouro era uma rocha com uma vareta, sem ter de ler o livro inteiro de novo :)

Links úteis:

Notebook em Python

Distância de Levenshtein