Levenshtein Algorithme de type distance pour différencier les objets en mémoire?

Question

Java 8 ici, bien que cette réponse devrait s'appliquer à tout lang.

J'ai un problème où je dois comparer à des objets, disons, Widgets et produire un « diff » entre eux: qui est, un ensemble de mesures qui, si elles sont suivies, transformera une Widget (la source ) dans l'autre (cible).

class Widget { 
    // Properties and such. 
} 

class WidgetDiffer extends Differ<Widget> { 
    List<Transformation> diff(Widget source, Widget target) { 
     // The produced list will convert source to target, if executed 
     // by some runtime. 
    } 
} 

class WidgetTransformer extends Transformer<Widget> { 
    @Override 
    Widget transformSourceToTarget(Widget source, List<Transformation> transforms) { 
     // Somehow, run 'transforms' on 'source', which *should* 
     // produce an object with the same state/properties as 
     // the original target. 
    } 
} 

Je suis au courant de l'algorithme Levenshtein Distance pour les transformations des chaînes, mais:

• C'est juste pour les chaînes, pas Widgets; et
• Il vous donne seulement un entier (nombre de transformations nécessaires pour transformer l'évier dans la cible), alors que je besoin d'un List<Transformation> qui, lorsqu'il est exécuté par un moteur, se source vers la cible

Je suis Je me demande s'il existe des algorithmes connus pour effectuer ce type d'opérations. Une chance que ces algorithmes vivent dans une bibliothèque quelque part?!?

Answer 1

Je le vois comme un problème de recherche. Construire un graphique où le nœud de destination est le widget désiré et le nœud de départ est le widget à transformer. Chaque étape (arête dans le graphique) représente une transformation possible du widget (ajout ou suppression de propriétés). Une fois que le graphe est construit, exécutez DFS avec le chemin d'extraction et vous obtiendrez les étapes nécessaires pour transformer le widget de départ en celui désiré (ce sera également le nombre minimum d'étapes nécessaires).

Answer 2

Si les widgets ne sont que des key-> value bags, le problème est assez simple.

Voici un JavaScript (vous pouvez l'utiliser comme code pseudo pour la mise en œuvre Java).

function diff(src, target) { 
    var result = []; 
    for(var key in src) { 
    if(key in target) { 
     if(src[key] !== target[key]) { 
     result.push({op:"update", name:key, value:target[key]}); 
     } 
    } else { 
     result.push({op:"delete", name:key}); 
    } 
    } 
    for(var key in target) { 
    if(!(key in src)) { 
     result.push({op:"add", name:key, value:target[key]}); 
    } 
    } 
    return result; 
} 

console.log(JSON.stringify(diff({}, {a:1, b:2, c:3}))); 
console.log(JSON.stringify(diff({a:1, b:2, c:3}, {}))); 
console.log(JSON.stringify(diff({a:1, b:2, c:3}, {b:20, c:30, d:40}))); 

O (srcPropCount * lookupTargetProp + targetPropCount * lookupSrcPropCount)

Les seules opérations sont Ajouter une nouvelle propriété, mettre à jour une propriété existante et supprimer une propriété.