Python digest / hash para similitud de cuerdas

Estoy buscando un algoritmo que pueda generar un código hash corto (fx 16 caracteres (no importante) de una cadena más larga.

El requisito principal es que las cadenas que son casi idénticas deberían dar como resultado el mismo compendio.

Fx 2 correo casi idéntico:

Hola martin. Aquí hay algunos … spam para ti. Saludos XYZ. => AAAA AAAA AAAA AAAA

Hola bo Aquí hay algunos … spam para ti. Saludos EFG. => AAAA AAAA AAAA AAAA

devuelve las mismas excavaciones (o casi las mismas), donde como un correo diferente:

Hola finn Este es un correo de prueba. => CCCC CCCC CCCC CCCC

devolverá un resumen diferente.

Este algoritmo sería parte de un filtro de spam. El filtro recordará los resúmenes de los correos, lo que es seguro es spam. Si aparece el mismo resumen en los correos donde está en duda, el resumen idéntico hará que el filtro aumente la puntuación de spam.

Sé de Levenshtein, pero me obliga a conocer las cuerdas que están al frente. En esta situación no tengo esta información. Podría tener esta información, pero eso requeriría el filtro para almacenar todo el correo electrónico no deseado y compararlos con cada uno, lo que sería un proceso muy lento.

Tal vez podría funcionar algún algoritmo de compresión suelto junto con un cálculo de la distancia Levenshtein entre los dos.

Cualquier puntero apreciado.

Parece que quieres hashing sensible a la localidad . Considere el uso de minhash o shingling . Hay una gran explicación de ambos en el libro de Rajatwign y Ullman, Mining Massive Datasets . Encontrará numerosas implementaciones cortas en los blogs de búsqueda de Python para las palabras clave anteriores.

Parece que hay otros enfoques para esto (de los que no sé mucho), pero eso puede ser de su interés, ya que están especialmente diseñados para mensajes de spam, en particular el hash nilsimsa:

  • explicado en ese papel
  • que tiene un puerto de python en pypi