Mise en œuvre d'un widget diff texte à partir d'un problème d'algorithme

Xiaolin au coin de la rue 2021-08-19 21:09:11 阅读数:526

mise en uvre widget diff

Tout le monde sait,De nombreuses communautés ont des mécanismes de vérification du contenu,À part la première sortie,Les modifications subséquentes doivent également être examinées,La façon la plus brutale, bien sûr, est de regarder de nouveau depuis le début,Mais le rédacteur en chef veut vous tuer,Apparemment, c'est moins efficace,Comme changer une mauvaise typographie,Ça ne se voit peut - être pas encore,Donc si vous pouviez savoir ce qui a été modifié à chaque fois,C'est comme...gitDediffC'est pareil,Ce serait beaucoup plus pratique,Cet article est une simple mise en œuvre d'un.

Trouver la plus longue sous - séquence commune

Pour savoir quelle est la différence entre les deux paragraphes,Nous pouvons d'abord trouver leur contenu public,Tout ce qui reste est supprimé ou ajouté.Dans l'algorithme,C'est un sujet classique,Il y a ce problème avec la boucle de force1143. La plus longue sous - séquence commune,Le titre est décrit ci - dessous:

image-20210816195639935.png

Ce genre de problème de maximisation est généralement fait en utilisant la programmation dynamique,La programmation dynamique est plus comme un problème de raisonnement,Vous pouvez utiliser récursive pour résoudre de haut en bas,Peut également être utiliséforFaites le cycle du bas vers le haut,UtiliserforLes boucles utilisent généralement undpPour stocker des informations,L'utilisation spécifique d'un tableau à plusieurs dimensions dépend du sujet,Ce problème parce qu'il y a deux variables(La longueur des deux chaînes)Donc nous utilisons un tableau bidimensionnel,Nous définissonsdp[i][j]Représentationtext1De0-i Substrats et text2De0-jLongueur maximale de la Sous - séquence commune pour les substrats de,Ensuite, il faut tenir compte de la situation limite, D'abord quand iPour0Quandtext1 Est une chaîne vide , Donc peu importe jLa longueur de la plus longue sous - séquence commune est0,jPour0 C'est la même chose. ,Donc nous pouvons initialiser une valeur initiale avec toutes les valeurs de0DedpTableau:

let longestCommonSubsequence = function (text1, text2) {
let m = text1.length
let n = text2.length
let dp = new Array(m + 1)
dp.forEach((item, index) => {
dp[index] = new Array(n + 1).fill(0)
})
}

QuandiEtj Pas du tout. 0Dans le cas de,Il y a plusieurs situations:

1.Quandtext1[i - 1] === text2[j - 1]Heure,Description les deux positions ont les mêmes caractères,Donc ils doivent être dans la séquence du premier enfant,Les plus longues sous - séquences actuelles dépendent des sous - chaînes qui les précèdent,C'est - à - diredp[i][j] = 1 + dp[i - 1][j - 1];

2.Quandtext1[i - 1] !== text2[j - 1]Heure,C'est évidentdp[i][j]Tout dépend de ce qui s'est passé avant, Il y en a trois. :dp[i - 1][j - 1]dp[i][j - 1]dp[i - 1][j],Mais le premier cas peut être exclu,Parce qu'il n'y aura évidemment pas les deux dernières situations,Parce que les deux derniers ont un caractère de plus que le premier,Donc ça pourrait être plus long1,Donc nous prenons la meilleure valeur pour les deux derniers cas;

Ensuite, il suffit d'une double boucle pour traverser tous les cas d'un tableau bidimensionnel:

let longestCommonSubsequence = function (text1, text2) {
let m = text1.length
let n = text2.length
// Initialisation d'un tableau 2D
let dp = new Array(m + 1).fill(0)
dp.forEach((item, index) => {
dp[index] = new Array(n + 1).fill(0)
})
for(let i = 1; i <= m; i++) {
// Parce queiEtj De 1Au début, Donc il faut soustraire 1
let t1 = text1[i - 1]
for(let j = 1; j <= n; j++) {
let t2 = text2[j - 1]
// La situation1
if (t1 === t2) {
dp[i][j] = 1 + dp[i - 1][j - 1]
} else {// La situation2
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
}
}
}
}

dp[m][n]La valeur de est la longueur de la plus longue sous - séquence commune,Mais ça ne sert à rien de savoir la longueur,Nous devons savoir exactement où, Une récursion supplémentaire est nécessaire ,Pourquoi pas dans ce cyclet1 === t2Où est la collecte des positions dans la branche de,Parce que toutes les positions des deux chaînes sont comparées,Il y a duplication lorsqu'il y a plusieurs caractères identiques, Comme en bas. :

image-20210817191053130.png

Nous définissons collectFonctions, Jugement récursif iEtjLa position est - elle dans la séquence la plus longue des enfants,Comme pouriEtjEmplacement,Sitext1[i - 1] === text2[j - 1],Donc, apparemment, ces deux positions sont dans la plus longue sous - séquence, Il suffit de juger. i - 1Etj - 1Emplacement,Et ainsi de suite.,Si la position actuelle n'est pas la même, nous pouvons utiliserdp Array to judge ,Parce qu'à ce moment - là, nous connaissons toutdp Valeur du tableau :

image-20210817194735329.png

Il n'est donc plus nécessaire d'essayer chaque position,Il n'y aura pas de répétition,Par exemple,dp[i - 1] > dp[j],Alors ce qu'il faut juger, c'esti-1EtjEmplacement, Sinon, jugez. iEtj-1Emplacement, La condition de fin de récursion est iEtj Un est arrivé. 0Emplacement:

let arr1 = []
let arr2 = []
let collect = function (dp, text1, text2, i, j) {
if (i <= 0 || j <= 0) {
return
}
if (text1[i - 1] === text2[j - 1]) {
// Collecte des index des mêmes caractères dans les deux chaînes
arr1.push(i - 1)
arr2.push(j - 1)
return collect(dp, text1, text2, i - 1, j - 1)
} else {
if (dp[i][j - 1] > dp[i - 1][j]) {
return collect(dp, text1, text2, i, j - 1)
} else {
return collect(dp, text1, text2, i - 1, j)
}
}
}

Les résultats sont les suivants::

image-20210817202220822.png

Comme vous pouvez le voir, c'est dans l'ordre inverse,Si vous n'aimez pas, vous pouvez aussi faire une séquence:

arr1.sort((a, b) => {
return a - b
});
arr2.sort((a, b) => {
return a - b
});

Ce n'est toujours pas fini ici,Nous devons également calculer les suppressions et les ajouts en fonction de la Sous - séquence la plus longue,C'est plus simple,Passez directement à travers les deux chaînes,Non.arr1Etarr2Les caractères des autres positions sont supprimés ou ajoutés:

let getDiffList = (text1, text2, arr1, arr2) => {
let delList = []
let addList = []
// Traverser les anciennes chaînes
for (let i = 0; i < text1.length; i++) {
// Les représentations de caractères dans l'ancienne chaîne qui ne sont pas dans la Sous - séquence commune sont supprimées
if (!arr1.includes(i)) {
delList.push(i)
}
}
// Traverser la nouvelle chaîne
for (let i = 0; i < text2.length; i++) {
// Les représentations de caractères dans la nouvelle chaîne qui ne sont pas dans la Sous - séquence commune sont nouvelles
if (!arr2.includes(i)) {
addList.push(i)
}
}
return {
delList,
addList
}
}

image-20210818094131108.png

Dimensions supprimer et ajouter

Nous connaissons les sous - séquences communes et les index ajoutés et supprimés,Alors on peut le marquer,Par exemple, supprimer avec un fond rouge,Nouveau fond vert,Un coup d'oeil sur ce qui a changé.

