Tengo una base de datos de 350,000 cadenas con una longitud promedio de alrededor de 500 . Las cadenas no están formadas por palabras, son esencialmente una variedad aleatoria de caracteres.
Necesito asegurarme de que ninguna de las cadenas sea demasiado similar, donde la similitud se define como la distancia de edición dividida por la longitud promedio de la cadena . La división se debe a que las distancias de edición más pequeñas son más aceptables para cadenas más pequeñas. Está bien si se utiliza una métrica diferente por motivos de rendimiento, pero la distancia de edición es la métrica de referencia preferida.
Ingenuamente, calculamos la distancia de edición con el tiempo de ejecución O(a*b) , donde a,b son la longitud de las dos cadenas. Hacemos esto para todos los n^2 pares, lo que da un tiempo de ejecución general de O(n^2*a*b) , claramente demasiado grande con n=350,000, a,b=500 .
La base de datos tiene la forma de una lista de Python leída de un archivo csv. Me gustaría procesarlo de forma pitónica, si es posible.
¿Cómo se puede acelerar esto? No estoy seguro de cuánto tardará en finalizar el algoritmo ingenuo (del orden de semanas), pero lo ideal sería que tardara menos de un día en ejecutarse.
Escribí un prototipo muy breve de un algoritmo hash sensible a la localidad simple en python. Sin embargo, hay algunas advertencias y es posible que también desee optimizar algunas piezas. Los mencionaré cuando los veamos.
Suponga que todas sus cadenas están almacenadas en strings .
import random from collections import Counter MAX_LENGTH = 500 SAMPLING_LENGTH = 10 def bit_sampling(string, indices): return ''.join([string[i] if i<len(string) else ' ' for i in indices]) indices = random.sample(range(MAX_LENGTH),SAMPLING_LENGTH) hashes = [bit_sampling(string, indices) for string in strings] counter = Counter(hashes) most_common, count = counter.most_common()[0] while count > 1: dup_indices = [i for i, x in enumerate(hashes) if x == most_common] # You can use dup_indices to check the edit distance for original groups here. counter.pop(most_common) most_common, count = counter.most_common()[0] En primer lugar, esta es una ligera variante de muestreo de bits que funciona mejor para la distancia de hamming general. Idealmente, si todas sus cuerdas tienen la misma longitud, esto puede dar un límite de probabilidad teórico para la distancia de hamming. Cuando la distancia de hamming entre dos cuerdas es pequeña, es muy poco probable que tengan un hash diferente. Esto se puede especificar mediante el parámetro SAMPLING_LENGTH . Un SAMPLING_LENGTH más grande hará que sea más probable convertir una cadena similar en un hash diferente, pero también reducirá la probabilidad de convertir una cadena no muy similar en el mismo hash. Para la distancia de hamming, puede calcular esta compensación fácilmente.
Ejecutar este fragmento varias veces puede aumentar su confianza en cadenas no similares, ya que cada vez probará diferentes lugares.
Para adaptarse a su propósito de comparar cadenas de diferentes longitudes, un enfoque posible es dejar espacio de relleno en cadenas más cortas y hacer copias de ellas.
Aunque todas las operaciones en este fragmento son lineales (O(n)), aún puede consumir una cantidad significativa de memoria y tiempo de ejecución y es posible reducir un factor constante.
También es posible que desee considerar el uso de un algoritmo hash sensible a la localidad más complicado, como el que se muestra aquí: https://arxiv.org/pdf/1408.2927.pdf