تضامنًا مع حق الشعب الفلسطيني |
ترميز ليفينشتاين
اذهب إلى التنقل
اذهب إلى البحث
ترميز ليفينشتاين (بالإنجليزية: Levenshtein coding) هو أحد أنواع الترميز العامة للأعداد غير السالبة. طُوِّر على يد فلاديمير ليفينشتاين [English].[1][2]
الترميز
يرمز الصفر ب "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.
يكون ترميز ليفينشتاين أطول ببت عن ترميزالياس أوميغا [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();
}
المراجع
- ^
"1968 paper by V. I. Levenshtein" (PDF) (بالروسية). Archived from the original (PDF) on 2020-09-19.
{{استشهاد ويب}}
: صيانة الاستشهاد: لغة غير مدعومة (link) - ^
Variable-length codes for data compression. Springer. 2007. ص. 80. ISBN:978-1-84628-958-3. مؤرشف من الأصل في 2021-02-19.
{{استشهاد بكتاب}}
: الوسيط غير المعروف|الكاتب=
تم تجاهله (مساعدة)