Text-Delta-Bestimmung (hierarchisch)

Question

Ich habe einen Fall, der Vergleich (und Diff-Bestimmung) von zwei Texten erfordert.

Dies sind tatsächlich hierarchische Konfigurationsdateien und alle Unterelemente sind in jeder Ebene eingerückt. Beispiel:

Datei 1:

conf_1 
    conf_1_1 
    conf_1_2 
    conf_1_3 
     conf_1_3_1 
    conf_1_4 
     conf_1_4_1 
     conf_1_4_2 

File 2:

conf_1 
    conf_1_1 
    conf_1_2 
    conf_1_3 
     conf_1_3_1 
     conf_1_3_2 
    conf_1_4 
     conf_1_4_1 
     conf_1_4_2 
    conf_1_5 

Der Vergleich zwischen diesen beiden Dateien sollten das Ergebnis als:

Ergebnis:

conf_1 
    conf_1_3 
     conf_1_3_2 
    conf_1_5 

Bemerkungen :

• Ich bin nur in Plus-Delta interessiert (die Ergänzungen in der zweiten Datei).
• Reihenfolge der Zeilen kann sich zwischen zwei Dateien ändern, dies sollte nicht
  als Unterschied interpretiert werden, sobald die Hierarchie beibehalten wird.

Ich habe eine Lösung:

"Verflachung" die Linien der einzelnen Dateien (zB conf_1> conf_1_3> conf_1_3_1), einen Brute-Force-Vergleich durchführt (jede Zeile in File1 mit jeder Zeile in File2 Vergleich) und dann die verschiedenen Zeilen erneut einrücken.

Aber ich suche nach effizienteren Lösungen.

Irgendeine Idee?

Vielen Dank im Voraus.

Answer 1

Ich würde vorschlagen, eine 2 hierarchische Listen aufzufüllen und sie rekursiv zu verarbeiten.

Beginnen Sie mit einer einfachen Klasse definieren:

class Node 
{ 
    public string Text; 
    public List<Node> Children; 
} 

Hier die Text soll entfernt, um den Text mit Vertiefung enthalten.

Dann würden Sie zwei Knotenlisten aus Ihren Dateien auffüllen, eine weitere Knotenliste mit Unterschieden erstellen und das Ergebnis in eine andere Datei schreiben. Etwas wie folgt aus:

var nodes1 = ReadNodes(sourceFile1); 
var nodes2 = ReadNodes(sourceFile2); 
var diff = GetDiff(nodes1, nodes2); 
if (diff.Count > 0) 
{ 
    using (var sw = new StreamWriter(diffFile)) 
     WriteDiff(sw, diff); 
} 

Die verwendeten Methoden sind:

static List<Node> ReadNodes(string fileName) 
{ 
    // I'm leaving that part for you 
} 

static List<Node> GetDiff(List<Node> nodes1, List<Node> nodes2) 
{ 
    if (nodes2 == null || nodes2.Count == 0) return null; 
    if (nodes1 == null || nodes1.Count == 0) return nodes2; 
    var map = nodes1.ToDictionary(n => n.Text); 
    var diff = new List<Node>(); 
    foreach (var n2 in nodes2) 
    { 
     Node n1; 
     if (!map.TryGetValue(n2.Text, out n1)) 
      diff.Add(n2); 
     else 
     { 
      var childDiff = GetDiff(n1.Children, n2.Children); 
      if (childDiff != null && childDiff.Count > 0) 
       diff.Add(new Node { Text = n2.Text, Children = childDiff }); 
     } 
    } 
    return diff; 
} 


static void WriteDiff(TextWriter output, List<Node> nodes, int indent = 0) 
{ 
    if (nodes == null) return; 
    foreach (var node in nodes) 
    { 
     for (int i = 0; i < indent; i++) 
      output.Write(' '); 
     output.WriteLine(node.Text); 
     WriteDiff(output, node.Children, indent + 4); 
    } 
} 

-Test mit Ihrem Beispiel:

var nodes1 = new List<Node> 
{ 
    new Node { Text = "conf_1", Children = new List<Node> { 
     new Node { Text = "conf_1_1" }, 
     new Node { Text = "conf_1_2" }, 
     new Node { Text = "conf_1_3", Children = new List<Node> { 
      new Node { Text = "conf_1_3_1" }, 
     } }, 
     new Node { Text = "conf_1_4", Children = new List<Node> { 
      new Node { Text = "conf_1_4_1" }, 
      new Node { Text = "conf_1_4_2" }, 
     } }, 
    }}, 
}; 
var nodes2 = new List<Node> 
{ 
    new Node { Text = "conf_1", Children = new List<Node> { 
     new Node { Text = "conf_1_1" }, 
     new Node { Text = "conf_1_2" }, 
     new Node { Text = "conf_1_3", Children = new List<Node> { 
      new Node { Text = "conf_1_3_1" }, 
      new Node { Text = "conf_1_3_2" }, 
     } }, 
     new Node { Text = "conf_1_4", Children = new List<Node> { 
      new Node { Text = "conf_1_4_1" }, 
      new Node { Text = "conf_1_4_2" }, 
     } }, 
     new Node { Text = "conf_1_5" }, 
    }}, 
}; 
var diff = GetDiff(nodes1, nodes2); 
if (diff.Count > 0) 
{ 
    using (var sw = new StringWriter()) 
    { 
     WriteDiff(sw, diff); 
     Console.WriteLine(sw.ToString()); 
    } 
}