Python Digest/hash dla podobieństwa ciąg

Question

Szukam algorytmu, który może generować krótkie (fx 16 znaków (nie ważne) hashcode/strawić od dłuższego łańcucha.

Głównym wymogiem jest to, że struny, która jest niemal identyczny powinno skutkować tym samym trawienie

Fx 2 prawie identyczne mail:..

Cześć Martin Oto kilka ... spam dla Ciebie Pozdrawiam XYZ => AAAA AAAA AAAA AAAA

.. Cześć Bo, oto kilka ... spam dla ciebie. Pozdrawiam EFG. => AAAA AAAA AAAA AAAA

zwraca te same Diges (lub prawie tak samo), gdzie jako inny mail:

Witam Finn. To jest wiadomość testowa. => CCCC CCCC CCCC CCCC

zwróci inny skrót.

Algorytm ten byłby częścią filtru antyspamowego. Filtr zapamiętuje streszczenia z wiadomości e-mail, które z pewnością są spamem. Jeśli ten sam skrót pojawia się w wiadomościach, w których jest wątpliwość, to samo podsumowanie spowoduje, że filtr zwiększy ilość spamu.

Wiem o Levenshtein, ale wymaga to ode mnie znajomości strun z góry. W tej sytuacji nie mam tych informacji. Mógłbym mieć te informacje, ale wymagałoby to filtra do przechowywania wszystkich spamowych wiadomości e-mail i sprawdzania ich pod każdym względem, co byłoby bardzo powolnym procesem.

Być może jakiś luźny algorytm kompresji w połączeniu z calc odległości Levenshteina między tymi dwoma może zadziałać.

Wszelkie wskazówki są mile widziane.

Answer 1

Wygląda na to, że chcesz locality-sensitive hashing. Rozważ użycie minhash lub shingling. Istnieje wspaniałe wytłumaczenie zarówno w książce Rajaraman & Ullmana, Mining Massive Datasets. Znajdziesz wiele, krótkich implementacji w blogach python wyszukiwania dla słów kluczowych powyżej.

Wydaje się, że inne podejście do tego (to nie wiem zbyt wiele o), ale które mogą być interesujące dla Ciebie, ponieważ są one specjalnie dostosowane do spamu, zwłaszcza hash nilsimsa:

• wyjaśnił in that paper
• który ma python port on pypi