Otro enfoque es Minhashing (cubierto en el Capítulo 3 de Minería de conjuntos de datos masivos). Construye un conjunto de n-gramos de cada cadena y toma sus hashes (enteros). El minhash es el valor mínimo de hash. Dado que necesita un conjunto de valores minhash para representar cada cadena, para cada valor minhash, XOR el entero se divide con un entero aleatorio, luego toma el mínimo de eso. Usted hace esto para cada cadena, luego compara la superposición entre las firmas minhash (o bandas de firmas minhash) usando algo similar a Jaccard.
Una alternativa para comparar cada cadena con todas las demás es construir una matriz de similitud y llenar cada elemento con la similitud de Jaccard entre las firmas minhash. Esto es aproximadamente O (n ^ 2/2) para escribir desde sim (a, b) == sim (b, a) y sim (a, a) == 1. La búsqueda es O (1).
Otra alternativa (O (1) para escribir y leer) es escribir los minhashes en algún tipo de índice: he usado Lucene para esto, donde los elementos de la firma minhash se escriben en campos indexables de valores múltiples. Buscar cadenas similares a la actual es hacer una consulta OR para todos los minhashes para el documento de consulta. Los resultados se clasificarán primero por los documentos de mayor correspondencia. Si necesita cortar en algún grado de superposición, deberá verificar manualmente la similitud de los primeros con su consulta.
- Cómo detectar imágenes en un documento de Word escaneado
- Cómo recorrer un trabajo de búsqueda binaria e imprimirlo en orden
- En el algoritmo EM, ¿debería aumentar el valor de la función objetivo a través de cada M-STEP?
- ¿Cómo podemos revertir una pila usando solo las operaciones push () y pop () sin usar ningún DS secundario?
- ¿Cuál es la diferencia entre árboles binarios completos y completos?
