1
\$\begingroup\$

What is the most compact way to encode/save DNS names in memory?

For example, storing "www.google.com" as a string in .NET will result in the object being encoded as UTF-16, and it will consume twice as much memory as plain ASCII... but for the purpose of storing DNS names, ASCII is overkill.

The only characters that are needed are:

  • A..Z (case insensitive)
  • 0..9
  • Hyphen
  • underscore
  • period
  • Asterisk (not legal DNS, but used in ACLs such as *.google.com) always as a leading character, never elsewhere.

A total of 40 characters.. which fits within single byte with plenty room to spare.

My code golf question/challenge is what is the most compact way to store a string of characters in memory and maximizing in memory storage?

The inspiration for this challenge came from this blog entry.

\$\endgroup\$
  • 1
    \$\begingroup\$ How do you win the competition? \$\endgroup\$ – beary605 Oct 21 '12 at 6:44
  • 3
    \$\begingroup\$ You meant UTF-16 for the .NET framework. In UTF-8, this name would take up just as much as ASCII. \$\endgroup\$ – Mr Lister Oct 21 '12 at 7:00
  • \$\begingroup\$ Try cs.stackexchange.com - there's probably already a question about basic information theory which would tell you all you need to know. \$\endgroup\$ – Peter Taylor Oct 21 '12 at 8:01
  • \$\begingroup\$ en.wikipedia.org/wiki/Kolmogorov_complexity? \$\endgroup\$ – beary605 Oct 21 '12 at 15:48
  • 1
    \$\begingroup\$ As stated this looks like a question for Stack Overflow (that is, it is a question). CodeGolf.SE is a plce for playing certain programming games. It would be essentially trivial to turn this into a [code-golf]---you just add the tag (and probably the one @beary suggests as well) and resign yourself to getting answer many languages. But I am closing until that is done just to encourage you to read the FAQ before posting to a new Stack Exchange site. Flag when you are ready for this to be re-opened. \$\endgroup\$ – dmckee --- ex-moderator kitten Oct 21 '12 at 19:10
3
\$\begingroup\$

You could interpret it as a base 39 number. Since only the first character can be an asterisk, you can encode it as the sign. If i use the characters as digits in the order you named them, www.google.com would be 10903065870001232914011 in decimal and 24f0e6f41d8ecd3a65b in hex, which could be stored in 10 bytes.

*.google.com would be -310664672884413873 in decimal and fbb04c2040762a4f in hex, if you store it in 8 bytes.

\$\endgroup\$
0
\$\begingroup\$

Oh, that's easy. You just zip it.

\$\endgroup\$
  • 1
    \$\begingroup\$ gzip on a file containing www.google.com gives 42 bytes. \$\endgroup\$ – ugoren Oct 21 '12 at 11:11
  • \$\begingroup\$ Ah... when you use Windows' built in zipping routines, you get a 132 byte file. Oh well. \$\endgroup\$ – Mr Lister Oct 21 '12 at 14:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.