يرجى إضافة وصلات داخلية للمقالات المتعلّقة بموضوع المقالة.

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

من أرابيكا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث

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

الترميز

يرمز الصفر ب "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.

يكون ترميز ليفينشتاين أطول ببت عن ترميزالياس أوميغا [English] لذات العدد، لكن الفرق أن ترميز ليفينشتاين يرمز الرقم 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();
}

المراجع

  1. ^ "1968 paper by V. I. Levenshtein" (PDF) (بالروسية). Archived from the original (PDF) on 2020-09-19.{{استشهاد ويب}}: صيانة الاستشهاد: لغة غير مدعومة (link)
  2. ^ Variable-length codes for data compression. Springer. 2007. ص. 80. ISBN:978-1-84628-958-3. مؤرشف من الأصل في 2021-02-19. {{استشهاد بكتاب}}: الوسيط غير المعروف |الكاتب= تم تجاهله (مساعدة)