# Not quite-infinitely expandable human-friendly naming system?

This may be a known problem, with known approaches, but I can't find the right way to search for it.

I would like to name points along a line of unknown final length such that their name reflects their relative position to all other named points on that line. One should be able to insert an arbitrary number of names at any point along the line including outside the existing first and last named points. A lexicographical sort of the point names would always result in a list of points in a monotonic order.

An order of magnitude estimate of the total number of points to be ultimately named can be supplied up front

• Names must be stable, no-renaming after initial assignment
• Names may be constructed from a limited character set: 25 lowercase letters a-z with 'L' removed.
• The naming scheme should not require an extreme fan-out of name length when adding names either outside the existing points or between two adjacent points. E.g. Imagine that I want to add something before the name 'a', that wouldn't be possible while maintaining linear order during sorting. Starting with 'b' only delays the issue. Same for z on the other end.
• Names should be of the shortest possible length such that a human could easily glance at one and then write it out elsewhere for most names.

It is highly likely that one would want to insert names between previously adjacent names, and then later between adjacent named points in that previous insertion.

The real-life use case for this is the creation of spatial names for all features of a given kind, say genes, in a species when we don't know in advance the total set of features. This is because different individuals only contain a subset of the total sequence space that the whole population of organisms encompass. The problem is easy to solve with static sets of sequences, but not if you allow them to expand at any point along the line (chromosomes) with the addition of new information. The set sizes of interest encompass 10^5 -10^7 items.

• It's not clear what the operations are. It appears you want some dynamic data structure, but what operations can be performed on the data structure? When you insert a name at any point on the line, how is the position on the line specified? Probably the answer will be something along the lines of "interpret the position as a real number in the range $[0,1]$, stored in fixed-point, and convert to base 25" or "build a tree with branching factor $\le 25$", but it's hard for me to tell exactly what to suggest since the requirements aren't entirely clear to me.
– D.W.
Jan 26 '18 at 23:15
• Interpreted literally, this isn't possible. The lexicographic order has no infinitely descending chains and that means that, however you choose to allocate labels, you'll run out of labels to the left if you get a long enough sequence of "And now add another point to the left of everything you already have" instructions. No such problem exists on the right, since you can always follow 'z' with 'zz', 'zzz', 'zzzz', etc. Jan 26 '18 at 23:25

Let's say you have n possible names. I insert the first point into the list, and you name it. However you name it, either there are only $n/2$ possible names larger or only $n/2$ possible names smaller than the name you chose.
I insert the second point so that it is in the range with fewer names. You name it. Now you have at least one range with only $n/4$ possible names. I insert the third point into the range with fewer possible names, and so on. After inserting k points, there will be a range where you have only $n/2^k$ possible names, and I can make you fail when $k ≥ \log n$.