¿Cómo comprueba Simhash si hay texto duplicado?
Comprobación de duplicación aproximada de páginas web a gran escala
Traducido principalmente de la detección de WWW07 de duplicación aproximada del rastreo de páginas web.
Existe una gran cantidad de páginas web con contenidos similares en la WWW. Para los motores de búsqueda, eliminar páginas web similares puede mejorar la eficiencia de la recuperación y reducir la sobrecarga de almacenamiento.
Cuando un rastreador rastrea una página web, debe poder descubrir rápidamente si hay páginas duplicadas en un conjunto de texto masivo.
Este artículo tiene dos contribuciones principales:
1. Esto muestra que simhash se puede utilizar para comprobar la duplicación de textos masivos.
2. Se propone un algoritmo que sea factible en aplicaciones prácticas.
Algoritmo Simhash
Después de extraer el contenido del texto, después de un preprocesamiento básico, como eliminar palabras vacías, reducir raíces e incluso bloquear, finalmente se puede obtener un vector.
Realice una conversión de algoritmo hash en cada $term para obtener un código hash con una longitud de f bits. El valor de 1-0 en cada bit se convierte en un peso positivo y negativo. Por ejemplo, cuando el bit de f1 es 1, el peso se establece en peso y cuando el bit de FK es 0, el peso se establece en -peso.
Sume los vectores de peso convertidos de todos los términos $ en el texto hablado de acuerdo con los bits correspondientes de F y finalmente obtenga una matriz de pesos de bits F. Si el bit es positivo, se establece en 1, si el bit es negativo, se establece en 0 y luego el texto se convierte en una nueva matriz de bits F 1-0, que es un nuevo código hash.
Simhash tiene dos "propiedades en conflicto":
1. Es un método de hash
2. El texto similar tiene un valor de hash similar. Si el simhash de dos textos es más cercano, es decir, cuanto menor es la distancia de Hamming, más similares son los textos.
Por lo tanto, cómo determinar rápidamente si hay una huella digital con una pequeña distancia de Hamming en un simhash masivo mediante el bit de conversión de tarea de verificación de duplicación en un texto masivo.
Es decir, entre n huellas dactilares de f bits, busque huellas cuya distancia de Hamming sea inferior a k.
En el experimento del artículo (ver al final), simhash utilizó una función hash de 64 bits. La distancia de Hamming = 3 es perfecta en la escala de 8 mil millones de páginas web.
Por lo tanto, los f bits de la tarea = 64, k = 3, n = 8 * 10 11.
La tarea es clara, veamos primero dos métodos muy intuitivos:
1. Enumerar todas las huellas dactilares simhash con una distancia de Hamming inferior a 3 y consultar cada una de los 8 mil millones de huellas dactilares ordenadas. huella dactilar.
(Este método requiere la huella digital simhash de la palabra C (64, 3) = 465438 C (64) y luego consulta cada palabra).
2. están todos ordenados juntos, hasta 41664, lo que requiere un gran espacio.
El método propuesto se encuentra en algún punto intermedio y es un compromiso razonable entre espacio y tiempo.
Supongamos que tenemos un conjunto de huellas dactilares 2d de bits f ordenadas. Mire los bits de alta d de cada huella digital. Los bits altos y bajos tienen las siguientes propiedades: Aunque hay muchas combinaciones de bits 2d, sólo hay unas pocas repeticiones en los bits D altos.
Ahora encuentre un número d' que esté cerca de d. Debido a que toda la lista está ordenada, una búsqueda puede encontrar el conjunto de huellas digitales f' que tiene el mismo bit d' alto que la huella digital objetivo f, porque d' está muy cerca de d, por lo que el conjunto f' encontrado no será muy grande.
Finalmente, es muy rápido encontrar huellas dactilares entre F y F con distancia de Hamming k en el conjunto F'.
La idea general: primero reduzca el conjunto de búsqueda y luego busque la distancia de Hamming de la posición f-d' en el conjunto pequeño.
Según el ejemplo, hay 2^34 páginas de 8 mil millones, por lo que, en teoría, 34 bits pueden representar 8 mil millones de huellas dactilares únicas.
Asumimos que los primeros 34 dígitos representan 8 mil millones de huellas dactilares, y los primeros 30 dígitos de las huellas dactilares son iguales, entonces los últimos 4 dígitos también pueden representar 24 huellas dactilares. Solo necesitamos comparar si Hamming. La distancia de estas 16 huellas dactilares es inferior a 3.
Hipótesis: Puedes hacer esto para 30 de 34 bits.
Por lo tanto, en una búsqueda completa, los primeros q bits deben coincidir exactamente (suponiendo que estas huellas digitales estén en q orden, puede usar el método de búsqueda binaria, y si el número de huellas digitales es muy grande y está distribuida uniformemente , incluso puede usar la búsqueda por interpolación), es necesario comparar los 64 bits restantes de la huella digital 2d-q posterior y la distancia de Hamming es inferior a 3.
Entonces la pregunta es cómo interceptar q de 64 bits.
Dividimos los 64 bits en varias partes, como por ejemplo ABCD 4 partes, cada una con 16 bits.
Suponiendo que estas huellas dactilares se han ordenado según la parte A, primero hacemos coincidir con precisión los 16 bits de A con un intervalo y verificamos si la distancia de Hamming después de los bits BCD de este intervalo es inferior a 3.
Bajo el mismo supuesto, en segundo lugar, hacemos coincidir con precisión otro intervalo basado en los 16 bits de b. Todas las huellas digitales en este intervalo deben compararse si la distancia de Hamming en el bit ACD es menor que 3.
Del mismo modo, están C y d.
Entonces aquí necesitamos hacer 4 copias de todas las huellas dactilares T, T1 T2 T3 T4, T1 está ordenada por A, T2 está ordenada por B... Se pueden consultar 4 copias en paralelo y los resultados finalmente se fusionan. De esta manera, incluso en el peor de los casos, no se perderán tres dígitos que caigan en tres áreas, ABC, ACD, BCD, ABD...
Solo hay 16 dígitos para una coincidencia exacta. La cantidad de huellas dactilares que deben compararse una por una sigue siendo enorme, posiblemente llegando a 2d-16.
Por ejemplo, divide 64 bits en 4 partes de ABCD, cada parte tiene 16 bits. En los 48 bits de BCD, lo dividimos en 4 partes, WXZY, cada parte tiene 12 bits. Los 3 bits de la distancia de Hamming se pueden distribuir entre tres partes cualesquiera, por lo que cualquiera de A y WXZY se puede combinar en exactamente 28 bits... las 3 partes restantes se utilizan para verificar la distancia de Hamming. Del mismo modo, también se pueden utilizar B, C y D. Luego, es necesario copiar T 16 veces y la combinación de ABCD y WXYZ coincide con precisión. Después de cada coincidencia exacta, el número de comparaciones requeridas se reduce a 2d-28. Las diferentes combinaciones son compensaciones en el tiempo y el espacio.
El peor de los casos es que tres de ellos pueden tener 1 bit y la diferencia en la distancia de Hamming es 1.
El algoritmo se describe a continuación:
1) Primero, copie la tabla original T en copias Tt: T1, T2,...TT.
2) Cada Ti está asociado con un pi y un πi, donde pi es un número entero y πi es una función de permutación, que se encarga de cambiar el bit pi a un bit alto.
3) Aplique la función de permutación πi a la tabla Ti correspondiente y luego ordene Ti.
4) Luego, realice las siguientes operaciones para cada Ti, la huella digital f que se va a comparar y la distancia de Hamming k:
a) Luego use los bits pi altos de F' para buscar y encontrar el mismo conjunto de bits de pi alto en Ti.
b) Compare los bits f-pi en el conjunto recuperado y encuentre las huellas dactilares cuya distancia de Hamming sea menor o igual a k. 5) Finalmente, combine los resultados de la búsqueda en todos los Ti.