2009-11-23 15 views
4

Je dois faire Word par mot comparaison de deux chaînes. Quelque chose comme diff, mais pour les mots, pas pour les lignes.Comparaison mot par mot diff de deux chaînes dans .NET

Comme cela se fait dans wikipedia http://en.wikipedia.org/w/index.php?title=Horapollo&action=historysubmit&diff=21895647&oldid=21893459

En résultat que je veux retourner les deux tableaux d'index de mots, qui sont différentes dans deux cordes.

Y a-t-il des bibliothèques/frameworks/standalone_methods pour .NET qui peuvent faire cela?

P.S. Je veux comparer plusieurs kilo-octets de texte

+0

Dupliquer de http://stackoverflow.com/questions/473522/word-comparison-algorithm –

+2

D'abord, divisez les chaînes en deux groupes de mots. Ensuite, il est assez simple de trouver les chaînes qui sont les mêmes dans deux tableaux. Et si vous pouvez le faire, alors vous pouvez sûrement trouver les mots qui sont différents. Voici un exemple simple dans JScript; le transformer en C# ne prend que quelques minutes. http://beta.blogs.msdn.com/ericlippert/archive/2004/07/21/recursion-and-dynamic-programming.aspx –

Répondre

3

Il semble que j'ai trouvé la solution nécessaire:

DiffPlex est une combinaison d'une bibliothèque .NET diffing à la fois une visionneuse diff Silverlight et HTML. http://diffplex.codeplex.com/

Mais il a un bug. Dans ces lignes "Hello-Kitty" "Bonjour - Kitty", le mot "Bonjour" sera marqué comme différence. Bien que la différence soit le symbole de l'espace.

1

vous pouvez remplacer tous les mots de vos 2 textes par des nombres uniques, prendre du code prêt à l'emploi pour modifier le calcul de distance et remplacer son caractère par une comparaison de caractères terminé!

Je ne suis pas sûr s'il existe une bibliothèque pour exactement ce que vous voulez. Mais vous trouverez sûrement beaucoup de code pour la distance d'édition. En outre, selon que vous souhaitez réellement autoriser des substitutions ou non dans le calcul de la distance d'édition, vous pouvez modifier les conditions dans le code de programmation dynamique.

Voir ceci. http://en.wikipedia.org/wiki/Levenshtein_distance

+0

En fait, j'ai déjà écrit la routine comparizon, mais je n'aime pas comment cela fonctionne, parce que de nouveaux bugs apparaissent de temps en temps, mais je n'ai pas beaucoup de temps à me battre, car c'est la petite paix de toutes les fonctionnalités. C'est pourquoi j'ai cherché déjà une bonne chose testée. C'est drôle, mais il semble que telle chose n'existe pas :) –

+0

@Alex: Voir ma réponse ci-dessus :) – Pedery

1

Vous pouvez essayer cela, bien que je ne suis pas sûr que c'est ce que vous cherchez StringUtils.difference() (http://commons.apache.org/lang/api-release/org/apache/commons/lang/StringUtils.html#difference%28java.lang.String,%20java.lang.String%29)

Alternativement, le projet Eclipse (eclipse.org) a une fonction de comparaison de diff, qui signifie qu'ils doivent également avoir du code pour déterminer les différences, vous pouvez parcourir leur API ou source pour voir ce que vous pouvez trouver.

Bonne chance.

2

Utilisez RegularExpressions.

Comme dans l'exemple:

using System; 
using System.Collections.Generic; 
using System.ComponentModel; 
using System.Data; 
using System.Drawing; 
using System.Text; 
using System.Windows.Forms; 
using System.Collections.Specialized; 

namespace WindowsApplication10 
{ 
    public partial class Form1 : Form 
    { 
     public Form1() 
     { 
      InitializeComponent(); 
     } 

     private void button2_Click(object sender, EventArgs e) 
     { 
      decimal discrimation = 0.75M; 
      string formHeading = "The brown dog jumped over the red lazy river, and then took a little nap! Fun!"; 
      string userSearch = "The brown dog jumped over the red lazy river, and then took a little "; 
      //string userSearch = "brown dog nap fun"; 
      decimal res = CompareText(formHeading, userSearch); 

      if (res >= discrimation) 
      { 
       MessageBox.Show("MATCH!" + res.ToString()); 
      } 
      else 
      { 
       MessageBox.Show("does not match! " + res.ToString()); 
      } 
     } 


     /// <summary> 
     /// Returns a percentage of 1 on how many words were matched 
     /// </summary> 
     /// <returns></returns> 
     private decimal CompareText(string formHeading, string userSearch) 
     { 
      StringCollection formHeadingWords = new StringCollection(); 
      StringCollection userSearchWords = new StringCollection(); 
      formHeadingWords.AddRange(System.Text.RegularExpressions.Regex.Split(formHeading, @"\W")); 
      userSearchWords.AddRange(System.Text.RegularExpressions.Regex.Split(userSearch, @"\W")); 

      int wordsFound = 0; 
      for (int i1 = 0; i1 < userSearchWords.Count; i1++) 
      { 
       if (formHeadingWords.Contains(userSearchWords[i1])) 
        wordsFound += 1; 
      } 
      return (Convert.ToDecimal(wordsFound)/Convert.ToDecimal(formHeadingWords.Count)); 
     } 
    } 
} 
4

En fait, vous voulez probablement mettre en œuvre une variante des algorithmes d'alignement d'alignement local/global que nous utilisons dans l'ADN sequence alignments. C'est parce que vous ne pouvez probablement pas faire une comparaison mot à mot des deux chaînes. À savoir:

Le renard brun rapide saute par-dessus le chien paresseux
Le renard rapide saute par-dessus le chien paresseux

En d'autres termes, si vous ne pouvez pas identifier des insertions et des suppressions de mots entiers, votre algorithme de comparaison peut devenir très sc (r) ewed. Jetez un oeil à l'algorithme Smith-Waterman et l'algorithme Needleman-Wunsch et de trouver un moyen de les adapter à vos besoins. Comme un tel espace de recherche peut devenir très grand si les chaînes sont longues, vous pouvez également consulter BLAST.BLAST est un algorithme heuristique très courant, et est à peu près la norme dans les recherches génétiques.

+0

Je n'ai pas compris, pourquoi je ne peux pas faire une comparaison mot à mot des deux cordes? Ce que je veux est comme vous l'avez dit - identifier les insertions et les suppressions de mots entiers. –

+0

Parce que si vous comparez mot par mot, votre algorithme de comparaison peut rapidement devenir très compliqué. L'exemple ci-dessus est trivial, mais illustre le point Les algorithmes de séquence que j'ai proposés ont été conçus pour identifier les lacunes et les insertions dans des séquences comparables. PS: n'oubliez pas de récompenser les réponses que vous trouvez utiles. Après tout, c'est ainsi que cette communauté reste en vie. Cliquez sur les images de la flèche vers le haut à côté des réponses utiles. – Pedery

0

Une bibliothèque supplémentaire pour C# est diff-match-patch - http://code.google.com/p/google-diff-match-patch/.

La mauvaise chose qu'il trouve une différence dans les caractères. La bonne chose, il y a une instruction que vous devez ajouter à diff les mots.