Mikrosaniye doğruluğu ile unix zaman damgasını sıkıştırmak

Question

Mikrosaniye doğruluklu bir gerçek zaman unix zaman damgası dizisinden oluşan bir dosyam var, yani zaman damgaları asla azalmayabilir. Kodlanması/kodu çözülmesi gereken tüm zaman damgaları aynı gündür. Dosyadaki örnek bir giriş, 1364281200.078739 gibi bir e-postadan beri 1364281200078739 usecs karşılık gelen bir şey olabilir. Veri dengesiz aralıklı ve sınırlıdır.

Yaklaşık 10 bit/zaman damgası içeren bir sıkıştırma elde etmem gerekiyor. Şu anda ardışık zaman damgaları arasındaki farkı hesaplayarak ortalama 31 bit/zaman damgası sıkıştırmak mümkün. Daha fazla nasıl geliştirebilirim?

Düzenleme:

Biz (bayt kodlanmış dosyanın Boyut)/(zaman damgaları sayısı) olarak Sıkıştırma derecesi hesaplıyoruz * 8. Zaman damgalarını 'önce' ikiye ayırdım. ve ondan sonra. Tamsayı kısmı oldukça sabittir ve iki tamsayı parçası zaman damgası 32 arasındaki maksimum fark 0-8 bit kullanarak kodlanmıştır. Kesinlik kısmı oldukça rastlantısaldır, bu yüzden önde gelen bitleri yok saydım ve 0-21 bit kullanarak dosyaya yazdım (maksimum 999999 olabilir). Ancak şifrelenmiş dosyamın boyutu 4007674 bayt olarak geliyor ve dolayısıyla 71.05 bit/TS olarak sıkıştırılıyor. Ben de yazarım. ve daha sonra çözmek için iki zaman damgası arasındaki boşluk. Kodlanmış dosya boyutumda nasıl geliştirebilirim? http://pastebin.com/3QJk1NDV maksimum fark/b zaman damgaları olup - - 32.594.136 mikro saniye Burada http://pastebin.com/QBs9Bqv0

mikro saniye içinde diferansiyel damgaları değeri link - Burada

kısmi veri seti için bağlantıdır.

Answer 1

, sizin örnek dosyada bit derinliği başına değerlerin dağılımı aşağıdaki gibidir: Yani

Değerlerin% 52.285'i ya 0 ya da 1'dir, sadece 64'ün altında bir avuç diğer değer (2 ~ 6-bit),% 27.59'u 7 ~ 12-bittir,% 2.1 civarında oldukça eşit bir dağılım vardır. bit başına 20-bit'e kadar ve maksimum 25-bit ile 20-bitlerin sadece% 3'ü. Verilere bakıldığında, 6 ardışık sıfıra kadar birçok dizinin olduğu da açıktır.

 
00 0xxxxx        0 (xxxxx is the number of consecutive zeros) 
00 1xxxxx        1 (xxxxx is the number of consecutive ones) 
01 xxxxxx xxxxxxxx     2-14 bit values 
10 xxxxxx xxxxxxxx xxxxxxxx   15-22 bit values 
11 xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 23-30 bit values 

hızlı bir test bu değil mi damgası başına 13,78 bit sıkıştırma oranı yol açtığını gösterdi:

Bu gözlemler bana böyle bir değişken değer başına bit boyutu, bir şeyi kullanma fikrini verdi Tam olarak hedeflediğin 10 bit, ama basit bir plan için kötü bir başlangıç ​​değil.

---

birkaçı örnek verileri analiz edildikten sonra, bir üst üste 0 ve 1 'S, 0 1 0 gibi kısa dizilerinin bir çok olduğu görülmektedir, böylece bu bir 1 baytlık düzeni ikame:

 
00xxxxxx 00  = identifies a one-byte value 
      xxxxxx = index in the sequence table 

dizilerin

tablo: 451.210 damgaları ile, örneğin dosya için

 
index ~ seq index ~ seq index ~ seq index ~ seq index ~ seq  index ~ seq 
    0  0  2  00  6  000  14 0000  30 00000  62 000000 
    1  1  3  01  7  001  15 0001  31 00001  63 000001 
       4  10  8  010  16 0010  32 00010  
       5  11   ...   ...   ... 
           11  101  27 1101  59 11101  
           12  110  28 1110  60 11110  
           13  111  29 1111  61 11111  