Simple. ,Nous afficherons les ajouts et les suppressions dans le même texte,Comme ça.:

image-20210818094506055.png

Supposons qu'il y ait deux paragraphes de texte à comparer,À l'intérieur de chaque paragraphe se trouve\n Ligne séparée ,On va d'abord les diviser en tableaux,Puis comparez - les deux à tour de rôle,Si l'ancien et le nouveau texte sont égaux, ajoutez - le directement au tableau affiché,Sinon, nous opérons sur la base du nouveau texte,Si un caractère à un endroit est ajouté, Enveloppez - le avec une nouvelle étiquette,Les caractères supprimés sont également localisés dans le nouveau texte et enveloppés d'une étiquette avant d'être insérés,La section modèle est la suivante:

<template>
<div class="content">
<div class="row" v-for="(item, index) in showTextArr" :key="index">
<span class="rowIndex">{{ index + 1 }}</span>
<span class="rowText" v-html="item"></span>
</div>
</div>
</template>

Puis comparez les deux:

export default {
data () {
return {
oldTextArr: [],
newTextArr: [],
showTextArr: []
}
},
mounted () {
this.diff()
},
methods: {
diff () {
// L'ancien et le nouveau texte sont divisés en tableaux
this.oldTextArr = oldText.split(/\n+/g)
this.newTextArr = newText.split(/\n+/g)
let len = this.newTextArr.length
for (let row = 0; row < len; row++) {
// Si les anciens et les nouveaux textes sont identiques, il n'est pas nécessaire de les comparer
if (this.oldTextArr[row] === this.newTextArr[row]) {
this.showTextArr.push(this.newTextArr[row])
continue
}
// Sinon, calculez l'emplacement de la plus longue sous - séquence commune de l'ancien et du nouveau texte
let [arr1, arr2] = longestCommonSubsequence(
this.oldTextArr[row],
this.newTextArr[row]
)
// Effectuer des opérations de dimensionnement
this.mark(row, arr1, arr2)
}
}
}
}

markLa méthode est utilisée pour générer la chaîne finale avec des informations différentielles, Passe d'abord par là. getDiffListMéthode pour obtenir les informations d'index supprimées et ajoutées,Parce que nous sommes sur la base du nouveau texte,Il est donc plus facile d'ajouter,Traverser directement l'index nouvellement ajouté,Puis trouvez le caractère correspondant à la position dans la nouvelle chaîne,Les caractères des éléments de l'étiquette sont collés à l'avant et à l'arrière:

/*
oldArr:Tableau d'index des sous - séquences publiques les plus longues pour l'ancien texte
newArr:Le plus long tableau commun d'index des sous - séquences pour le nouveau texte
*/
mark (row, oldArr, newArr) {
let oldText = this.oldTextArr[row];
let newText = this.newTextArr[row];
// Obtenir les index de localisation supprimés et ajoutés
let { delList, addList } = getDiffList(
oldText,
newText,
oldArr,
newArr
);
// Parce que span Les étiquettes prendront également place ,Il en résulte un décalage de notre nouvel index,La longueur de l'étiquette doit être soustraite pour être corrigée
let addTagLength = 0;
// Traverser le nouveau tableau de localisation
addList.forEach((index) => {
let pos = index + addTagLength;
// Tronquer la chaîne avant la position actuelle
let pre = newText.slice(0, pos);
// Tronquer la chaîne suivante
let post = newText.slice(pos + 1);
newText = pre + `<span class="add">${newText[pos]}</span>` + post;
addTagLength += 25;// <span class="add"></span> La longueur de 25
});
this.showTextArr.push(newText);
}

Les effets sont les suivants:

image-20210818181744111.png

image-20210818181753703.png

Il serait un peu plus difficile de supprimer,Parce qu'apparemment les caractères supprimés n'existent pas dans le nouveau texte,Nous devons trouver où il devrait être s'il n'a pas été supprimé,Et le remettre ici, On va dessiner. :

