Недавно мне попалась задачка на поиск почти-дублей среди большого количества коротких текстов. Поиск готового решения не привел к успеху, а полученное решение оказалось довольно интересным, и я не смог отказать себе в удовольствии поделиться им.

Формулировка

Есть большая база текстов (сотни тысяч текстов). Длины текстов примерно одинаковые, около 250 символов, язык — английский. Некоторые из текстов отредактированы (исправлены опечатки, расставлены запятые и т.п.); таким образом в базе оказывается как оригинальный текст, так и его исправленная копия. Таких пар не очень много, скажем не более 1%. Задача: найти все такие пары.