bu 676,418 sayılı belgelerde bayt veya zaman damgası başına 11,99 bit kodlanmış dosya boyutu indirir. Yukarıdaki yöntemin test edilmesi, daha büyük aralıklar arasında 98.578 tek sıfır ve 31.271 tekil olduğunu göstermiştir. Bu yüzden, her bir büyük aralığın 1 bitini bir sıfır ile takip edip etmediğini saklamak için kullanmayı denedim, bu da kodlanmış boyutu 592,315 bayta indirdi. Ve daha büyük aralıkların 0, 1 veya 00 (en sık kullanılan dizi) tarafından takip edilip edilmediğini depolamak için 2 bit kullandığımda, kodlanmış boyut, zaman damgası başına 564,034 bayta veya 10.0004 bit'e düştü.
Daha sonra tek 0'lar ve 1'leri önceki kod yerine (yalnızca kod sadeliği nedeniyle) aşağıdaki büyük aralıkta saklamak için değiştirdim ve bunun, dosya boyutu 563.884 bayt ya da zaman damgası 9.997722 bit biti !

Yani tam bir yöntemdir: bir kodlayıcının

 
Store the first timestamp (8 bytes), then store the intervals as either: 

00 iiiiii        sequences of up to 5 (or 6) zeros or ones 
01 XXxxxx xxxxxxxx      2-12 bit values (2 ~ 4,095) 
10 XXxxxx xxxxxxxx xxxxxxxx   13-20 bit values (4,096 ~ 1,048,575) 
11 XXxxxx xxxxxxxx xxxxxxxx xxxxxxxx 21-28 bit values (1,048,576 ~ 268,435,455) 

iiiiii = index in sequence table (see above) 
XX  = preceded by a zero (if XX=1), a one (if XX=2) or two zeros (if XX=3) 
xxx... = 12, 20 or 28 bit value 

Örnek: Çünkü MinGW'nin/gcc içinde long double output bug arasında

#include <stdint.h> 
#include <iostream> 
#include <fstream> 
using namespace std; 

uint64_t read_timestamp(ifstream& ifile) { // big-endian 
    uint64_t timestamp = 0; 
    uint8_t byte; 
    for (uint8_t i = 0; i < 8; i++) { 
     ifile.read((char*) &byte, 1); 
     if (ifile.fail()) return 0; 
     timestamp <<= 8; timestamp |= byte; 
    } 
    return timestamp; 
} 

uint8_t read_interval(ifstream& ifile, uint8_t *bytes) { 
    uint8_t bytesize = 1; 
    ifile.read((char*) bytes, 1); 
    if (ifile.fail()) return 0; 
    bytesize += bytes[0] >> 6; 
    for (uint8_t i = 1; i < bytesize; i++) { 
     ifile.read((char*) bytes + i, 1); 
     if (ifile.fail()) return 0; 
    } 
    return bytesize; 
} 

void write_seconds(ofstream& ofile, uint64_t timestamp) { 
    long double seconds = (long double) timestamp/1000000; 
    ofile << seconds << "\n"; 
} 

uint8_t write_sequence(ofstream& ofile, uint8_t seq, uint64_t timestamp) { 
    uint8_t interval = 0, len = 1, offset = 1; 
    while (seq >= (offset <<= 1)) { 
     seq -= offset; 
     ++len; 
    } 
    while (len--) { 
     interval += (seq >> len) & 1; 
     write_seconds(ofile, timestamp + interval); 
    } 
    return interval; 
} 

int main() { 
    ifstream ifile ("timestamps.bin", ios::binary); 
    if (! ifile.is_open()) return 1; 
    ofstream ofile ("output.txt", ios::trunc); 
    if (! ofile.is_open()) return 2; 
    ofile.precision(6); ofile << std::fixed; 

    uint64_t timestamp = read_timestamp(ifile); 
    if (timestamp) write_seconds(ofile, timestamp); 

    while (! ifile.eof()) { 
     uint8_t bytes[4], seq = 0, bytesize = read_interval(ifile, bytes); 
     uint32_t interval; 

     if (bytesize == 1) { 
      timestamp += write_sequence(ofile, bytes[0], timestamp); 
     } 
     else if (bytesize > 1) { 
      seq = (bytes[0] >> 4) & 3; 
      if (seq) timestamp += write_sequence(ofile, seq - 1, timestamp); 
      interval = bytes[0] & 15; 
      for (uint8_t i = 1; i < bytesize; i++) { 
       interval <<= 8; interval += bytes[i]; 
      } 
      timestamp += interval; 
      write_seconds(ofile, timestamp); 
     } 
    } 
    ifile.close(); 
    ofile.close(); 
    return 0; 
} 