image-20210818183712848.png

Regardez d'abord ce qui a été supprimé. Dégage!,Sa position dans l'ancienne chaîne est3,Par la plus longue sous - séquence commune,Nous pouvons trouver l'index des caractères avant lui dans la nouvelle liste,Il est clair que l'index est suivi de la position du caractère supprimé dans la nouvelle chaîne:

image-20210818184131840.png

Écrivez d'abord une fonction pour obtenir l'index des caractères supprimés dans le nouveau texte:

getDelIndexInNewTextIndex (index, oldArr, newArr) {
for (let i = oldArr.length - 1; i >= 0; i--) {
if (index > oldArr[i]) {
return newArr[i] + 1;
}
}
return 0;
}
}

Ensuite, on calcule la position exacte dans la chaîne,PourDégage!Sa position est calculée comme suit:

image-20210818185833500.png

mark (row, oldArr, newArr) {
// ...
// Traverser le tableau d'index supprimé
delList.forEach((index) => {
let newIndex = this.getDelIndexInNewTextIndex(index, oldArr, newArr);
// Nombre de caractères ajoutés précédemment
let addLength = addList.filter((item) => {
return item < newIndex;
}).length;
// Nombre de caractères non modifiés avant
let noChangeLength = newArr.filter((item) => {
return item < newIndex;
}).length;
let pos = addLength * 26 + noChangeLength;
let pre = newText.slice(0, pos);
let post = newText.slice(pos);
newText = pre + `<span class="del">${oldText[index]}</span>` + post;
});
this.showTextArr.push(newText);
}

Par ici.Dégage! L'emplacement de , Voir l'effet :

image-20210818190258024.png

On voit que c'est le chaos derrière,La raison en est simple.,PourCrystalDis, Nouveau Dégage!Nous n'avons pas ajouté:

// Position des caractères insérés
let insertStrLength = 0;
delList.forEach((index) => {
let newIndex = this.getDelIndexInNewTextIndex(index, oldArr, newArr);
let addLength = addList.filter((item) => {
return item < newIndex;
}).length;
let noChangeLength = newArr.filter((item) => {
return item < newIndex;
}).length;
// Plus la longueur totale des nouveaux caractères insérés
let pos = insertStrLength + addLength * 26 + noChangeLength;
let pre = newText.slice(0, pos);
let post = newText.slice(pos);
newText = pre + `<span class="del">${oldText[index]}</span>` + post;
// <span class="del">x</span> La longueur de 26
insertStrLength += 26;
});

Nous sommes ici précipitammentdiff L'outil est terminé. :

image-20210818191126696.png

Problèmes existants

Croyez en l'intelligence, vous devez trouver la mise en oeuvre ci - dessus problématique,Si j'efface une ligne entière,Ou ajouter une ligne complète,D'abord, le nombre de lignes nouvelles et anciennes est différent, Répare - le d'abord. diffFonctions:

diff () {
this.oldTextArr = oldText.split(/\n+/g);
this.newTextArr = newText.split(/\n+/g);
// Si le nombre de lignes nouvelles et anciennes est différent,Compléter avec une chaîne vide
let oldTextArrLen = this.oldTextArr.length;
let newTextArrLen = this.newTextArr.length;
let diffRow = Math.abs(oldTextArrLen - newTextArrLen);
if (diffRow > 0) {
let fixArr = oldTextArrLen > newTextArrLen ? this.newTextArr : this.oldTextArr;
for (let i = 0; i < diffRow; i++) {
fixArr.push('');
}
}
// ...
}

Si nous sommes la dernière ligne ajoutée ou supprimée, Ce n'est pas un problème. :

image-20210818192107232.png

Mais,Si une ligne au milieu est ajoutée ou supprimée,Alors tout ce qui est derrière cette lignediff Ça n'a aucun sens. :

