Algorithm to convert a fixed-length string to the smallest possible collision-free representation?

Question

I have a US-based telephone number (in the format 000-000-0000) and need to convert it to a "shorter" representation. Using base32/64 produces too long of a string. I've discovered CRC-16, which produces a string of length 4, however, I'm not sure it's a suitable tool for the job (I want to prevent collisions).

Basically, if the input is 000-000-0000 (without the dashes), I want the output to be something like 4xg4. In this use case, the advantage is that I have 10 digits, thus I could "convert" them to something smaller that uses letters as well.

Are you aware of any algorithm implementation for this?

Answer 1

As ratchet freak says, you have ten decimal digits, which should give $10^{10}$ possible values. But in practice, there are a few more restrictions. The format of a North American telephone number looks something like this:

[2-9][0-8]\d - [2-9]\d\d - \d\d\d\d

This gives 8*9*10 * 8*10*10 * 10*10*10*10 values. In addition, the fifth and sixth characters can't both be 1, which removes 1% of these. This means there are 5,702,400,000 possible telephone numbers. (Let's call this number $T$.)

If you want to encode these using an alphabet with $b$ different characters, you'll need a code $\lceil \log_b T \rceil$ characters long. So if you want a code four characters long, you'll need $b \geq 275$. If you want a code five characters long, you'll need $b \geq 90$. And if you want a code six characters long, you'll need $b \geq 43$.

Unfortunately, this is the best you can do, unless you have additional information about what numbers you'll be getting. This comes down to the pigeonhole principle, a remarkably straightforward theorem that's quite useful in CS. It's mathematically impossible to use fewer characters than this without ever having any collisions. You can make collisions extremely unlikely, but never fully prevent them.

(You can also make some of the codes be shorter without collisions, but as a consequence some of them will have to be longer. Again, pigeonhole principle.)

P.S. Note that, while base64 also produces a six-character string (since 64 is between 43 and 90), you can take advantage of the fact that you only need 43 to choose a "nicer" character set. For example, you can get rid of o, O, 0, Q, I, l, and 1 to cut down on confusion in writing. My suggestion would be 23456789ABCDEFGHJKLMNPRSTVXYZabdeghknpqrt-=.

Answer 2

You have 10 base10 digits. This is $10^{10}$ possible values.

Encoding this in an alphabet with 64 tokens you need $\lceil \log_{64}(10^{10}) \rceil = 6$ characters.

If you encode it in straight binary you only need $\lceil \log_{2}(10^{10}) \rceil = 34$ bits total. 4 bytes + 2 bits.

Unless there is a pattern in the number itself this is the best you can do.

Note that this looks at the number in a vacuum. If you encode more than just that number you can use arithmetic encoding to use some of the "spare room" the rounding creates.

Answer 3

Draconis already gave an excellent answer of the specific theoretical limitations of your question. However, I figured it wouldn't hurt to show an explicit implementation of such an encoding schema.

As Draconis covered we need an alphabet of at least 90 letters in order to encode a North American based telephone number in 5 characters or less. As luck would have it standard ASCII has 95 printable characters, of which one is the space character and thus unsuitable for encoding (using the restriction that all elements be, well, visible). This gives us four extra characters, so for ease of reading I am removing the quotation characters ('"`) and capital I as it may be confused for lower case L.

The algorithm itself is fairly simple, but there are some major caveats. Naively we could just convert the telephone number into a base 10 number and then convert it to a base 90 representation, but our solution relies upon the reduced variations of a North American telephone number, otherwise we would need an alphabet of at least 100 characters. Consequently the naive implementation would actually fail for "large" inputs. So instead we will convert the telephone number to base 10 with some reductions to get it in the right form.

To be exact, the first (counting from left to right) seven digits will be converted as normal, but we will subtract $2\cdot 10^6$ to account for the seventh digit not being allowed to be zero or one (in effect, we are shifting [2-9] down to [0-7]). Then the next three digits will be converted with similar restrictions and multiplied by $8 \cdot 10^6$ instead of $10^7$ to account for the seventh digit's having only 8 possible values, not ten.

Sample Python implementation included below

charset = ''.join([chr(i) for i in range(33,127) if i not in [34, 39, 73, 96]])
def encodeTel(t, charset):
    n = ''.join(t.split('-'))
    num = int(int(n[3:]) - 2e6 + ((int(n[0])-2)*90 + int(n[1:3]))*8e6)
    encoded = []
    base = len(charset)
    x = num
    if x == 0:
        encoded.append(charset[0])
    while x > 0:
        encoded.append(charset[x % base])
        x //= base
    return ''.join(encoded[::-1])

Sample output:

In [1]: encodeTel('989-999-9999', charset)
Out[1]: '|l8,~'
In [2]: encodeTel('200-200-0000', charset)
Out[2]: '!'

(Note: I haven't actually checked if the given function absolutely has no collisions, but it shouldn't have any and a cursory check didn't find any in the first 85 million valid telephone numbers or so)