L'emprunt illégal est une hydre à plusieurs têtes, un ennemi qui change constamment de visage. Nos meilleurs enquêteurs privés sont prêts à s'accrocher à tout crime commis par cet ennemi. Cependant, l'ennemi ne dort pas, il est rusé et perfide: se substituant évidemment à une chose, il balaie incroyablement habilement les traces des autres. Parfois, il parvient à attraper en flagrant délit avec l'aide de notre employé le plus agile - Suffix Massiv . Parfois, l'ennemi hésite, et la recherche minutieuse mais tranquille de Paraphrase parvient à calculer sa position. Mais le mal est insidieux et nous avons constamment besoin de nouvelles forces pour le combattre .
Aujourd'hui, nous parlerons de notre nouveau détective spécial nommé Fuzzy Search , ainsi que de sa première rencontre avec des emprunts flous.
Avec votre agence de détective Antiplagiat , préparez- vous à l'affaire Mysterious Opponent
Source de l'image: pxhere.comScène
Lors de la vérification de la zone (document), l' anti-plagiat vérifie s'il y a des appels concernant un crime possible dans la zone. Les témoins oculaires qui nous signaleront le crime sont le Shingles Index .
"Un bardeau est un morceau de texte de quelques mots." Chacune de ces pièces est hachée, et les documents qui ont des bardeaux avec les mêmes hachages que dans le document en cours de vérification sont recherchés dans l'index.
Un témoin oculaire, voyant une coïncidence dans le hachage de deux bardeaux, nous appelle avec un message sur le crime. Malheureusement, l'indice du zona ne peut être puni pour un faux appel, il est à l'abri des sanctions, c'est pourquoi il y a beaucoup d'appels. L'agence détermine les documents avec la plus grande accumulation de tels appels - la scène d'un crime potentiel.
InterludeMalgré le fait que dans le contexte de l'histoire que nous appelons les crimes liés aux fonds empruntés, en réalité l'argent emprunté peut être légitime ou provenir de faux positifs. Bien que l'Antilpagiate puisse extraire des citations, la décision finale doit être prise par le réviseur.
Premier indice
Maintenant tu es détective, fils.
Il est désormais interdit de croire aux coïncidences.
© «The Dark Knight: Revival of the Legend» («The Dark Knight Rises», dir. K. Nolan, 2012).
Le détective Fuzzy Search est arrivé sur les lieux du crime. Les criminels suffisamment grands ne passent pas inaperçus, car plus le crime est important, plus il est probable qu'il laisse un indice. Pour la recherche floue, ces pistes sont de courtes correspondances d'une longueur fixe. Il semble que notre détective manque une grande partie des traces habilement balayées de criminels, mais seulement 5% des attaquants ne laissent pas un tel indice. Il est important de ne pas perdre de criminels, de sorte que le détective scanne rapidement la zone en utilisant une technique spéciale pour détecter les matchs.
Journal du détective sur la méthode de travail. Première étape
Nous utiliserons deux caractéristiques de la tâche:
- Nous souhaitons des doublons clairs de longueur fixe.
- Dans un bon document, le même bardeau n'est pas dupliqué trop souvent.
La deuxième condition est nécessaire pour limiter le nombre de doublons clairs trouvés. En effet, un seul qui se produit 1000 fois dans le document et dans la source donnera 1 000 000 de paires de correspondances. Ces bardeaux fréquemment répétés ne peuvent être vus que dans des documents non nettoyés avec des tentatives d'exploration.
Un document débarrassé des analyses est présenté comme une séquence de mots. Nous apportons les mots à la forme de mot normale, puis les hachons. Nous obtenons une séquence d'entiers (sur le gif - une séquence de lettres). Tous les bardeaux de cette séquence sont hachés et entrés dans la table de hachage avec la valeur de la position du début de la sous-chaîne. Ensuite, pour chaque bardeau du document candidat, des correspondances sont trouvées dans la table de hachage. Cela crée des doublons clairs d'une longueur fixe. Les tests montrent une triple accélération lors de l'utilisation de la nouvelle méthode par rapport au tableau de suffixes.
RemarqueVeuillez noter que, contrairement au tableau de suffixes, qui trouve tous les doublons maximum (non extensibles), nous avons trouvé tous les doublons de longueur fixe . C'est un peu pire, mais vous devez quand même distribuer les doublons, mais une telle recherche consomme moins de ressources et est plus facile à comprendre / implémenter. Bonus: vous pouvez limiter le nombre d'enregistrements d'un doublon fréquemment répété, ce qui aidera à maintenir la linéarité sur des documents gigantesques.
Nous calculons le criminel
- Y a-t-il d'autres points sur lesquels vous me conseilleriez de prêter attention?
"Le comportement étrange du chien la nuit du crime."
- Des chiens? Mais elle ne s'est pas comportée en aucune façon!
"C'est étrange", a déclaré Holmes.
© Arthur Conan-Doyle, «Silver» (de la série «Notes on Sherlock Holmes»)
Ainsi, Fuzzy Search a trouvé plusieurs indices permettant d'identifier les criminels. Notre héros utilise ses capacités déductives au maximum, afin de peu à peu, restaurer progressivement l'image du criminel selon les indices trouvés. Le détective élargit progressivement l'image de ce qui se passe, la complétant avec de nouveaux détails, découvrant de plus en plus de preuves jusqu'à ce que cette image soit finalement complète. Notre détective est parfois amené, et il doit être descendu du ciel sur terre et convaincu que nous avons besoin de l'identité du criminel, et non de la biographie de son cousin. La recherche floue grogne, mais réduit humblement l'image à l'échelle souhaitée.
Journal du détective sur la méthode de travail. Deuxième étape
Source de l'image: pixabay.com
La deuxième étape distribue les doublons à gauche et à droite dans le document. La distribution provient des «centres» - on a trouvé des doublons clairs. Pour comparer les suffixes, nous utilisons la distance Levenshtein - le nombre minimum de suppressions / remplacements / insertions de mots nécessaires pour amener une ligne à une autre. La distance peut être calculée dynamiquement pour les suffixes en double en utilisant l'algorithme de Wagner-Fisher , basé sur la détermination récursive de la distance de Levenshtein. Cependant, cet algorithme est d'une complexité quadratique et ne permet pas de contrôler la proportion d'erreurs. Un autre problème est la définition exacte des limites des doublons. Pour résoudre ces problèmes, nous utilisons plusieurs procédures simples, mais néanmoins efficaces.
À cette étape, il est d'abord proposé de remplir séquentiellement la matrice de distance de Levenshtein pour les suffixes en double flous (puis, de même, pour les préfixes). Puisque nous vérifions la «similitude» des suffixes, nous ne nous intéressons qu'aux valeurs proches de la diagonale de cette matrice (la distance de Levenshtein est supérieure ou égale à la différence de longueurs de ligne). Cela permet une complexité linéaire. Après avoir défini la distance Levenshtein maximale autorisée, nous remplirons le tableau jusqu'à ce que nous rencontrions une colonne avec des valeurs supérieures aux valeurs autorisées. Une telle colonne indique que notre doublon flou a récemment pris fin et que les mots ont presque complètement coïncidé. Après avoir sauvegardé la précédente optimale pour chaque cellule remplie, nous descendons de la cellule avec une pénalité minimale dans la colonne critique jusqu'à ce que nous trouvions plusieurs correspondances, après quoi l'erreur a commencé à augmenter fortement. Ce seront les limites du doublon flou trouvé.
De plus, afin que les erreurs ne s'accumulent pas, une procédure est introduite qui réinitialise le nombre d'erreurs, relançant la propagation si nous tombons sur un «îlot» de coïncidences successives.
Gang de criminels
- Demain, nous prévoyons de nous réunir avec des camarades de classe!
- Dans un grand camarade de classe?
- Quoi?
© Bashorg
La recherche floue est restée une tâche simple: rassembler les criminels pris au même endroit dans des gangs, justifier les suspects innocents et recueillir les résultats ensemble.
Source de l'image: pixabay.com
Le collage de doublons résout immédiatement 3 problèmes. Premièrement, la deuxième étape de la «distribution des doublons» absorbe les modifications des mots et des phrases, mais pas les phrases entières. Si vous augmentez la "capacité d'étalement" de l'algorithme, alors il commencera à se propager sur des coïncidences trouvées à une trop grande distance, et les limites des doublons seront déterminées plus mal. Nous perdons donc la précision si importante pour nous, qu'une recherche claire avait.
Deuxièmement, la deuxième étape ne reconnaît pas la permutation de deux doublons. J'aimerais que la permutation des deux phrases à certains endroits forme une phrase proche de l'original, mais pour une ligne de caractères uniques, la permutation du préfixe et du suffixe à certains endroits mène à la ligne la plus éloignée possible de l'original (dans la métrique Levenshtein). Il s'avère que la deuxième étape, lors du réarrangement des phrases, trouve deux doublons situés l'un à côté de l'autre que vous souhaitez fusionner en un seul.
Et la troisième raison est la granularité, ou granularité. La granularité est une métrique qui détermine le nombre moyen de doublons trouvés dans un seul prêt que nous avons trouvé. En d'autres termes, la granularité montre à quel point nous trouvons l'ensemble de l'emprunt au lieu des quelques parties qui le recouvrent. La définition formelle de la granularité, ainsi que la définition de la précision et de l'exhaustivité micro-moyennes, se trouvent dans l'article «Un cadre d'évaluation pour la détection du plagiat» .
Gifka montre que parfois deux doublons ne peuvent être collés qu'après que l'un d'eux a adhéré au troisième doublon. Par conséquent, un seul passage de gauche à droite sur le document ne fonctionne pas pour terminer le collage.
AlgorithmeLa liste des doublons à l'entrée est triée par la bordure gauche du document.
Nous essayons de coller le double actuel avec plusieurs des candidats les plus proches devant lui.
S'il s'avère, essayez de le coller à nouveau, sinon, passez au duplicata suivant.
Étant donné que le nombre de doublons ne dépasse pas la longueur du document et que chaque double vérification réduit le nombre de doublons de 1 et est effectuée en temps constant, la complexité de cet algorithme est O (n).
Un ensemble de plusieurs paramètres est généralement utilisé pour coller les doublons, mais si nous oublions la microoptimisation de la qualité, nous collerons alors les doublons pour lesquels le maximum des distances dans le document et la source est suffisamment petit.
La localité de collage fournit O (1) doublons, auxquels le doublon actuel peut être collé.
Formation débutant
Le détective devait s'adapter aux caractéristiques de notre ville, s'adapter au terrain, se promener dans les rues discrètes et mieux connaître ses habitants. Pour cela, un débutant suit une formation spéciale dans laquelle il étudie des situations similaires sur un terrain d'entraînement. Le détective en pratique étudie les indices, la déduction et la construction des liens sociaux pour la capture la plus efficace des criminels.
Le modèle paramétrique devait être optimisé. Pour déterminer les paramètres optimaux du modèle, l' échantillon PlagEvalRus a été utilisé .
L'échantillon est divisé en 4 collections:
- Generated_Copypast (4250 paires) - emprunts générés textuellement
- Generated_Paraphrased (4250 paires) - emprunts faiblement et moyennement modifiés générés par la machine en utilisant le bruit des passages originaux (remplacements / suppressions / insertions arbitraires)
- Manuellement_paraphrasé (713 paires) Textes écrits à la main avec différents types d'emprunts, principalement des emprunts faibles et à modification moyenne (remplacés par pas plus de 30% des mots du double)
- Manuellement_Paraphrasé 2 (198 paires) Textes écrits à la main avec des emprunts moyens et très modifiés (plus de 30% de mots)
L'échantillon contient également le type de chaque emprunt.- DEL - Supprimer des mots individuels (jusqu'à 20%) de la phrase d'origine.
- AJOUTER - Ajoutez des mots simples (jusqu'à 20%) à la phrase d'origine.
- LPR - Changement de forme (changement du nombre, de la casse, de la forme et du temps d'un verbe, etc.) des mots individuels (jusqu'à 30%) de la phrase d'origine.
- SHF - Changer l'ordre des mots ou des parties d'une phrase (tours, parties d'une phrase simple en tant que partie d'un complexe) sans changements significatifs «à l'intérieur» des parties réarrangées.
- CCT - Collez deux phrases ou plus du texte source en une seule phrase.
- SEP / SSP - Division de la phrase complexe initiale en deux phrases indépendantes ou plus (éventuellement avec un changement dans l'ordre de leur séquence dans le texte).
- SYN - Remplacement de mots individuels ou de termes individuels par des synonymes (par exemple, «sel» - «chlorure de sodium»), remplacement des abréviations par leur déchiffrement complet et vice versa, révélant les initiales de votre nom complet et vice versa, remplacement du prénom par les initiales, etc.
- HPR - Traitement efficace de la phrase d'origine, qui est une combinaison de nombreux (3-5 ou plus) types de modification de texte ci-dessus. Le même type suppose une forte modification du texte source par périphrase en utilisant des expressions idiomatiques, des constructions synonymes complexes, la permutation de mots ou de parties d'une phrase complexe, etc. astuces qui, ensemble, rendent difficile la détermination de la correspondance entre la source d'origine et le texte modifié.
La recherche des paramètres optimaux du modèle a été effectuée en utilisant la méthode de descente multi-départs. Maximisé mesurer avec (accent mis sur la précision). Voici les paramètres optimaux les plus significatifs.
Histoire de cas
La période d'essai de notre recherche floue est terminée. Comparons sa productivité avec celle d'un autre détective, le Suffix Array. Le cours de formation Fuzzy Search a eu lieu sur le programme Manually_Paraphrased.
Sur le terrain, le nouveau venu a montré une supériorité significative dans la proportion de cas résolus. La vitesse de son travail ne peut que se réjouir. Notre agence manquait d'un employé aussi précieux.
En comparant la qualité du modèle avec le réseau de suffixes, nous remarquons une amélioration significative de la granularité, ainsi qu'une meilleure détection des emprunts moyens et fortement modifiés.
En testant des documents jusqu'à 10 7 mots, nous vérifions la linéarité des deux algorithmes. Sur le processeur i5-4460, le programme traite une paire de «sources de documents» d'un million de mots en moins d'une seconde.
Ayant généré des textes avec un grand nombre d'emprunts, nous sommes convaincus que la recherche floue (ligne bleue) n'est pas plus lente que le tableau des suffixes (ligne rouge). Inversement, un tableau de suffixes souffre sur les gros documents de trop de doublons. Nous avons comparé les performances avec une longueur minimale en double de 5 mots. Mais pour une couverture d'emprunt suffisante, nous utilisons une recherche claire avec une longueur minimale en double de 3 mots, ce qui conduit sur des documents gigantesques à une baisse significative de la productivité (ligne orange). Il convient de noter que les documents ordinaires contiennent moins d'emprunts et, dans la pratique, cet effet est beaucoup moins prononcé. Mais une telle expérience permet de comprendre l'expansion de l'applicabilité des modèles avec une nouvelle recherche floue.
Exemples:
On peut voir que l'algorithme, malgré la faible complexité de calcul, gère la détection des remplacements / suppressions / insertions, et la troisième étape vous permet de détecter les emprunts avec la permutation des phrases et de leurs parties.
Épilogue
La recherche floue fonctionne en équipe avec nos autres outils: recherche rapide des documents candidats, extraction de la mise en forme des documents, capture à grande échelle des tentatives de contournement. Cette commande vous permet de trouver rapidement un plagiat potentiel. La recherche floue a pris racine dans cette équipe et exécute ses fonctions de recherche de manière plus qualitative et, surtout, plus rapide que la matrice de suffixes. Notre agence s'acquittera encore mieux de ses tâches et les auteurs sans scrupules rencontreront de nouveaux problèmes lors de l'utilisation de textes non originaux .
Créez avec votre propre esprit!