Ho creato un'implementazione DIFF per confrontare le revisioni dei documenti al lavoro. È basato su Un algoritmo di differenza O (ND) e le sue varianti .
Una cosa che è diventata importante è prendere la lista dei cambiamenti e interpretarli in un testo leggibile. Sebbene l'algoritmo attuale sia molto efficiente, è talmente tanto che è difficile espandersi.
Breve domanda
Stavo pensando di provare a usare A * e un euristico che aggiunge penalità per i "turni". L'idea di appianare non è necessaria "aggiungere, eliminare, aggiungere, eliminare, aggiungere, eliminare" in modo che sia più facile analizzare in qualcosa che un essere umano può leggere. In pratica, trasforma il mio problema percorso più breve in un percorso più semplice problema.
E ovviamente non creare output che sia sempre "Elimina tutto , Aggiungi tutto "
Suona ragionevole?
C'è qualche precedenza nell'usare un'euristica in un'implementazione DIFF? Cos'è l'euristico?
Il problema:
Se una frase lunga viene cancellata e un'altra frase lunga viene rimossa, ma condividono almeno una parola, pronunciare "con". Lasciare la parola comune da sola (non aggiungendola e cancellandola) creerà il percorso più breve. Tuttavia, questo in realtà offusca il contesto del cambiamento di un essere umano cercando di leggere una stampa dei cambiamenti.
Esempio con DIFF corrente:
- Vecchio testo: Pulisci: Powerwash e asciuga con aria da negozio.
- Nuovo testo: Pulisci: pulisci con acetone e un panno privo di lanugine.
-
Modifica elenco note:
- Cambia "Powerwash and blow dry" in "Wipe with acetone"
- Cambia "shop air" in "acetone e un panno privo di lanugine"
Nota: "Cambia" è usato al posto di "cancella 'shop air', aggiungi 'acetone'"
Come puoi vedere, la seconda nota perde TUTTO il contesto e senza guardare ancora i set di testo completi vecchi e nuovi non riesci a capire cosa significhi.
Nota sulla punteggiatura:
Ho delimitato la punteggiatura come "parole" separate in modo da ottenere
- Aggiungi "("
invece di
- Cambia "Ripara" in "(Ripara"
perché questo era odioso. Tuttavia, ciò significa che se c'è anche una virgola in entrambi i testi (al contrario della parola "con" nell'esempio precedente) accade la stessa cosa.
Soluzione possibile:
Penso che potrei utilizzare un algoritmo di individuazione dei percorsi diverso che può darmi la flessibilità di aggiungere peso a diversi "percorsi" di cambiamento che potrebbero avere più senso per una persona. Forse, potrei persino fare in modo che viaggiare verso i nodi che contengono la punteggiatura abbiano poco peso (non sono sicuro di come questo potrebbe avere effetto su altre cose).
Quindi potrei ottenere l'esempio precedente per elencare quanto segue:
-
Modifica elenco note:
- Modifica "Lavaggio e asciugatura con aria compressa" su "Pulisci con acetone e un panno privo di lanugine"
Vedi! Molto più chiaro!
So che prenderei un successo in termini di prestazioni, e potrei dover fare una revisione abbastanza importante del mio programma, ma è più importante avere il risultato finale che voglio.
Bottom Line:
Anche in questo caso, esiste una precedenza per l'utilizzo di un'euristica in un'implementazione DIFF, e di cosa si tratta?
Altri pensieri? Un investimento di tempo ragionevole? Altre idee? Altri algoritmi?
Grazie in anticipo!
Modifica
Ho provato a chiarire / consolidare la mia domanda e generalizzare la mia domanda ad aggiungere un'euristica al mio algoritmo, piuttosto che usare A *. Fondamentalmente la stessa cosa in questo caso, ma penso ancora più preciso ora. questo post è stato approfondito.