image-20210818192342057.png

La raison en est simple., Une ligne a été supprimée ,Ce qui fait que les deux derniers contrastes sont juste décalés, Et alors? ,Une idée est de découvrir qu'une ligne a été supprimée ou qu'une ligne a été ajoutée,Puis corrigez le nombre de lignes contrastées,Une autre façon est de ne plus séparer chaque lignediff, Mais directement. diff Texte complet ,Cela n'a pas d'importance de supprimer les nouvelles lignes.

La première idée, c'est que l'auteur n'est pas sûr,Alors on ne peut voir que le second,On supprime la logique de segmentation par sauts de ligne,Directdiff Texte complet :

diff () {
this.oldTextArr = [oldText];// .split(/\n+/g);
this.newTextArr = [newText];// .split(/\n+/g);
// ...
}

image-20210818192825679.png

On dirait bien. ,Augmentons le nombre de textes:

image-20210818193054909.png

Il fait froid. ,De toute évidence, notre simple algorithme précédent pour trouver la plus longue sous - séquence commune ne supporte pas trop de texte,Que ce soitdpLe tableau prend trop d'espace,Ou le nombre de couches de l'algorithme récursif est trop profond pour causer un débordement de mémoire.

Pour l'auteur de l'algorithme Slag, ce n'est pas sûr,Et alors?,On ne peut utiliser que le pouvoir de l'Open Source, Dang Dang Dang ,C'est ça:diff-match-patch.

diff-match-patchBibliothèque

diff-match-patchEst une bibliothèque haute performance pour manipuler le texte,Prise en charge de plusieurs langages de programmation,En plus de calculer la différence entre les deux textes,Il peut également être utilisé pour faire des correspondances floues et des correctifs,Ça se voit aussi par son nom.

Facile à utiliser,On va d'abord l'attirer,importL'introduction de la méthode nécessite une modification du fichier source,Le code source par défaut suspend les classes dans l'environnement global,On va sortir la classe manuellement,Et puisnew Un exemple ,AppelezdiffLa méthode est juste:

import diff_match_patch from './diff_match_patch_uncompressed';
const dmp = new diff_match_patch();
diffAll () {
let diffList = dmp.diff_main(oldText, newText);
console.log(diffList);
}

Le résultat est le suivant:

image-20210818195940486.png

Renvoie un tableau ,Chacun représente une différence,0 Aucune différence de représentation ,1 Le représentant est nouveau ,-1 Representative is deleted ,Il suffit de traverser ce tableau pour assembler les chaînes,C'est très simple.:

diffAll () {
let diffList = dmp.diff_main(oldText, newText);
let htmlStr = '';
diffList.forEach((item) => {
switch (item[0]) {
case 0:
htmlStr += item[1];
break;
case 1:
htmlStr += `<span class="add">${item[1]}</span>`;
break;
case -1:
htmlStr += `<span class="del">${item[1]}</span>`;
break;
default:
break;
}
});
this.showTextArr = htmlStr.split(/\n+/);
}

image-20210818201307191.png

Mesure réelle21432Caractèresdiff Temps écoulé 4msGauche et droite, C'est rapide. .

C'est bon,Plus tard, le rédacteur en chef sera heureux de pêcher~

Résumé

Cet article fait simplement un【Trouver la plus longue sous - séquence commune】 Problème d'algorithme pour ,Et l'analyse dans le textediffUne utilisation pratique sur,Mais nos algorithmes simples ne supportent pas les projets réels,Ainsi, si vous avez des exigences connexes, vous pouvez utiliser une bibliothèque open source décrite dans cet article.

Exemple complet de code :https://github.com/wanglin2/text_diff_demo

Copyright:Cet article est[Xiaolin au coin de la rue]Établi,Veuillez apporter le lien original pour réimprimer,remercier。 https://fra.fheadline.com/2021/08/20210819210825550H.html