Outils de développement · Comparaison de texte
Comment une différence de texte trouve les lignes modifiées : LCS et l'algorithme Myers
· Comment ça marche
texte-diff algorithmes flux de travail du développeur
Explique l'idée de la sous-séquence commune la plus longue derrière la comparaison basée sur les lignes et pourquoi l'algorithme de Myers l'a rendu suffisamment rapide pour s'exécuter instantanément, même dans un onglet de navigateur.
Deux fichiers, une question : quelles lignes ont survécu ? — comparaison des cadres consistant à trouver la plus longue série de lignes communes aux deux versions plutôt que de faire correspondre les numéros de ligne
Deux révisions n'arrivent pas avec des étiquettes indiquant quelles lignes ont survécu. ToolAcre divise d'abord chaque texte en une liste ordonnée, puis recherche une longue sous-séquence apparaissant dans les deux listes dans le même ordre. Les lignes en dehors de cette colonne vertébrale partagée deviennent des ajouts ou des suppressions plutôt que des modifications devinées.
Le résultat comporte des positions originales à base unique pour les deux côtés. Une rangée inchangée possède un numéro de chaque côté, une suppression uniquement à gauche et une addition uniquement à droite. Cette comptabilité rend l'histoire affichée révisable même lorsque des lignes répétées donnent plus d'un alignement plausible.
Pourquoi diff fonctionne sur les lignes, pas sur les caractères - comment le fractionnement sur les nouvelles lignes transforme un texte en une séquence d'unités comparables et pourquoi cela fait que la prose se comporte différemment du code
L'implémentation traite une ligne complète comme unité de comparaison. Les limites de nouvelle ligne façonnent donc le résultat : une modification d'un mot à l'intérieur d'un paragraphe stocké sur une ligne remplace cette ligne entière, tandis que la même prose arrangée phrase par phrase peut isoler une région beaucoup plus petite.
La comparaison de lignes n'est pas une analyse de caractères cachée derrière un affichage différent. `splitLines` crée des tableaux et la table LCS compare une clé de ligne avec une autre. Cette granularité prévisible convient aux fichiers source et de configuration, mais elle ne peut pas mettre en évidence les lettres exactes modifiées dans un remplacement d'apparence correspondante.
La sous-séquence commune la plus longue en termes simples : présente l'idée LCS sur un exemple de cinq lignes et montre comment tout ce qui se trouve en dehors de la sous-séquence devient une insertion ou une suppression.
Imaginez les lignes gauche A, B, C, D, E et les lignes droite A, C, E. A, C et E forment une sous-séquence commune ordonnée. B et D se situent en dehors de celui-ci, le résultat indique donc deux suppressions et trois lignes inchangées sans qu'il soit nécessaire d'associer l'une ou l'autre des lignes supprimées à un remplacement.
Le tableau enregistre, pour chaque paire de positions restante, la meilleure longueur partagée disponible à partir de là. La reconstruction avance à travers ces valeurs. Des touches égales avancent des deux côtés ; sinon, la valeur voisine la plus grande décide s'il faut émettre une suppression à gauche ou une addition à droite.
L'algorithme Myers et pourquoi la vitesse est importante : explique, sans formules, comment le traçage du script d'édition le plus court permet une comparaison rapide sur des fichiers comportant des milliers de lignes.
Le classeur nomme Myers, mais `diff.js` implémente explicitement une programmation dynamique simple à sous-séquence commune la plus longue. Son commentaire indique le temps et la mémoire O(n·m) pour le milieu différent. Revendiquer Myers ou le comportement du graphe d'édition le plus court remplacerait un algorithme familier par le code réellement livré.
ToolAcre limite ce coût avant allocation. Les préfixes et suffixes égaux sont décollés en passes linéaires, et chaque milieu différent peut contenir au plus 2,000 lignes. La matrice est un `Uint32Array` ; le pire carré autorisé documenté occupe environ seize mégaoctets plutôt que des valeurs encadrées illimitées.
ToolAcre utilise une table LCS, pas l'algorithme Myers nommé dans le plan
Comparez un journal des modifications contenant « Recherche ajoutée », « Exportation corrigée » et « Aide mise à jour » avec une révision qui conserve les première et troisième entrées mais insère « Filtres ajoutés » avant la dernière. Les entrées communes ancrent le chemin, « Exportation fixe » est supprimé et « Filtres ajoutés » est ajouté.
L'algorithme n'appelle pas cette paire une ligne modifiée. Son vocabulaire de lignes est uniquement égal, ajouté et supprimé, donc un remplacement textuel apparaît comme une suppression suivie d'un ajout. Le résumé compte ces opérations séparément et marque les textes identiques uniquement lorsque les deux comptes sont nuls.
Pourquoi deux différences correctes peuvent sembler différentes – montre comment les liens entre des scripts d'édition également courts expliquent pourquoi un outil blâme une ligne vide et un autre blâme un crochet fermant.
Des lignes répétées ou interchangeables peuvent produire plusieurs sous-séquences communes de même longueur. ToolAcre résout une égalité en préférant une suppression lorsque les deux valeurs de table voisines sont égales. Une autre implémentation correcte peut choisir d'abord un ajout et présenter un alignement d'aspect différent avec le même coût d'édition.
C'est pourquoi une ligne vide ou une accolade fermante peut apparaître attachée à un morceau différent dans les outils. L’écart ne signifie pas automatiquement que la comparaison a perdu du contenu. Lisez les numéros de ligne d'origine et les lignes inchangées environnantes avant de traiter les différences de présentation comme des affirmations factuelles concurrentes.
Ce que cela ne couvre pas : la comparaison sémantique ou structurelle, la détection de mouvement et la mise en évidence au niveau des mots sont en dehors de ce que calcule une différence basée sur une ligne.
Rien dans ce chemin n'analyse les arbres de syntaxe, ne reconnaît les identifiants renommés, n'étiquette les blocs déplacés ou ne comprend le sens de la prose. Un paragraphe déplacé viole l’exigence d’ordre partagé et peut apparaître une fois comme supprimé et une fois comme ajouté. L’outil ne calcule pas non plus les surlignages au niveau des caractères ou des mots à l’intérieur des lignes.
Ces omissions sont des limites, pas des modes cachés. Utilisez un réviseur prenant en charge le langage pour les revendications sémantiques et le contrôle de version pour l'historique des fusions. Text diff répond à la question plus précise de la différence entre deux séquences de lignes ordonnées, puis permet à l'humain d'interpréter si ces modifications textuelles sont importantes.
À retenir : ce que signifient réellement les lignes en surbrillance - résume comment lire une différence de ligne comme l'histoire la plus courte des modifications et comment la comparaison de texte de ToolAcre l'exécute dans votre onglet sans rien télécharger
Lisez les lignes vertes et rouges comme une explication dérivée du LCS, et non comme une preuve de l'intention de l'auteur. La suppression des préfixes et des suffixes modifie la quantité de travail mais pas la comptabilité finale. Le texte original reste dans chaque ligne même lorsque les options de casse ou d'espace fournissent des clés de correspondance plus lâches.
La comparaison s'exécute via les modules de navigateur importés et s'affiche avec les nœuds de texte DOM ; il n'y a pas de point final de conversion dans le chemin d'outil. Essayez un exemple de cinq lignes, échangez les côtés et téléchargez la sortie en forme de patch pour voir comment la direction transforme les ajouts en suppressions sans inventer de sémantique.