1
$\begingroup$

Is there a way to calculate some kind of numerical 'score' for arbitrary strings which when compared with score of some other string will preserve '<' relation?

I've searched for order preserving compression/hashing but what I've found is either based on precomputing with known set of strings or is a some for of lossless compression.

edit:

To clarify - I don't need it to preserve order exactly. When I need is to have guarantee that if score(A) < score(B) than A < B. If score(A) >= score(B) than it still can be true that A < B. I just would be nice if probability of incorrect relation was 'low'.

$\endgroup$
  • $\begingroup$ Since $a < aa < aaa < \cdots < b$, this is impossible if the the numerical score is integral, but possible if it is an infinite-precision real number. $\endgroup$ – Yuval Filmus Feb 14 '18 at 14:11
  • $\begingroup$ Yes, you are of course right - I was unclear in the question - sorry. $\endgroup$ – tumdum Feb 14 '18 at 15:33
1
$\begingroup$

Suppose that your alphabet has size $N$ (say, $N=256$). You can think of each word as being over an alphabet of size $N+1$, with the extra element (first in the order) representing "end of word". Take a short prefix of the word (of some fixed constant size) and think of it as the base $N+1$ representation of a natural number.

As an example, suppose that the alphabet is $A<B$ (in this order), and that we take prefixes of length 2. Consider the strings $$ A < AA < AAA < B. $$ We think of these as the numbers $1,11,111,2$ in base 3. Taking prefixes of length 2, we get $10,11,11,20$ (here you see how the extra element is used). The encodings are thus $$ 3 < 4 = 4 < 6. $$

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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