كيف يعمل إلغاء ضغط القيمة لـ Facebook's Gorilla في حالة عدم تخزين عدد الأصفار البادئة

Question

وأشير إلى هذه الورقة: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

سؤالي يتعلق بالقسم 4.1.2 حيث يقول:

عندما يكون XOR غير صفري ، قم بحساب عدد الأصفار الرائدة والمتزايدة في XOR ، وتخزين بت '1' تليها إما a) أو b):

(أ) (البت التحكم "0") إذا كانت كتلة البتات ذات مغزى تندرج داخل كتلة البتات ذات المغزى السابق ، أي على الأقل ، فهناك العديد من الأصفار الرائدة وأكبر عدد من الأصفار المتأخرة كما هو الحال مع القيمة السابقة وضع الكتلة وتخزين القيمة xored ذات مغزى.

عند فك الضغط، كيف نعرف إذا كان علينا إضافة أصفار بادئة أم أصفار لاحقة؟على سبيل المثال لنفترض أن لدينا أرقام 48 بت التالية:

A = 0xfff ffff fffff
B = 0xfff 0000 fffff
C = 0xfff 0ff0 fffff

و

A xor B = 0x000 ffff 00000

B xor C = 0x000 0ff0 00000

إذا اتبعنا خوارزمية الضغط لـ A xor B سنقوم بتخزين عدد الأصفار البادئة، وهو 12, ، وكذلك الأجزاء ذات المعنى ffff.

الآن ل B xor C نظرًا لأن "هناك على الأقل عددًا من الأصفار البادئة وعددًا من الأصفار اللاحقة كما هو الحال مع القيمة السابقة"، لذلك نقوم فقط بتخزين البتات ذات المعنى ff.عندما أريد فك التشفير ff, استنادًا إلى البتات المضغوطة السابقة، أعلم أن لدي ما لا يقل عن 12 صفرًا بادئًا و 20 صفرًا ذيلًا، لكن ما زلت بحاجة لملء 8 أصفار؛هل علي ان افعل ff00 أو 00ff أو مزيج آخر؟

Answer 1

لقد وجدت إجابتي بعد قراءة التنفيذ المرجعي: https://github.com/facebookarchive/beringei/blob/92784ec6e22572f28500c76b669276007635c875/beringei/lib/TimeSeriesStream.cpp

إن استخدام مصطلح "الأجزاء ذات المغزى" في الورقة غامض.اعتقدت أن الجملة "استخدم هذه المعلومات لموضع الكتلة وقم بتخزين القيمة Xored ذات مغزى." يعني تخزين البتات الجميع تمت إزالة الأصفار الزائدة والبادئة لأن "قيمة XORed ذات المعنى" هي قيمة لا تحتوي على صفر بادئ وزائد.ولكن، وفقًا للتنفيذ المرجعي، فإنك تقوم فقط بإزالة نفس القدر من الأصفار البادئة والزائدة مثل دلتا القيمة السابقة؛قد تظل البتات ذات المعنى في هذه الحالة تحتوي على بعض الأصفار البادئة والزائدة.

لذا، على سبيل المثال في السؤال، يجب علينا تخزين 0ff0 كأجزاء ذات معنى بدلاً من مجرد ff.