0
$\begingroup$

Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$?

$$h : S^* \rightarrow \mathbb{N} $$

Assume $S$ is finite. I would prefer an efficient map.

There should be nice applications of this question for perfect hashing, right?

$\endgroup$
  • $\begingroup$ You probably mean injection instead of map. Right? $\endgroup$ – xskxzr May 11 '18 at 14:01
  • $\begingroup$ yes that's what I meant $\endgroup$ – pedroth May 11 '18 at 16:22
  • $\begingroup$ Perfect hashing is supposed to significantly reduce the amount of information you need to keep for each key. If every possibly value has a unique hash, the hash function is definitely collision-free but you've wasted an enormous amount of space. $\endgroup$ – rici May 11 '18 at 17:42
  • $\begingroup$ Yes I understand what you are saying @rici. Here I just wanted a nice way to compute hash of strings, then I could apply $h(x) \mod N$ to insert in my hash table $\endgroup$ – pedroth May 14 '18 at 10:22
  • $\begingroup$ @pedroth: that won't work well with either of the injections proposed in david richerby's answer or the comment by pseudonym. $\endgroup$ – rici May 14 '18 at 13:45
2
$\begingroup$

Just pretend that your alphabet $S = \{0, \dots, s\}$ for some $s$ and then a string in $S^*$ is just a natural number written out in base $s+1$. There's the slight wrinkle that $0$, $00$, $000$, etc. are all representations of zero, but that's easily fixed by associating the string $x$ with the number whose base-$(s+1)$ representation is $1x$ (i.e., $x$ with a $1$ stuck on the front).

$\endgroup$
  • 1
    $\begingroup$ Making an injective mapping if $S$ is countably infinite is not difficult. Denote the string $s = s_1 s_2 s_3 \ldots s_n$ where $s_i$ are positive integers. Then $h(s) = 2^{s_1} 3^{s_2} 5^{s_3} \cdots p_n^{s_n}$ where $p_i$ are the prime numbers. $\endgroup$ – Pseudonym May 11 '18 at 14:15
  • $\begingroup$ @Pseudonym I guess you could post it as an answer anyway, since it works just fine for finite $S$, too. $\endgroup$ – David Richerby May 11 '18 at 14:35
  • $\begingroup$ Hi @DavidRicherby, can you add some examples of your approach? $\endgroup$ – pedroth May 11 '18 at 16:27
  • $\begingroup$ @pedroth Take $S = \{0, \dots, 9\}$ and the approach is essentially just "Oh, look -- a string in $S^*$ is already a number!" $\endgroup$ – David Richerby May 11 '18 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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