Różnicowanie danych - Data differencing

W informatyce i teorii informacji , różnicowych danych lub różnica kompresja produkuje opis techniczny różnicy pomiędzy dwoma zestawami danych - źródło i cel. Formalnie algorytm różnicowania danych przyjmuje jako wejściowe dane źródłowe i docelowe i wytwarza dane różnicowe w taki sposób, że mając dane źródłowe i dane różnicowe, można zrekonstruować dane docelowe („ załatanie ” źródła różnicą w celu uzyskania celu) .

Przykłady

Jednym z najbardziej znanych przykładów różnicowania danych jest narzędzie diff , które tworzy różnice między wierszami w plikach tekstowych (oraz w niektórych implementacjach, plikach binarnych , będąc w ten sposób narzędziem różnicowania ogólnego przeznaczenia). Różnicowanie ogólnych plików binarnych podlega pod rubrykę kodowania delta , a szeroko stosowanym przykładem jest algorytm używany w rsync . Standardowym formatem różnicowania generycznego jest VCDIFF , zaimplementowany w takich narzędziach jak Xdelta w wersji 3. Program różnicujący o wysokiej wydajności (małe pliki łatek) to bsdiff, który używa bzip2 jako ostatniego kroku kompresji wygenerowanej delty.

Obawy

Główne problemy związane z różnicowaniem danych to użyteczność i oszczędność miejsca (rozmiar poprawki).

Jeśli ktoś chce po prostu zrekonstruować cel mając dane źródło i łatę, może po prostu dołączyć cały cel do łaty i „zastosować” łatę przez odrzucenie źródła i wysłanie celu, który został zawarty w łacie; podobnie, jeśli źródło i cel mają ten sam rozmiar, można utworzyć prostą łatkę przez XORing źródła i celu. W obu tych przypadkach łata będzie tak duża jak cel. Jak pokazują te przykłady, jeśli jedynym problemem jest rekonstrukcja celu, można to łatwo zrobić kosztem dużej łaty, a głównym problemem dla różnicowania binarnego ogólnego przeznaczenia jest zmniejszenie rozmiaru łaty.

Zwłaszcza w przypadku danych strukturalnych istnieją inne obawy, które w dużej mierze należą do „użyteczności” – na przykład, jeśli porównujemy dwa dokumenty, zazwyczaj chcemy wiedzieć, które sekcje uległy zmianie lub jeśli niektóre sekcje zostały przeniesione – chcemy zrozumieć, w jaki sposób dokumenty różnią. Na przykład „tutaj 'kot' zmieniono na 'pies', a paragraf 13 został przeniesiony do paragrafu 14”. Można również chcieć mieć solidne różnice – na przykład, jeśli dwa dokumenty A i B różnią się w paragrafie 13, można chcieć zastosować tę łatkę, nawet jeśli zmieniono paragraf 7 A. Przykład tego znajduje się w diff , który pokazuje, które wiersze uległy zmianie i gdzie format kontekstu zapewnia niezawodność i poprawia czytelność dla człowieka.

Inne obawy dotyczą wydajności obliczeniowej, jak w przypadku kompresji danych – znalezienie małej łatki może być bardzo czasochłonne i wymagające dużej ilości pamięci.

Najlepsze wyniki uzyskuje się, gdy ktoś ma wiedzę na temat porównywanych danych i innych ograniczeń: diff jest przeznaczony dla plików tekstowych zorientowanych liniowo, szczególnie kodu źródłowego, i działa z nimi najlepiej; rsync algorytm jest stosowany w oparciu o źródłowy i docelowy jest w sieci od siebie, a komunikacja jest powolny, więc minimalizuje dane, które muszą zostać przekazane; a aktualizacje dla Google Chrome wykorzystują algorytm dostosowany do archiwum i formatu wykonywalnego danych programu.

Połączenie z kompresją danych

Kompresja danych może być postrzegana jako szczególny przypadek różnicowania danych – różnicowanie danych polega na tworzeniu różnicy dla źródła i celu , z łataniem tworzącym cel dla źródła i różnicy, podczas gdy kompresja danych polega na tworzeniu skompresowanego pliku o określonej cel, a dekompresja polega na stworzeniu celu na podstawie tylko skompresowanego pliku. Można więc uznać kompresję danych za różnicowanie danych z pustymi danymi źródłowymi, skompresowany plik odpowiadający "różnicy od niczego". Jest to to samo, co rozważanie entropii bezwzględnej (odpowiadającej kompresji danych) jako szczególnego przypadku entropii względnej (odpowiadającej różnicowaniu danych) bez danych początkowych.

Kiedy ktoś chce podkreślić połączenie, może użyć terminu kompresja różnicowa w odniesieniu do różnicowania danych.

Słownik tłumaczący terminologię obu dziedzin podaje się jako:

Bibliografia