Delta kodlaması - Delta encoding

Delta kodlama , tam dosyalar yerine sıralı veriler arasındaki farklar (deltalar) biçimindeki verileri depolamanın veya iletmenin bir yoludur ; daha genel olarak bu, veri farkı olarak bilinir . Delta kodlamaya bazen delta sıkıştırması denir , özellikle de değişikliklerin arşiv geçmişinin gerekli olduğu durumlarda (örneğin, revizyon kontrol yazılımında ).

Farklar, "deltas" veya "diffs" adı verilen ayrı dosyalara kaydedilir. Farkların küçük olduğu durumlarda (örneğin, büyük bir belgedeki birkaç kelimenin değişmesi veya büyük bir tablodaki birkaç kaydın değişmesi) delta kodlaması, veri fazlalığını büyük ölçüde azaltır. Benzersiz delta koleksiyonları, kodlanmamış eşdeğerlerinden önemli ölçüde daha fazla alan verimlidir.

Mantıksal bir bakış açısından, iki veri değeri arasındaki fark, bir değeri diğerinden elde etmek için gereken bilgidir – bkz. bağıl entropi . Özdeş değerler arasındaki fark (bazı denklikler altında ) genellikle 0 veya nötr eleman olarak adlandırılır .

Basit örnek

Belki de en basit örnek, bayt değerlerini, değerlerin kendisinden ziyade sıralı değerler arasındaki farklar (deltalar) olarak depolamaktır. Yani 2, 4, 6, 9, 7 yerine 2, 2, 2, 3, −2'yi kaydederiz. Bu , komşu örnekler ilişkilendirildiğinde değerlerin varyansını (aralığı) azaltır ve aynı veriler için daha düşük bit kullanımına olanak tanır. IFF 8SVX ses formatı, sıkıştırma uygulamadan önce bu kodlamayı ham ses verilerine uygular. Ne yazık ki, 8 bitlik ses örneklerinin tümü bile delta kodlandığında daha iyi sıkıştırmaz ve delta kodlamanın kullanılabilirliği 16 bit ve daha iyi örnekler için daha da küçüktür. Bu nedenle, sıkıştırma algoritmaları genellikle yalnızca sıkıştırma, olmamasından daha iyi olduğunda delta kodlamayı seçer. Ancak video sıkıştırmada delta çerçeveler çerçeve boyutunu önemli ölçüde azaltabilir ve hemen hemen her video sıkıştırma kodeğinde kullanılır .

Tanım

Bir delta, simetrik delta ve yönlendirilmiş delta olmak üzere 2 şekilde tanımlanabilir . Bir simetrik delta olarak ifade edilebilir

\Delta (v_{1},v_{2})=(v_{1}\setminus v_{2})\cup (v_{2}\setminus v_{1}),

nerede ve iki versiyonu temsil eder. $v_{1}$ $v_{2}$

Bir yönlendirilmiş ö da bir değişiklik olarak adlandırılan, bir uyarlamada uygulandığında (temel) değiştirme işlemleri dizisidir , başka bir versiyonunu elde edilir (yazışmalar not işlem günlükleri veritabanlarında). Bilgisayar uygulamalarında, genellikle iki komutlu bir dil biçimini alırlar: v1'den verileri kopyala ve değişmez verileri yaz . $v_{1}$ $v_{2}$

Varyantlar

Arasındaki farkları kodlayan delta kodlaması bir varyasyonu önekleri veya son ekler arasında dizeleri adlandırılır artan kodlama . Özellikle bir sözlükten sözcük listesi gibi dizeler arasında küçük farklar bulunan sıralanmış listeler için etkilidir .

Uygulama sorunları

Kodlanacak verilerin doğası, belirli bir sıkıştırma algoritmasının etkinliğini etkiler.

Delta kodlama, veriler küçük veya sabit değişkenliğe sahip olduğunda en iyi performansı gösterir; sıralanmamış bir veri seti için, bu yöntemle sıkıştırma mümkün olmayabilir veya çok az olabilir.

