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

ترميز ليفينشتاين (بالإنجليزية: Levenshtein coding)‏ هو أحد أنواع الترميز العامة للأعداد غير السالبة. طُوِّر على يد فلاديمير ليفينشتاين .

الترميز

يرمز الصفر ب "0"، بينما لترميز الأرقام الموجبة تتم عبر:

1. تهيئة متغير عداد الخطوة وليكن C بالعدد 1.
2. كتابة التمثيل الثنائي للرقم 1 في بداية البرنامج (الكود).
3. اجعل M تمثل البتات الموافقة للرقم في الخطوة رقم 2.
4. إذا لم تكن M صفراً، قم بزيادة C، ومن ثم أعد الخطوة 2 مع رقم M جديد.
5. اجعل 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. أضف عداداً يعد عدد البتات "1" حتى يتم العثور على "0".
2. إذا كان العدد في العداد صفرًا ، تكون القيمة صفرًا، وإلا
3. ابدأ بالمتغير N، واضبطه على القيمة 1 وكرر العد مطروحًا منه 1 مرة:
4. قم بقراءة 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();
}