: bir dekoderin

#include <stdint.h> 
#include <iostream> 
#include <fstream> 
using namespace std; 

void write_timestamp(ofstream& ofile, uint64_t timestamp) { // big-endian 
    uint8_t bytes[8]; 
    for (int i = 7; i >= 0; i--, timestamp >>= 8) bytes[i] = timestamp; 
    ofile.write((char*) bytes, 8); 
} 

int main() { 
    ifstream ifile ("timestamps.txt"); 
    if (! ifile.is_open()) return 1; 
    ofstream ofile ("output.bin", ios::trunc | ios::binary); 
    if (! ofile.is_open()) return 2; 

    long double seconds; 
    uint64_t timestamp; 

    if (ifile >> seconds) { 
     timestamp = seconds * 1000000; 
     write_timestamp(ofile, timestamp); 
    } 

    while (! ifile.eof()) { 
     uint8_t bytesize = 0, len = 0, seq = 0, bytes[4]; 
     uint32_t interval; 

     while (bytesize == 0 && ifile >> seconds) { 
      interval = seconds * 1000000 - timestamp; 
      timestamp += interval; 

      if (interval < 2) { 
       seq <<= 1; seq |= interval; 
       if (++len == 5 && seq > 0 || len == 6) bytesize = 1; 
      } else { 
       while (interval >> ++bytesize * 8 + 4); 
       for (uint8_t i = 0; i <= bytesize; i++) { 
        bytes[i] = interval >> (bytesize - i) * 8; 
       } 
       bytes[0] |= (bytesize++ << 6); 
      } 
     } 
     if (len) { 
      if (bytesize > 1 && (len == 1 || len == 2 && seq == 0)) { 
       bytes[0] |= (2 * len + seq - 1) << 4; 
      } else { 
       seq += (1 << len) - 2; 
       ofile.write((char*) &seq, 1); 
      } 
     } 
     if (bytesize > 1) ofile.write((char*) bytes, bytesize); 
    } 
    ifile.close(); 
    ofile.close(); 
    return 0; 
} 

Örnek 4.8.1 derleyici kullanıyorum, bu geçici çözümü kullanmak zorundaydım: (bu diğer c ile gerekli olmamalıdır gelecek okuyuculara ompilers)

void write_seconds(ofstream& ofile, uint64_t timestamp) { 
    long double seconds = (long double) timestamp/1000000; 
    ofile << "1" << (double) (seconds - 1000000000) << "\n"; 
} 

Not: Bu yöntem, örneğin, veri dosyasının analizine dayanmaktadır; Verileriniz farklıysa aynı sıkıştırma oranını vermez.

Answer 2

Verilerinizdeki farkların bir histogramını görmeden bilmek zor. Farkları kodlamak için Rice Code'u deneyebilirim, farklılıkların dağılımı için en iyi sıkıştırmayı elde etmek için parametreyi seçiyorum.

Answer 3

Eğer mikrosaniye hassasiyetinde kayıpsız sıkıştırma gerekiyorsa, o zaman 10 bit Etkinliklerinizin zamanlaması tesadüfi ise, 1024.

için sayalım unutmayın ve aslında mikrosaniye doğruluğu gerektiğini size spec'ed Bu, farklı zaman damgalarınızın 10 bit/etkinlik bütçenizi aşmadan yaklaşık 1 milisaniyeden fazla bir değere sahip olamayacağı anlamına gelir.

Verilerinize hızlı bir şekilde göz attığınızda, muhtemelen 10 bit/zaman damgası oluşturamazsınız. Bununla birlikte, farklılığınız ilk adımdır ve 31 bit'ten daha iyi bir performans sergileyebilirsiniz - örnek veri kümesinde istatistik yapar ve bu dağılımı yansıtan bir ikili önek kodlaması seçerim.

Kodunuzun, gerekiyorsa büyük boşlukları kodlama alanı olduğundan emin olmalısınız, bu nedenle bir universal code ürününü temel almayı düşünün. Her zaman damgası ile eskisi arasındaki aralığı alıp (yani tamsayılar gibi) mikrosaniye içinde bunu ifade ederse