İletişim kanalının her iki ucunda dosyanın yalnızca tek bir kopyasının bulunduğu bir ağ üzerinden delta kodlu iletimde , dosyanın önceki sürümünden bu yana hangi bölümlerinin değiştiğini tespit etmek için özel hata kontrol kodları kullanılır. Örneğin, rsync , Mark Adler'in adler-32 sağlama toplamını temel alan bir yuvarlanan sağlama toplamı algoritması kullanır .

Örnek C kodu

Aşağıdaki C kodu, bir dizi karakter üzerinde basit bir delta kodlama ve kod çözme biçimi gerçekleştirir:

void delta_encode(unsigned char *buffer, int length)
{
    unsigned char last = 0;
    for (int i = 0; i < length; i++)
    {
        unsigned char current = buffer[i];
        buffer[i] = current - last;
        last = current;
    }
}

void delta_decode(unsigned char *buffer, int length)
{
    unsigned char last = 0;
    for (int i = 0; i < length; i++)
    {
        unsigned char delta = buffer[i];
        buffer[i] = delta + last;
        last = buffer[i];
    }
}

Örnekler

HTTP'de Delta kodlaması

Delta kodlamanın başka bir kullanım örneği, HTTP sunucularının güncellenmiş Web sayfalarını sürümler arasındaki farklar (deltalar) biçiminde gönderebilmesi gerektiğini öneren RFC 3229 , " HTTP'de delta kodlaması " dır. sayfalar tekrar tekrar tamamen yeniden yazılmak yerine zaman içinde yavaş değişir:

Bu belge, delta kodlamanın HTTP/1.1'e uyumlu bir uzantı olarak nasıl desteklenebileceğini açıklar.

Birçok HTTP (Köprü Metni Aktarım Protokolü) isteği, istemcinin zaten bir önbellek girdisine sahip olduğu biraz değiştirilmiş kaynak örneklerinin alınmasına neden olur. Araştırmalar, bu tür değiştirme güncellemelerinin sık olduğunu ve değişikliklerin genellikle gerçek varlıktan çok daha küçük olduğunu göstermiştir. Bu gibi durumlarda HTTP, kaynağın yeni örneğinin tamamı yerine değişikliklerin minimum bir tanımını aktarabilseydi ağ bant genişliğini daha verimli kullanırdı.

[...] Bu belgede daha sonra açıklanan "örnek işleme" çerçevesini kullanarak rsync'i desteklemenin mümkün olabileceğine inanıyoruz, ancak bu ayrıntılı olarak ele alınmadı.

Önerilen rsync tabanlı çerçeve, rproxy sisteminde bir çift HTTP proxy'si olarak uygulandı . Temel vcdiff tabanlı uygulama gibi, her iki sistem de nadiren kullanılır.

Delta kopyalama

Delta kopyalama , hedef konumda önceki bir sürüm varken kısmen değiştirilmiş bir dosyayı kopyalamanın hızlı bir yoludur. Delta kopyalama ile dosyanın yalnızca değiştirilen kısmı kopyalanır. Genellikle yedekleme veya dosya kopyalama yazılımlarında, özel bir ağ veya internet üzerinden bilgisayarlar arasında kopyalama yaparken bant genişliğinden tasarruf etmek için kullanılır . Dikkate değer bir açık kaynak örneği rsync'dir .

Çevrimiçi yedekleme

