التحويل بين الأسس وتطبيقاتها

كتبه بركات يوم السبت, 22 آب 2015

لعلك سبق أن صادفت خدمات اختصار الروابط مثل خدمة goo.gl التابعة لقوقل، هذه الخدمة تعطيها رابط طويل وتختصر لرابط أقصر، مثل:

https://ar.wikipedia.org/wiki/الصفحة_الرئيسية → https://goo.gl/gZoevD

مبدأ عمل هذه الخدمة بسيط، حيث تأخذ الرابط وتخزنه في قاعدة البيانات، لايهم نوعها، قاعدة البيانات ستعطيك معرف فريد للرابط المُخزّن، لكن غالباً مايكون طويل مثل 4237442375892332343، لذا عن طريق التلاعب بأساس العدد يمكن نقله إلى أساس آخر مثل 62 ليصبح 531wVj82UBh، قل طوله نحو 57.89% من العدد الأصلي، ويصبح الرابط http://url.com/531wVj82UBh.

الآن عند دخول شخص على الرابط http://url.com/531wVj82UBh، سيقرأ التطبيق 531wVj82UBh ويحولها من الأساس 62 إلى الأساس 10 ليحصل على معرف القيمة في قاعدة البيانات، ثم يستخرج الرابط الأصلي ويحول المستخدم له، حتى نفهم مسألة التحويل بين الأسس، علينا أن نفهم بعض الأشياء عن الأعداد.

العدد الذي نتعامل معه عبارة عن تشكيلة من 10 رموز (أرقام) محدودة، اتفقنا على أن تكون $\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$، ومنها نشكل أي عدد نريده عن طريق رفع هذه الأرقام لخانة، أي ضربها بأساس هذا العدد مرفوع للأس الذي يمثل هذه الخانة $a \times 10^{i}$ بداءً من الصفر، ومن ثم نضمّها (نجمعها) مع بعض، فمثلاً العدد 1234 يكافئ:

$$1234 = \underbrace{1 \times 10^3 + 2 \times 10^2 + 3 \times 10^1 + 4 \times 10^0}_{1000 + 200 + 30 + 4}$$

الموضوع لايختلف مع الأسس الأخرى المشهورة، فمثلاً الأساس 2 يتكون من رمزين $\{ 0, 1 \}$، حيث أن 13 تكافئ في هذا الأساس $1101_{2}$ ونحسبها هكذا:

$$1101_{2} = \underbrace{1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0}_{8 + 4 + 0 + 1 = 13}$$

بينما في الأساس 16، الرموز أكثر وهي 16 رمز $\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, \textrm{a, b, c, d, e, f} \}$، وفيه 242 تكافئ $\textrm{f}2_{16}$:

$$\textrm{f}2_{16} = \underbrace{15 \times 16^1 + 2 \times 16^0}_{240 + 2 = 242}$$

هناك بعض الأشياء يمكننا ملاحظتها:

  • الأساس يساوي عدد رموزه، ففي الأساس 2 لدينا رمزين وفي الأساس 10 لدينا عشرة رموز.
  • عندما نضرب بأساس العدد، فإننا نضرب ترتيب الرمز في مجموعة رموز هذا العدد (لاحظ في المثال الأخير، 15 هي ترتيب f).
  • الرموز يمكن أن تكون أي رمز يتفق عليه، الأحرف a إلى f في الأساس 16 كان يمكن أن تكون رمز آخر في عالم آخر.
  • يمكنك إنشاء أي أساس تريده طالما لديك الرموز الازمة لتمثيله.
  • كلما كبر الأساس، كلما قل عدد الخانات الازمة لتمثيل هذا العدد.

عدد الخانات الي يشغلها العدد $n$ في الأساس $b$ يمكن الحصول عليها باستخدام $\lfloor \log_{b}{(n+1)} \rfloor + 1$، فمثلاً عدد خانات العدد 1234 في الأسس 2، و10، و16 و62:

$$ \begin{align} \lfloor \log_{2}{(1234 + 1)} \rfloor + 1 &= 11 \\ \lfloor \log_{10}{(1234 + 1)} \rfloor + 1 &= 4 \\ \lfloor \log_{16}{(1234 + 1)} \rfloor + 1 &= 3 \\ \lfloor \log_{62}{(1234 + 1)} \rfloor + 1 &= 2 \end{align} $$

