Я хотел бы приблизительно сопоставить строки с использованием хеширования, чувствительного к локальности. У меня есть много строк> 10M, которые могут содержать опечатки. Для каждой строки я хотел бы сравнить все остальные строки и выбрать те, у которых расстояние редактирования соответствует некоторому порогу.

То есть наивное решение требует O (n ^ 2) сравнений. Чтобы избежать этой проблемы, я подумал об использовании хеширования с учетом локальных особенностей. Тогда почти одинаковые строки приведут к одним и тем же сегментам, и мне нужно делать только поиск по сегментам. Так что это O (n * C), где C - размер корзины.

Тем не менее, я не понимаю, как представлять строки. Если бы это был текст, я бы представлял его в векторном пространстве. Мой главный вопрос: можно ли это использовать с помощью LSH, а затем с помощью соответствующего векторного представления строки.

Могу ли я использовать уже реализованную библиотеку для этой задачи? или это зависит от моей проблемы, поэтому я должен реализовать это сам? Есть ли пакет Python, который делает это?