Simhash или charikar's hash.
Используется в гугле для поиска похожих документов. Легко переделывается для строк (в качестве фич берутся не биграммы-токены, а биграммы-символы).
Подробный алгоритм
здесь.
Теоретическое обоснование – в статье «Similarity estimation techniques from rounding algorithms».
