Me gustaría hacer coincidir aproximadamente las cadenas usando el hashing sensible a la localidad. Tengo muchas cadenas> 10M que pueden contener errores tipográficos. Para cada Cadena, me gustaría hacer una comparación con todas las otras cadenas y seleccionar aquellas con una distancia de edición de acuerdo con algún umbral.

Es decir, la solución ingenua requiere comparaciones O (n ^ 2). Para evitar ese problema, estaba pensando en usar Hashing sensible a la localidad. Luego, cerca de cadenas similares darían como resultado los mismos cubos y solo necesito hacer una búsqueda interna de cubos. Entonces es O (n * C) donde C es el tamaño del cubo.

Sin embargo, no entiendo cómo representar las cadenas. Si fuera texto, lo representaría en el espacio vectorial. Mi pregunta principal es si esto es manejable usando LSH y luego una representación vectorial adecuada de la cadena.

¿Puedo usar una biblioteca ya implementada para esta tarea? ¿o depende de mi problema, así que debo implementarlo yo mismo? ¿Hay algún paquete de Python que haga esto?