Computing the size of UID possibilities

Question

Per DICOM specification, a UID is defined by: 9.1 UID Encoding Rules. In other words the following are valid DICOM UIDs:

• "1.2.3.4.5"
• "1.3.6.1.4.35045.103501438824148998807202626810206788999"
• "1.2.826.0.1.3680043.2.1143.5028470438645158236649541857909059554"

while the following are illegal DICOM UIDs:

• ".1.2.3.4.5"
• "1..2.3.4.5"
• "1.2.3.4.5."
• "1.2.3.4.05"
• "12345"
• "1.2.826.0.1.3680043.2.1143.50284704386451582366495418579090595540"

Therefore I know that the string is at most 64 bytes, and should match the following regex [0-9\.]+. However this regex is really a superset, since there are a lot less than (10+1)^64 (=4457915684525902395869512133369841539490161434991526715513934826241L) possibilities.

How would one computes precisely the number of possibilities to respect the DICOM UID rules ?

---

Reading the org root / suffix rule clearly indicates that I need at least one dot ('.'). In which case the combination is at least 3 bytes (char) in the form: [0-9].[0-9]. In which case there are 10x10=100 possibilities for UID of length 3.

Looking at the first answer, there seems to be something unclear about:

The first digit of each component shall not be zero unless the component is a single digit.

What this means is that:

• "0.0" is valid
• "00.0" or "1.01" are not valid

Thus I would say a proper expression would be:

(([1-9][0-9]*)|0)(\.([1-9][0-9]*|0))+

Using a simple C code, I could find:

• f(0) = 0
• f(1) = 0
• f(2) = 0
• f(3) = 100
• f(4) = 1800
• f(5) = 27100
• f(6) = 369000
• f(7) = 4753000
• f(8) = 59049000

---

The validation of the Root UID part is outside the scope of this question. A second validation step could take care of rejecting some OID that cannot possibly be registered (some people mention restriction on first and second arc for example). For simplicity we'll accept all possible (valid) Root UID.

Answer 1

While my other answer takes good care of this specific application, here is a more generic approach. It takes care of situations where you have a different regular expression describing the language in question. It also allows for considerably longer string lengths, since it only requires O(log n) arithmetic operations to compute the number of combinations for strings of length up to n. In this case the number of strings grows so quickly that the cost of these arithmetic operations will grow dramatically, but that may not be the case for other, otherwise similar situations.

Build a finite state automaton

Start with a regular expression description of your language in question. Translate that regular expression into a finite state automaton. In your case the regular expression can be given as

(([1-9][0-9]*)|0)(\.([1-9][0-9]*|0))+

The automaton could look like this:

Eliminate ε-transitions

This automaton usually contains ε-transitions (i.e. state transitions which do not correspond to any input character). Remove those, so that one transition corresponds to one character of input. Then add an ε-transition to the accepting state(s). If the accepting states have other outgoing transitions, don't add ε-loops to them, but instead add an ε-transition to an accepting state with no outgoing edges and then add the loop to that. This can be seen as padding the input with ε at its end, without allowing ε in the middle. Taken together, this transformation ensures that performing exactly n state transitions corresponds to processing an input of n characters or less. The modified automaton might look like this:

Note that both the construction of the first automaton from the regular expression and the elimination of ε-transitions can be performed automatically (and perhaps even in a single step. The resulting automata might be more complicated than what I constructed here manually, but the principle is the same.

Ensuring unique paths

You don't have to make the automaton deterministic in the sense that for every combination of source state and input character there is only one target state. That's not the case in my manually constructed one either. But you have to make sure that every complete input has only one possible path to the accepting state, since you'll essentially be counting paths. Making the automaton deterministic would ensure this weaker property, too, so go for that unless you can ensure unique paths without this. In my example the length of each component clearly dictates which path to use, so I didn't make it deterministic. But I've included an example with a deterministic approach at the end of this post.

Build transition matrix

Next, write down the transition matrix. Associate the rows and columns with your states (in order a, b, c, d, e, f in my example). For each arrow in your automaton, write the number of characters included in the label of that arrow in the column associated with the source state and the row associated with the target state of that arrow.

⎛ 0  0  0  0  0  0⎞
⎜ 9 10  0  0  0  0⎟
⎜10 10  0 10 10  0⎟
⎜ 0  0  1  0  0  0⎟
⎜ 0  0  0  9 10  0⎟
⎝ 0  0  0 10 10  1⎠

Read result off that matrix

Now applying this matrix with a column vector once has the following meaning: if the number of possible ways to arrive in a given state is encoded in the input vector, the output vector gives you the number of ways one transition later. Take the 64th power of that matrix, concentrate on the first column (since ste start situation is encoded as (1,0,0,0,0,0), meaning only one way to end up in the start state) and sum up all the entries that correspond to accepting states (only the last one in this case). The bottom left element of the 64th power of this matrix is

1474472506836676237371358967075549167865631190000000000000000000000

which confirms my other answer.

Compute matrix powers efficiently

In order to actually compute the 64th power of that matrix, the easiest approach would be repeated squaring: after squaring the matrix 6 times you have an exponent of 2⁶ = 64. If in some other scenario your exponent (i.e. maximal string length) is not a power of two, you can still perform exponentiation by squaring by multiplying the relevant squares according to the bit pattern of the exponent. This is what makes this approach take O(log n) arithmetic operations to compute the result for string length n, assuming a fixed number of states and therefore fixed cost for each matrix squaring.

Example with deterministic automaton

If you were to make my automaton deterministic using the usual powerset construction, you'd end up with

and sorting the states as a, bc, c, d, cf, cef, f one would get the transition matrix

⎛ 0  0  0  0  0  0  0⎞
⎜ 9 10  0  0  0  0  0⎟
⎜ 1  0  0  0  0  0  0⎟
⎜ 0  1  1  0  1  1  0⎟
⎜ 0  0  0  1  0  0  0⎟
⎜ 0  0  0  9  0 10  0⎟
⎝ 0  0  0  0  1  1  1⎠

and could sum the last three elements of the first column of its 64th power to obtain the same result as above.