Stworzyłem implementację DIFF, aby porównać wersje dokumentów w pracy. Opiera się na algorytmie różnicowym O (ND) i jego odmianach .
Ważną rzeczą stało się wzięcie listy zmian i zinterpretowanie ich w postaci tekstu czytelnego dla człowieka. Chociaż obecny algorytm jest bardzo wydajny, jest tak bardzo, że trudno jest go rozwinąć.
Krótkie pytanie
Myślałem o próbie użycia A * i heurystyki, która dodaje kary za „zakręty”. Chodzi o to, aby wygładzić niepotrzebne „dodawanie, usuwanie, dodawanie, usuwanie, dodawanie, usuwanie”, aby łatwiej było parsować w coś, co człowiek może przeczytać. Zasadniczo zmień mój najkrótszy problem ścieżki na najprostszy problem ścieżki .
I oczywiście nie twórz wyników, które zawsze brzmią: „Usuń wszystko , Dodaj wszystko ”
Czy to brzmi rozsądnie?
Czy istnieje jakikolwiek priorytet w stosowaniu heurystyki w implementacji DIFF? Co to jest heurystyka?
Problem:
Jeśli długie zdanie zostanie usunięte, a inne długie zdanie zostanie usunięte, ale mają one co najmniej jedno słowo, powiedz „z”. Pozostawienie wspólnego słowa w spokoju (nie przez dodanie i usunięcie go) stworzy najkrótszą ścieżkę. Jednak to naprawdę zaciemnia kontekst zmiany dla człowieka, który próbuje odczytać wydruk zmian.
Przykład z bieżącym DIFF:
- Stary tekst: Czyszczenie: Pranie w proszku i suszenie powietrzem sklepowym.
- Nowy tekst: Czyszczenie: Przecierać acetonem i niestrzępiącą się szmatką.
- Zmień listę notatek:
- Zmień „Pranie i suszenie” na „Przetrzyj acetonem”
- Zmień „powietrze sklepowe” na „aceton i niestrzępiącą się szmatkę”
Uwaga: zamiast „usuń” shop air należy dodać „Zmień” , dodać „aceton” ”
Jak widać, druga nuta traci WSZYSTKO i bez patrzenia na pełne stare i nowe zestawy tekstów nie można zrozumieć, co to znaczy.
Uwaga na temat interpunkcji:
Interpunkcję wyznaczyłem jako osobne „słowa”, aby je uzyskać
- Dodaj "("
zamiast
- Zmień „Napraw” na „(Napraw”
ponieważ to było okropne. Oznacza to jednak, że jeśli w obu tekstach występuje przecinek (w przeciwieństwie do słowa „z” w poprzednim przykładzie), dzieje się to samo.
Możliwe rozwiązanie:
Myślę, że mógłbym zamiast tego użyć innego algorytmu znajdowania ścieżek, który dałby mi elastyczność w dodawaniu wagi do różnych „ścieżek” zmian, które mogłyby mieć sens dla osoby. Może mógłbym nawet sprawić, że podróżowanie do węzłów zawierających znaki interpunkcyjne będzie miało niewielką wagę (nie jestem pewien, jak to wpłynie na inne rzeczy).
Następnie mógłbym pobrać poprzedni przykład z listą następujących elementów:
- Zmień listę notatek:
- Zmień „Prać proszkowo i wysuszyć powietrzem sklepowym” na „Przecierać acetonem i niestrzępiącą się szmatką”
Widzieć! O wiele jaśniej!
Wiem, że wybrałbym hit wydajnościowy i być może będę musiał dokonać dość gruntownego przeglądu mojego programu, ale ważniejsze jest, aby uzyskać końcowy wynik, jaki chcę.
Dolna linia:
Ponownie, czy istnieje jakikolwiek precedens dla stosowania heurystyki w implementacji DIFF i co to jest?
Inne przemyślenia? Rozsądna inwestycja czasu? Inne pomysły? Inne algorytmy?
Z góry dziękuję!
EDYTOWAĆ:
Próbowałem wyjaśnić / zestalić moje pytanie i uogólnić moje pytanie na dodanie heurystyki do mojego algorytmu, zamiast używać A *. Zasadniczo to samo w tym przypadku, ale nadal uważam, że bardziej dokładne. Ten post był wnikliwy.
źródło