Python compendio/hash de similitud de la cadena

Question

Busco un algoritmo que puede generar un corto (fx 16 caracteres (código hash no es importante)/digerir de una cadena más larga.

El requisito principal es que las cuerdas que es casi idéntica debe resultar en el mismo digesto

Fx 2 electrónico casi idéntica:..

Hola Martin ... Éstos son algunos de spam para usted Saludos XYZ => aaaa aaaa aaaa aaaa

.. Hola Bo. Aquí hay algunos ... correo no deseado para ti Saludos EFG. => aaaa aaaa aaaa aaaa

devuelve los mismos Diges (o casi el mismo), en tanto que 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 correo no deseado. El filtro recordará compendios de correos electrónicos que es seguro que son spam. Si el mismo resumen se muestra en los correos donde hay dudas, el resumen idéntico hará que el filtro aumente el spamscore.

Sé de Levenshtein, pero me exige conocer las cuerdas por adelantado. 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 compararlo con cada uno, lo que sería un proceso muy lento.

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

Cualquier puntero apreciado.

Answer 1

Parece que quiere locality-sensitive hashing. Considere usar minhash o shingling. Hay una gran explicación de ambos en Rajaraman & Ullman's book, Mining Massive Datasets. Encontrará numerosas implementaciones cortas en blogs de búsqueda de Python para las palabras clave anteriores.

Parece que hay otros métodos para esto (que no sé mucho sobre), pero que puede ser de interés para usted, ya que están especialmente adaptados para los mensajes de spam, en particular, el hash nilsimsa:

• explicó in that paper
• que tiene una python port on pypi