Python дайджест / хэш для сходства строк

Question

Я ищу алгоритм, который может генерировать короткий (например, 16 символов (не важно)) хэш-код / ​​дайджест из более длинной строки.

Основным требованием является то, что строки, которые почти идентичны, должны приводить ктот же дайджест.

Fx 2 почти идентичная почта:

Привет, Мартин. Вот тебе ... спам. С уважением. XYZ. => AAAA AAAA AAAA AAAA

Привет Бо. Вот некоторые ... спам для вас. С уважением EFG. => AAAA AAAA AAAA AAAA

возвращает те же цифры (или почти одинаковые), где в качестве другой почты:

Здравствуйте, Финн. Это тестовое письмо. => CCCC CCCC CCCC CCCC

вернет другой дайджест.

Этот алгоритм будет частью фильтра спама. Фильтр запоминает дайджесты изписьма, которые наверняка являются спамом. Если тот же дайджест обнаруживается в письмах, в которых он вызывает сомнения, идентичный дайджест вызовет увеличение спама в фильтре.

Я знаю о Левенштейне, но он требует от менязнать строки впереди.В этой ситуации у меня нет этой информации.Я мог бы иметь эту информацию, но для этого потребовался бы фильтр для хранения всей спам-почты и проверки каждого из них, что было бы очень медленным процессом.

Может быть, какой-то свободный алгоритм сжатия в сочетании с вычислениемЛевенштейновское расстояние между ними может сработать.

Любые указатели оценены.

Answer 1

Похоже, вы хотите хеширование с учетом локальных условий .Попробуйте использовать minhash или shingling.В книге Раджарамана и Уллмана есть отличное объяснение: Mining Massive Datasets .Вы найдете множество коротких реализаций в блогах по поиску Python по ключевым словам выше.

Кажется, есть и другие подходы к этому (о которых я не знаю много), но это может вас заинтересоватьпоскольку они специально созданы для спам-сообщений, в частности хеша nilsimsa:

• объяснено в этой статье
• , которая имеет порт python на pypi