Contexto: ¿Por qué es necesaria esta técnica?

Durante el preprocesamiento de datos para el entrenamiento de modelos de lenguaje, surge un desafío crítico: identificar de manera eficiente textos repetitivos o muy similares dentro de conjuntos de datos masivos (del orden de miles de millones de registros). Los enfoques ingenuos, como el uso directo de conjuntos (set) en Python, colapsan por el consumo de memoria y, además, suelen requerir la detección de similitudes aproximadas, no solo coincidencias exactas.

Algoritmos como MinHash, combinados con Locality Sensitive Hashing (LSH), ofrecen una solución práctica para estimar la similitud entre documentos de forma rápida y escalable.

El concepto fundamental: Similitud de Jaccard

Para cuantificar la similitud entre dos conjuntos (por ejemplo, los n-gramas de dos documentos), se utiliza el índice de Jaccard. Dados dos conjuntos A y B, se define como:

Jaccard(A, B) = |A ∩ B| / |A ∪ B|

Un valor cercano a 1 indica alta similitud. Calcular esto de forma directa para todos los pares en un corpus gigante es computacionalmente inviable (complejidad O(n²)).

Funcionamiento básico de MinHash

MinHash es una técnica que permite aproximar la similitud de Jaccard de manera eficiente. Su proceso se resume en dos fases principales.

1. Tokenización mediante Shingles (n-gramas)

En lugar de usar palabras sueltas, se segmenta el texto en subcadenas consecutivas de longitud fija k (llamadas k-gramas o shingles). Por ejemplo, con k=3:

Documento: "aprendizaje profundo"
Shingles: {"apr", "pre", "ren", "end", "ndi", "dzi", "zia", "iaj", "aje", "eje", "aju", "jud", "udo"}

Este enfoque preserva parcialmente el orden de las palabras.

2. Firma mediante mínimos hash

Se utilizan múltiples funciones hash independientes (p. ej., 100). Para cada documento y cada función hash h_i, se calcula el valor hash de cada uno de sus shingles y se conserva únicamente el valor mínimo obtenido. El vector resultante (de longitud igual al número de funciones hash) constituye la firma MinHash del documento.

La propiedad fundamental es que la probaiblidad de que las firmas de dos documentos coincidan en una posición determinada es igual a su similitud de Jaccard. Comparando las firmas se puede estimar rápidamente la similitud.

Implementación de ejemplo en Python

El siguiente código ilustra una implementación sencilla de MinHash para estimar la similitud entre dos cadenas de texto.

import hashlib

def generar_shingles(texto, k=3):
    """Convierte el texto en un conjunto de k-gramas."""
    if len(texto) < k:
        return set()
    return {texto[i:i+k] for i in range(len(texto) - k + 1)}

def calcular_firma_minhash(conjunto_shingles, num_funciones=100):
    """Genera una firma MinHash para un conjunto de shingles."""
    firma = []
    for i in range(num_funciones):
        valor_minimo = float('inf')
        for shingle in conjunto_shingles:
            # Se genera un hash diferente para cada función usando una semilla 'i'
            datos_para_hash = (str(i) + shingle).encode('utf-8')
            hash_valor = int(hashlib.sha256(datos_para_hash).hexdigest(), 16)
            if hash_valor < valor_minimo:
                valor_minimo = hash_valor
        firma.append(valor_minimo)
    return firma

def estimar_similitud_jaccard(firma1, firma2):
    """Estima la similitud de Jaccard a partir de las firmas MinHash."""
    if len(firma1) != len(firma2):
        raise ValueError("Las firmas deben tener la misma longitud.")
    coincidencias = sum(1 for a, b in zip(firma1, firma2) if a == b)
    return coincidencias / len(firma1)

# Ejemplo de uso
texto_a = "la inteligencia artificial está avanzando"
texto_b = "la inteligencia artificial avanza muy rápido"

shingles_a = generar_shingles(texto_a)
shingles_b = generar_shingles(texto_b)

firma_a = calcular_firma_minhash(shingles_a)
firma_b = calcular_firma_minhash(shingles_b)

similitud_estimada = estimar_similitud_jaccard(firma_a, firma_b)
print(f"Similitud estimada por MinHash: {similitud_estimada:.3f}")

Consideraciones y lecciones aprendidas

• Número de funciones hash: Se requiere un número suficiente (típicamente 100-200) para obtener una estimación estable con baja varianza.
• Tamaño del shingle (k): Es un hiperparámetro clave. Para texto en español, k=3 suele funcionar. Un valor muy bajo (p. ej., 1) hace que documentos con las mismas palabras pero diferente orden sean idénticos. Un valor muy alto hace que documentos casi idénticos parezcan diferentes.
• Eficiencia de memoria: Aunque MinHash comprime la información, almacenar todas las firmas en memoria para miles de millones de documentos sigue siendo inviable. Aquí es donde entra en juego LSH, que usa las firmas para agrupar documentos candidatos a ser similares, reduciendo drásticamente los pares a comparar.

Aplicaciones adecuadas

MinHash es particularmente útil para:

• Deduplicación a gran escala de texto (documentos web, conjuntos de datos de entrenamiento).
• Detección de plagio basado en fragmentos.
• Sistemas de recomendación para encontrar ítems (texto) similares.

No es la herramienta adecuada si se necesita medir similitud semántica profunda (p. ej., paráfrasis). Para eso se requieren técnicas basadas en embeddings neuronales.

Conclusión

MinHash transforma el problema de comparar conjuntos grandes en el de comparar vectores cortos, intercambiando exactitud por eficiencia. Su combinación con LSH es una piedra angular en el preprocesamiento de datos para el entrenamiento de modelos a escala industrial, permitiendo identificar y filtrar duplicados y cuasi-duplicados de manera práctica.