ترميز ليفينشتاين

ترميز ليفينشتاين  هو أحد أنواع الترميز العامة للأعداد غير السالبة. طُوِّر على يد .

 الترميز 
يرمز الصفر ب "0"، بينما لترميز الأرقام الموجبة تتم عبر:
 تهيئة متغير عداد الخطوة وليكن C بالعدد 1.
 كتابة التمثيل الثنائي للرقم 1 في بداية البرنامج (الكود).
 اجعل M تمثل البتات الموافقة للرقم في الخطوة رقم 2.
 إذا لم تكن M صفراً، قم بزيادة C، ومن ثم أعد الخطوة 2 مع رقم M جديد.
 اجعل C صفراً في بداية البرمجة، ومن ثم لتصبح C هي البتات "1".

 الرقم  الترميز  الاحتمال المضمن 0  0  1/2 1  10  1/4 2  110 0  1/16 3  110 1  1/16 4  1110 0 00  1/128 5  1110 0 01  1/128 6  1110 0 10  1/128 7  1110 0 11  1/128 8  1110 1 000  1/256 9  1110 1 001  1/256 10  1110 1 010  1/256 11  1110 1 011  1/256 12  1110 1 100  1/256 13  1110 1 101  1/256 14  1110 1 110  1/256 15  1110 1 111  1/256 16  11110 0 00 0000  1/4096 17  11110 0 00 0001  1/4096
لفك الترميز يكون عبر:
 أضف عداداً يعد عدد البتات "1" حتى يتم العثور على "0".
 إذا كان العدد في العداد صفرًا ، تكون القيمة صفرًا، وإلا
 ابدأ بالمتغير N، واضبطه على القيمة 1 وكرر العد مطروحًا منه 1 مرة:
 قم بقراءة N بت ، قبل "1" ، ثم قم بتعيين القيمة الناتجة إلى N.
يكون ترميز ليفينشتاين أطول ببت عن  لذات العدد، لكن الفرق أن ترميز ليفينشتاين يرمز الرقم 0 فيما يزيح ترميز إلياس أوميغا عنه ويبدأ من الواحد.

 برنامج 
 مثال تطبيقي بلغة ++C 
 الترميز 
void levenshteinEncode(char* source, char* dest)
{
    IntReader intreader(source);
    BitWriter bitwriter(dest);
    while (intreader.hasLeft())
    {
        int num = intreader.getInt();
        if (num == 0)
            bitwriter.outputBit(0);
        else
        {
            int c = 0;
            BitStack bits;
            do {
                int m = 0;
                for (int temp = num; temp > 1; temp>>=1)  // calculate floor(log2(num))
                    ++m;
                for (int i=0; i < m; ++i)
                    bits.pushBit((num >> i) & 1);
                num = m;
                ++c;
            } while (num > 0);
            for (int i=0; i < c; ++i)
                bitwriter.outputBit(1);
            bitwriter.outputBit(0);
            while (bits.length() > 0)
                bitwriter.outputBit(bits.popBit());
        }
    }
}

 فك الترميز 
void levenshteinDecode(char* source, char* dest)
{
    BitReader bitreader(source);
    IntWriter intwriter(dest);
    while (bitreader.hasLeft())
    {
        int n = 0;
        while (bitreader.inputBit())     // potentially dangerous with malformed files.
            ++n;
        int num;
        if (n == 0)
            num = 0;
        else
        {
            num = 1;
            for (int i = 0; i < n-1; ++i)
            {
                int val = 1;
                for (int j = 0; j < num; ++j)
                    val = (val << 1) | bitreader.inputBit();
                num = val;
            }
        }
        intwriter.putInt(num);           // write out the value
    }
    bitreader.close();
    intwriter.close();
}

 المراجع 

*
تصنيف:أنظمة عددية
تصنيف:برمجة
تصنيف:تخزين بيانات الحاسوب
تصنيف:خوارزميات ضغط بيانات غير مضيعة