El préstamo ilegal es una hidra de múltiples cabezas, un enemigo que cambia constantemente de rostro. Nuestros mejores investigadores privados están listos para aferrarse a cualquier crimen cometido por este enemigo. Sin embargo, el enemigo no duerme, es astuto y traicionero: obviamente sustituyendo en una cosa, increíblemente hábilmente barre las huellas en otras. A veces se las arregla para atrapar con las manos en la masa con la ayuda de nuestro empleado más ágil: Suffix Massiv . A veces el enemigo duda, y la búsqueda meticulosa pero pausada de paráfrasis logra calcular su ubicación. Pero el mal es insidioso, y constantemente necesitamos nuevas fuerzas para combatirlo .
Hoy hablaremos sobre nuestro nuevo detective especial llamado Fuzzy Search , así como sobre su primer encuentro con préstamos borrosos.
Con su agencia de detectives Antiplagiarism , prepárese para el caso Mysterious Opponent
Fuente de la imagen: pxhere.comEscena
Al verificar el área (documento), el Anti-Plagio verifica si hay alguna llamada sobre un posible delito en el área. Los testigos que nos señalarán el crimen son el Índice de herpes zóster .
"Una teja es un texto de unas pocas palabras de tamaño". Cada pieza de este tipo está en hash, y los documentos que tienen tejas con los mismos hashes que en el documento que se verifica se buscan en el índice.
Un testigo presencial, al ver una coincidencia en el hash de dos tejas, nos llama con un mensaje sobre el crimen. Desafortunadamente, el índice de herpes zóster no puede ser castigado por una llamada falsa, es inmune a las sanciones, razón por la cual hay muchas llamadas. La agencia determina los documentos con la mayor acumulación de tales llamadas: la escena de un posible crimen.
InterludioA pesar del hecho de que en el contexto de la historia llamamos delitos a los fondos prestados, en realidad el dinero prestado puede ser legítimo o puede ser causado por falsos positivos. Aunque el Antilpagiate puede extraer citas, el revisor debe tomar la decisión final.
Primera pista
Ahora eres un detective, hijo.
De ahora en adelante tienes prohibido creer en las coincidencias.
© "The Dark Knight: Revival of the Legend" ("The Dark Knight Rises", dir. K. Nolan, 2012).
El Detective Fuzzy Search llegó a la escena del crimen. Los delincuentes lo suficientemente grandes no pasan desapercibidos, porque cuanto mayor sea la escala del crimen, más probable es que dejen una pista. Para Fuzzy Search, estos leads son coincidencias cortas de una longitud fija. Parece que a nuestro detective le falta una gran cantidad de rastros de delincuentes, pero solo el 5% de los atacantes no dejan esa pista. Es importante no perder criminales, por lo que el detective escanea rápidamente el área utilizando una técnica especial para detectar coincidencias.
El diario del detective sobre el método de trabajo. Primera etapa
Utilizaremos dos características de la tarea:
- Estamos interesados en duplicados claros de una longitud fija.
- En un buen documento, la misma teja no se duplica muchas veces.
La segunda condición es necesaria para limitar el número de duplicados claros encontrados. De hecho, un sencillo que ocurra 1000 veces en el documento y en la fuente dará 1,000,000 de pares de coincidencias. Estas tejas repetidas con frecuencia solo se pueden ver en documentos sin limpiar con intentos de rastreo.
Un documento despejado de rastreos se presenta como una secuencia de palabras. Llevamos las palabras a la forma normal de las palabras y luego las procesamos en hash. Obtenemos una secuencia de enteros (en el gif, una secuencia de letras). Todas las tejas de esta secuencia se numeran y se ingresan en la tabla hash con el valor de la posición del comienzo de la subcadena. Luego, para cada tabla en el documento candidato, las coincidencias se encuentran en la tabla hash. Esto crea duplicados claros de una longitud fija. Las pruebas muestran una aceleración triple cuando se utiliza el nuevo método en comparación con la matriz de sufijos.
ObservaciónTenga en cuenta que, a diferencia de la matriz de sufijos, que encuentra todos los duplicados máximos (no expandibles), encontramos todos los duplicados de una longitud fija . Esto es un poco peor, pero de todos modos necesita distribuir duplicados, pero dicha búsqueda consume menos recursos y es más fácil de entender / implementar. Bonificación: puede limitar el número de grabaciones de un duplicado repetido con frecuencia, lo que ayudará a mantener la linealidad en documentos gigantes.
Calculamos el criminal
- ¿Hay otros puntos a los que me aconsejes que preste atención?
"El extraño comportamiento del perro en la noche del crimen".
- perros? ¡Pero ella no se comportó de ninguna manera!
"Eso es extraño", dijo Holmes.
© Arthur Conan-Doyle, "Silver" (de la serie "Notas sobre Sherlock Holmes")
Entonces, Fuzzy Search encontró varias pistas para identificar criminales. Nuestro héroe usa sus habilidades deductivas al máximo, para restaurar, poco a poco, gradualmente la imagen del criminal de acuerdo con las pistas encontradas. El detective está ampliando gradualmente la imagen de lo que está sucediendo, completándola con nuevos detalles, descubriendo más y más evidencia hasta que esta imagen finalmente se complete. A veces traen a nuestro detective, y tiene que bajarlo del cielo a la tierra y convencerlo de que necesitamos la identidad del criminal y no la biografía de su primo. Fuzzy Search se queja, pero humildemente reduce la imagen a la escala deseada.
El diario del detective sobre el método de trabajo. Segunda etapa
Fuente de la imagen: pixabay.com
La segunda etapa distribuye duplicados a izquierda y derecha en todo el documento. La distribución proviene de los "centros": se encuentran duplicados claros. Para comparar los sufijos, utilizamos la distancia de Levenshtein : el número mínimo de eliminaciones / reemplazos / inserciones de palabras necesarias para llevar una línea a otra. La distancia se puede calcular dinámicamente para sufijos duplicados utilizando el algoritmo de Wagner-Fisher , basado en la determinación recursiva de la distancia de Levenshtein. Sin embargo, este algoritmo es de complejidad cuadrática y no permite controlar la proporción de errores. Otro problema es la definición exacta de los límites de los duplicados. Para abordar estos problemas, utilizamos varios procedimientos directos pero efectivos.
En este paso, se propone primero completar secuencialmente la Matriz de distancia de Levenshtein para sufijos duplicados difusos (luego, de manera similar, para prefijos). Como verificamos los sufijos para "similitud", solo nos interesan los valores cercanos a la diagonal de esta matriz (la distancia de Levenshtein es mayor o igual que la diferencia en las longitudes de línea). Esto permite la complejidad lineal. Una vez establecida la distancia máxima permitida de Levenshtein, completaremos la tabla hasta encontrar una columna con valores mayores que los permitidos. Dicha columna indica que nuestro duplicado difuso ha terminado recientemente y las palabras coincidieron casi por completo. Habiendo guardado el óptimo anterior para cada celda llena, descendemos de la celda con una penalización mínima en la columna crítica hasta que encontremos varias coincidencias, después de lo cual el error comenzó a aumentar bruscamente. Estos serán los límites del duplicado difuso encontrado.
Además, para que los errores no se acumulen, se introduce un procedimiento que restablece el número de errores, comenzando la propagación nuevamente si nos topamos con una "isla" de sucesivas coincidencias.
Pandillas de delincuentes
- ¡Mañana planeamos reunirnos con compañeros de clase!
- En un gran compañero de clase?
- que?
© Bashorg
La búsqueda difusa ha seguido siendo una tarea simple: unir a los delincuentes atrapados en el mismo lugar en pandillas, justificar a los sospechosos inocentes y reunir los resultados.
Fuente de la imagen: pixabay.com
Pegar duplicados inmediatamente resuelve 3 problemas. En primer lugar, la segunda etapa de "distribución de duplicados" absorbe modificaciones de palabras y frases, pero no oraciones completas. Si aumenta la "capacidad de propagación" del algoritmo, comenzará a extenderse sobre las coincidencias encontradas a una distancia demasiado grande, y los límites de los duplicados se determinarán peor. Entonces perdemos la precisión tan importante para nosotros, que tenía una búsqueda clara.
En segundo lugar, la segunda etapa no reconoce la permutación de dos duplicados. Me gustaría que la permutación de las dos oraciones en algunos lugares forme una frase cercana al original, pero para una línea de caracteres únicos, la permutación del prefijo y el sufijo en algunos lugares conduce a la línea que está lo más lejos posible del original (en la métrica de Levenshtein). Resulta que la segunda etapa, al reorganizar las oraciones, encuentra dos duplicados ubicados uno al lado del otro que desea combinar en uno.
Y la tercera razón es Granularidad, o Granularidad. La granularidad es una métrica que determina el número promedio de duplicados encontrados en un préstamo real que encontramos. En otras palabras, la granularidad muestra qué tan bien encontramos el préstamo completo en lugar de las pocas partes que lo cubren. La definición formal de granularidad, así como la definición de precisión e integridad micro-promedio, se pueden encontrar en el artículo "Un marco de evaluación para la detección de plagio" .
Gifka muestra que a veces solo se pueden pegar dos duplicados después de que uno de ellos se adhiere al tercer duplicado. En consecuencia, solo una pasada de izquierda a derecha en el documento no funciona para completar el pegado.
AlgoritmoLa lista de duplicados en la entrada se ordena por el borde izquierdo del documento.
Estamos tratando de pegar el duplicado actual con varios de los candidatos más cercanos frente a él.
Si resulta, intente pegarlo nuevamente, si no, vaya al siguiente duplicado.
Dado que el número de duplicados no es mayor que la longitud del documento, y cada doble verificación reduce el número de duplicados en 1 y se realiza en tiempo constante, la complejidad de este algoritmo es O (n).
Como regla general, se usa un conjunto de varios parámetros para pegar duplicados, pero si nos olvidamos de la microoptimización de la calidad, pegaremos esos duplicados para los cuales la distancia máxima en el documento y la fuente es bastante pequeña.
La localidad de pegado proporciona O (1) duplicados, a los cuales se puede pegar el duplicado actual.
Entrenamiento para principiantes
El detective necesitaba adaptarse a las características de nuestra ciudad, adaptarse al terreno, dar un paseo por las calles poco conocidas y conocer mejor a sus habitantes. Para esto, un principiante toma un curso de entrenamiento especial en el que estudia situaciones similares en un campo de entrenamiento. El detective en la práctica estudia las pistas, la deducción y la construcción de lazos sociales para la captura más efectiva de delincuentes.
El modelo paramétrico necesitaba ser optimizado. Para determinar los parámetros óptimos del modelo, se utilizó la muestra PlagEvalRus .
La muestra se divide en 4 colecciones:
- Generated_Copypast (4250 pares) - préstamos generados literalmente
- Generated_Paraphrased (4250 pares): préstamos modificados débilmente y medianos generados por la máquina utilizando el ruido de los pasajes originales (reemplazos / supresiones / inserciones arbitrarias)
- Manually_Paraphrased (713 pares) Textos escritos a mano con varios tipos de préstamos, en su mayoría préstamos endeudados y de modificación media (reemplazados por no más del 30% de las palabras en el duplicado)
- Manually_Paraphrased 2 (198 pares) Textos escritos a mano con préstamos medianos y altamente modificados (más del 30% de palabras)
La muestra también contiene el tipo de cada préstamo.- DEL - Eliminar palabras individuales (hasta 20%) de la oración original.
- AGREGAR - Agregue palabras individuales (hasta 20%) a la oración original.
- LPR - Cambio de formas (cambio en el número, caso, forma y tiempo de un verbo, etc.) de palabras individuales (hasta 30%) de la oración original.
- SHF: cambiar el orden de las palabras o partes de una oración (giros, partes de una oración simple como parte de un complejo) sin cambios significativos "dentro" de las partes reorganizadas.
- CCT: pegue dos o más oraciones del texto de origen en una oración.
- SEP / SSP: dividir la oración compleja inicial en dos o más oraciones independientes (posiblemente con un cambio en el orden de su secuencia en el texto).
- SYN - Reemplazar palabras individuales o términos individuales con sinónimos (por ejemplo, "sal" - "cloruro de sodio"), reemplazar abreviaturas con sus desciframientos completos y viceversa, revelar las iniciales de su nombre completo y viceversa, reemplazar el primer nombre con las iniciales, etc.
- HPR: procesamiento sólido de la oración original, que es una combinación de muchos (3-5 o más) tipos de modificaciones de texto anteriores. El mismo tipo supone un fuerte cambio en el texto de origen por la frase periférica usando expresiones idiomáticas, construcciones sinónimos complejas, permutación de palabras o partes de una oración compleja, etc. trucos que en conjunto dificultan determinar la correspondencia entre la fuente original y el texto alterado.
La búsqueda de los parámetros óptimos del modelo se llevó a cabo utilizando el método de descenso de arranque múltiple. Maximizado medir con (énfasis en la precisión). Aquí están los parámetros óptimos más significativos.
Historia del caso
El período de prueba de nuestra Búsqueda difusa ha llegado a su fin. Comparemos su productividad con la de otro detective, la matriz de sufijos. El curso de capacitación Fuzzy Search se realizó en el programa Manually_Paraphrased.
En el campo, el recién llegado mostró una superioridad significativa en la proporción de casos resueltos. La velocidad de su trabajo tampoco puede sino alegrarse. Nuestra agencia carecía de un empleado tan valioso.
Al comparar la calidad del modelo con la matriz de sufijos, notamos una mejora significativa en la granularidad, así como una mejor detección de préstamos medianos y altamente modificados.
Al probar documentos de hasta 10 7 palabras de tamaño, verificamos la linealidad de ambos algoritmos. En el procesador i5-4460, el programa procesa un par de "fuente de documentos" de un millón de palabras en menos de un segundo.
Habiendo generado textos con una gran cantidad de préstamos, estamos convencidos de que la búsqueda difusa (línea azul) no es más lenta que la matriz de sufijos (línea roja). Por el contrario, una matriz de sufijo sufre en documentos grandes debido a demasiados duplicados. Comparamos el rendimiento con una longitud mínima duplicada de 5 palabras. Pero para una cobertura de préstamo suficiente, utilizamos una búsqueda clara con una longitud mínima duplicada de 3 palabras, que en documentos gigantescos conduce a una caída significativa en la productividad (línea naranja). Vale la pena señalar que los documentos ordinarios contienen menos préstamos, y en la práctica este efecto es mucho menos pronunciado. Pero tal experimento nos permite comprender la expansión de la aplicabilidad de los modelos con una nueva búsqueda difusa.
Ejemplos:
Se puede ver que el algoritmo, a pesar de la pequeña complejidad computacional, hace frente a la detección de reemplazos / eliminaciones / inserciones, y el tercer paso le permite detectar préstamos con la permutación de oraciones y sus partes.
Epílogo
Fuzzy Search trabaja en equipo con nuestras otras herramientas: Búsqueda rápida de documentos candidatos, Extracción de formato de documentos, Captura a gran escala de intentos de omisión. Este comando le permite encontrar rápidamente plagio potencial. Fuzzy Search se ha arraigado en este equipo y realiza sus funciones de búsqueda de forma más cualitativa y, lo que es más importante, más rápido que la matriz de sufijos. Nuestra agencia se encargará aún mejor de sus tareas, y los autores inescrupulosos encontrarán nuevos problemas cuando usen texto no original .
¡Crea con tu propia mente!