Approccio euristico per implementazione flessibile DIFF

12

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.

    
posta ptpaterson 11.03.2014 - 17:39
fonte

1 risposta

1

Potresti farlo in una versione simile a Vimdiff:

Passaggio 1: identificazione delle frasi aggiunte, cancellate e modificate.

Passaggio 2: per ogni frase modificata, individua la prima e l'ultima parola cambiate e taglia qualsiasi cosa che non sia tra queste due parole.

Se hai bisogno di mantenere una struttura grammaticale coerente, guarda l'interno del link o un altro mostrato su questo post .

Informazioni sulla presentazione: puoi presentare entrambe le versioni di quella frase una sotto l'altra. Potresti voler mostrare il contesto per ogni cambiamento. Per l'ispirazione, guarda latexdiff che può stampare il testo aggiunto in blu al posto finale nella versione finale del testo e il testo eliminato in note a piè di pagina (anche compatibile con \usepackage[para]{footmisc} ).

    
risposta data 27.03.2014 - 17:17
fonte

Leggi altre domande sui tag