حتى نحول بين أساس وأساس آخر، علينا أولاً أن نعرف الرموز التي نستخدمها، الأساس الذي نستطيع تمثيله يجب أن لايتجاوز عدد هذه الرموز، مثلاً لنستخدم الرموز $S$ التالية:

0123456789
abcdefghijklmnopqrstuvwxyz
ABCDEFGHIJKLMNOPQRSTUVWXYZ
~ - _

وهي بالمناسبة الرموز الممكن استخدامها في الروابط بدون أن ترمّز، عدى الرمز .1، هكذا لدينا 65 رمز، أي أن أعلى أساس يمكننا تمثيله هو الأساس 65، لتحويل العدد $n$ من الأساس 10 إلى أي أساس $b$ من 2 إلى 65 باستخدام هذه الرموز، فيمكننا أن نحسب باقي قسمة العدد $n$ على $b$ أي $a \bmod b$ لنحصل على ترتيب الرمز في $S$، هنا نحصل على أول خانة، ثم نقسم العدد $n$ قسمة صحيحة على $b$ أي $a \backslash b$2، ونكرر العملية لباقي الخانات حتى تعطينا القسمة صفر:

def tobase(n, b):
    digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~-_'
    assert b >= 2 and b <= len(digits)  # base must be in range[2, len(digits)]
    if n == 0:                          # special case
        return digits[0]
    s = ''
    while n > 0:
        r = n  % b
        n = n // b                      # integer division
        s = digits[r] + s               # append to the left
    return s

هنا assert للتأكد من أن الأساس بين 2 و 65 في هذه الحالة، فلا يعقل أن نحول مثلاً للأساس 1 أو الأساس 70، عند التطبيق يفترض استبدالها مثلاً برسالة خطأ، لنجرب الدالة مع العدد 1234:

>>> tobase(1234, 2)
'10011010010'
>>> tobase(1234, 8)
'2322'
>>> tobase(1234, 10)
'1234'
>>> tobase(1234, 16)
'4d2'
>>> tobase(1234, 63)
'jB'
>>> tobase(1234, 65)
'i_'
>>>

لعكس العملية، فإننا نبدأ بأول رمز، ستكون آخر خانة في العدد، ونحصل على ترتيب الرمز في $S$، الآن مع كل خانة جديدة نضرب العدد الناتج بالأساس ثم نجمع الرمز الحالي:

def frombase(s, b):
    digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ~-_'
    assert b >= 2 and b <= len(digits)  # base must be in range[2, len(digits)]
    i = 1
    assert digits.index(s[0]) < b       # e.g. 9 in base 2 invalid
    n = digits.index(s[0])
    while i < len(s):
        assert digits.index(s[i]) < b   # e.g. 9 in base 2 invalid
        n = n * b + digits.index(s[i])
        i += 1
    return n

لنجرب القيم التي حصلنا عليها مع tobase، يفترض أن نحصل على 1234:

>>> frombase('10011010010', 2)
1234
>>> frombase('2322', 8)
1234
>>> frombase('1234', 10)
1234
>>> frombase('4d2', 16)
1234
>>> frombase('jB', 63)
1234
>>> frombase('i_', 65)
1234
>>>

طبعاً الخوارزمية التي وضعتها يمكنك أن تطبقها بالشكل الذي يناسبك.


  1. الرمز . غير مناسب لأن يستخدم في الروابط، فلو صادف أن نقطتين التقت .. فسيصبح شكل الرابط مثلاً /a/b/.. وسيفسرها خادم الويب أنها عودة للمجلد السابق أي /a/، لذا يفضل استبعادها. 

  2. نعم لم أعكس علامة القسمة، الرمز $/$ يشير للقسمة العادية، بينما $\backslash$ يشير للقسمة الصحيحة، فقسمة العددين $a$ و $b$ قسمة صحيحة تساوي $a \backslash b = \lfloor a / b \rfloor$ بمعنى اقسمه قسمة عادية، لكن خذ الجزء الصحيح فقط.