Birçok çevrimiçi yedekleme hizmetleri genellikle sadece olarak bilinen bu yöntem, kabul deltaları kendi kullanıcılarına önceki yedeklerden aynı dosyanın önceki sürümlerini verebilmek için. Bu, yalnızca farklı sürümler olarak depolanması gereken veri miktarında (bir dosyanın değiştirilen her sürümünün tamamı kullanıcıların erişimine sunulması gerektiğinden) ilişkili maliyetleri değil, aynı zamanda yükleme (ve bazen güncellenen her dosyanın indirilmesi (tüm dosya yerine yalnızca daha küçük deltanın kullanılması gerekir).

Delta güncellemeleri

Büyük yazılım paketleri için, sürümler arasında genellikle çok az veri değiştirilir. Birçok satıcı zamandan ve bant genişliğinden tasarruf etmek için delta aktarımlarını kullanmayı tercih eder.

Fark

Diff, çoğunlukla metin dosyaları için kullanılan bir dosya karşılaştırma programıdır. Varsayılan olarak, tersine çevrilebilir simetrik deltalar oluşturur. Yazılım yamaları için kullanılan iki biçim , bağlam ve birleşik , satır numarasındaki kaymalara izin veren ek bağlam satırları sağlar.

Git

Git kaynak kodu kontrol sistemi, yardımcı bir " git yeniden paketleme " işleminde delta sıkıştırması kullanır . Depodaki henüz delta sıkıştırılmamış nesneler ("gevşek nesneler"), diğer tüm nesnelerin buluşsal olarak seçilen bir alt kümesiyle karşılaştırılır ve ortak veriler ve farklılıklar, daha sonra geleneksel kullanılarak sıkıştırılan bir "paket dosyası" içinde birleştirilir. yöntemler. Kaynak veya veri dosyalarının taahhütler arasında aşamalı olarak değiştirildiği yaygın kullanım durumlarında bu, önemli ölçüde alan tasarrufu sağlayabilir. Yeniden paketleme işlemi tipik olarak , gevşek nesnelerin veya paket dosyalarının sayısı yapılandırılmış eşikleri aştığında otomatik olarak tetiklenen " git gc " işleminin bir parçası olarak gerçekleştirilir .

Format, Git belgelerinin paket formatı sayfasında belgelenmiştir. Yönlendirilmiş bir delta uygular.

VCDIFF

Yönlendirilmiş delta kodlaması için genel bir format, RFC 3284'te açıklanan VCDIFF'dir . Ücretsiz yazılım uygulamaları arasında Xdelta ve open-vcdiff bulunur.

GDIFF

Genel Fark Biçimi (GDIFF), başka bir yönlendirilmiş delta kodlama biçimidir. 1997'de W3C'ye sunuldu . Birçok durumda VCDIFF, GDIFF'den daha iyi sıkıştırma oranına sahiptir.

bsdiff

Bsdiff, sonek sıralama kullanan bir ikili fark programıdır . İşaretçi adreslerinde birçok değişiklik içeren yürütülebilir dosyalar için, VCDIFF tipi "kopyalama ve değişmez" kodlamalardan daha iyi performans gösterir. Amaç, derleme kodunu ayrıştırmaya gerek kalmadan küçük bir fark oluşturmanın bir yolunu bulmaktır (Google'ın Kabak'ında olduğu gibi). Bsdiff bunu, hatalarla "kopyalama" eşleşmelerine izin vererek başarır, bunlar daha sonra fazladan bir "ekleme" bayt farklılıkları dizisi kullanılarak düzeltilir. Bu dizi, ofset değişiklikleri için çoğunlukla sıfır veya tekrarlanan değerler olduğundan, sıkıştırmadan sonra çok az yer kaplar.

Bsdiff, delta güncellemeleri için kullanışlıdır. Google, Chromium ve Android'de bsdiff kullanır. Deltarpm özelliği RPM Paket Yöneticisi eşleşmesi için bir karma tablo kullanabilirsiniz ağır modifiye bsdiff dayanmaktadır. FreeBSD ayrıca güncellemeler için bsdiff kullanır.

2005 yılında bsdiff'in 4.3 sürümünden bu yana, onun için çeşitli iyileştirmeler veya düzeltmeler yapılmıştır. Google, ürünlerinin her biri için kodun birden çok sürümünü tutar. FreeBSD, başta bir güvenlik açığı düzeltmesi ve daha hızlı divsufsortson ek sıralama rutinine geçiş olmak üzere Google'ın uyumlu değişikliklerinin çoğunu alır . Debian'ın programda bir dizi performans ayarı var.

ddelta , Debian'ın delta güncellemelerinde kullanılması önerilen bsdiff'in yeniden yazılmış halidir. Diğer verimlilik iyileştirmelerinin yanı sıra, bellek ve CPU maliyetini azaltmak için kayan bir pencere kullanır.

Ayrıca bakınız

Referanslar

Dış bağlantılar

RFC 3229 – HTTP'de Delta Kodlama

Languages

In other projects