# Computing 'score' of string which preserves < relation

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'.

• 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. – Yuval Filmus Feb 14 '18 at 14:11
• Yes, you are of course right - I was unclear in the question - sorry. – tumdum Feb 14 '18 at 15:33

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.$$