math - Cálculo del tamaño de las posibilidades de UID

dicom

Question

Según la especificación DICOM, un UID se define mediante: 9.1 Reglas de codificación UID . En otras palabras, los siguientes son UIDs DICOM válidos:

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

Mientras que los siguientes son UIDs DICOM ilegales:

• ".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"

Por lo tanto, sé que la cadena tiene un máximo de 64 bytes y debe coincidir con la siguiente expresión regular [0-9/.]+ . Sin embargo, este regex es realmente un superconjunto, ya que hay mucho menos que (10+1)^64 (=4457915684525902395869512133369841539490161434991526715513934826241L) posibilidades.

¿Cómo se calcula con precisión la cantidad de posibilidades para respetar las reglas UID de DICOM?

La lectura de la regla de raíz / sufijo org indica claramente que necesito al menos un punto (''.''). En cuyo caso la combinación es de al menos 3 bytes (char) en la forma: [0-9]. [0-9]. En cuyo caso hay 10x10=100 posibilidades para UID de longitud 3.

En cuanto a la primera respuesta, parece que hay algo poco claro sobre:

El primer dígito de cada componente no será cero a menos que el componente sea un solo dígito.

Lo que esto significa es que:

• "0.0" es válido
• "00.0" o "1.01" no son válidos

Por eso diría que una expresión adecuada sería:

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

Usando un código C simple, pude encontrar:

• 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

La validación de la parte UID raíz está fuera del alcance de esta pregunta. Un segundo paso de validación podría encargarse de rechazar algunos OID que no se pueden registrar (por ejemplo, algunas personas mencionan restricciones en el primer y segundo arco). Por simplicidad aceptaremos todos los UID de raíz posibles (válidos).

Answer 1

Componente único

Comience buscando formas de formar un solo componente. La expresión regular correspondiente para un solo componente es

0|[1-9][0-9]*

por lo tanto, es cero o un dígito distinto de cero seguido de muchos cero dígitos arbitrarios. (Al principio, me había perdido el posible único caso cero, pero el comentario de malat me hizo consciente de esto). Si la longitud total de dicho componente es n , y escribe h ( n ) para indicar el número de formas para formar un componente de longitud exactamente n , entonces puede calcular que h ( n ) como

h(n) = if n = 1 then 10 else 9 * 10^(n - 1)

donde el caso n = 1 permite todos los dígitos posibles, y los otros casos aseguran un primer dígito distinto de cero.

Uno o mas componentes

La subsección 9.1 solo escribe que un UID es un grupo de componentes numéricos separados por puntos, como se describe anteriormente. Así que en expresiones regulares eso sería

(0|[1-9][0-9]*)(/.(0|[1-9][0-9]*))*

Supongamos que f ( n ) es el número de formas de escribir un UID de longitud n . Entonces tiene

f(n) = h(n) + sum h(i) * f(n-i-1) for i from 1 to n-2

El primer término describe el caso de un solo componente, mientras que la suma se ocupa del caso en el que consta de más de un componente. En ese caso, tiene un primer componente de longitud i , luego un punto que representa el -1 en la fórmula, y luego los dígitos restantes forman uno o más componentes que se expresan mediante el uso recursivo de f .

Dos o mas componentes

Como indica el comentario de cneller, la parte de la sección 9 antes de la subsección 9.1 indica que debe haber al menos dos componentes. Así que la expresión regular apropiada sería más como

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

con un + al final que indica que queremos al menos una repetición de la expresión entre paréntesis. Derivar una expresión para esto simplemente significa dejar de lado el caso de un solo componente en la definición de f :

g(n) = sum h(i) * f(n-i-1) for i from 1 to n-2

Si suma toda la g ( n ) para n desde 3 (la longitud de UID mínima posible) hasta 64, obtendrá el número de UID posibles como

1474472506836676237371358967075549167865631190000000000000000000000

o aproximadamente 1.5e66 . Lo que es considerablemente menor que el 4.5e66 que obtiene de su cálculo, en términos de diferencia absoluta, aunque definitivamente es del mismo orden de magnitud. Por cierto, su estimación no menciona explícitamente los UID más cortos que 64, pero siempre puede considerar rellenarlos con puntos en su configuración. Hice el cálculo utilizando unas pocas líneas de código Python :

f = [0]
g = [0]
h = [0, 10] + [9 * (10**(n-1)) for n in range(2, 65)]
s = 0
for n in range(1, 65):
x = 0
if n >= 3:
for i in range(1, n - 1):
x += h[i] * f[n-i-1]
g.append(x)
f.append(x + h[n])
s += x
print(h)
print(f)
print(g)
print(s)

Answer 2

Si bien mi otra respuesta cuida esta aplicación específica, aquí hay un enfoque más genérico. Se ocupa de las situaciones en las que tiene una expresión regular diferente que describe el lenguaje en cuestión. También permite longitudes de cadena considerablemente más largas, ya que solo requiere operaciones aritméticas O (log n ) para calcular el número de combinaciones para cadenas de longitud hasta n . En este caso, el número de cadenas crece tan rápidamente que el costo de estas operaciones aritméticas crecerá drásticamente, pero puede que no sea el caso para otras situaciones similares.

Construir un autómata de estado finito

Comience con una descripción de expresión regular de su idioma en cuestión. Traducir esa expresión regular en un autómata de estado finito. En su caso la expresión regular se puede dar como

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

El autómata podría verse así:

Eliminar las transiciones ε

Este autómata generalmente contiene transiciones ε (es decir, transiciones de estado que no corresponden a ningún carácter de entrada). Elimínelos, de modo que una transición corresponda a un carácter de entrada. Luego agregue una transición ε al estado o estados de aceptación. Si los estados de aceptación tienen otras transiciones salientes, no les agregue bucles ε, sino que agregue una transición ε a un estado de aceptación sin bordes salientes y luego agregue el bucle a eso. Esto se puede ver como rellenar la entrada con ε en su extremo, sin permitir ε en el medio. En conjunto, esta transformación garantiza que realizar exactamente n transiciones de estado corresponde al procesamiento de una entrada de n caracteres o menos. El autómata modificado podría verse así:

Tenga en cuenta que tanto la construcción del primer autómata a partir de la expresión regular como la eliminación de las transiciones ε se pueden realizar automáticamente (y quizás incluso en un solo paso . Los autómatas resultantes pueden ser más complicados que lo que construí aquí manualmente, pero el principio es el mismo.

Asegurando caminos únicos.

No tiene que hacer que el autómata sea deterministic en el sentido de que para cada combinación de estado de origen y carácter de entrada solo hay un estado objetivo. Ese no es el caso en mi construido manualmente tampoco. Pero debe asegurarse de que cada entrada completa tenga solo una ruta posible al estado de aceptación, ya que esencialmente contará las rutas. Hacer que el autómata sea determinista también aseguraría esta propiedad más débil, así que hazlo a menos que puedas asegurar rutas únicas sin esto. En mi ejemplo, la longitud de cada componente dicta claramente qué ruta usar, así que no lo hice determinista. Pero he incluido un ejemplo con un enfoque determinista al final de este post.

Construir una matriz de transición

A continuación, escriba la matriz de transición. Asocie las filas y columnas con sus estados (en el orden a, b, c, d, e, f en mi ejemplo). Para cada flecha en su autómata, escriba el número de caracteres incluidos en la etiqueta de esa flecha en la columna asociada con el estado de origen y la fila asociada con el estado objetivo de esa flecha.

⎛ 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⎠

Lee el resultado de esa matriz

Ahora, aplicar esta matriz con un vector de columna una vez tiene el siguiente significado: si el número de formas posibles de llegar a un estado determinado se codifica en el vector de entrada, el vector de salida le da el número de formas de una transición posterior. Tome la potencia 64 de esa matriz, concéntrese en la primera columna (ya que esta situación de inicio se codifica como (1,0,0,0,0,0), lo que significa que solo hay una forma de terminar en el estado de inicio) y resuma todas las entradas que corresponden a estados de aceptación (solo la última en este caso). El elemento inferior izquierdo de la potencia 64 de esta matriz es

1474472506836676237371358967075549167865631190000000000000000000000

Lo que confirma mi otra respuesta.

Calcular las potencias de la matriz de manera eficiente.

Para calcular realmente la potencia 64 de esa matriz, el enfoque más fácil sería repetir el escuadrado: después de cuadrar la matriz 6 veces, tiene un exponente de 2 ⁶ = 64. Si en algún otro escenario su exponente (es decir, la longitud máxima de la cadena) es no es una potencia de dos, aún puede realizar la exponencia al cuadrar multiplicando los cuadrados relevantes de acuerdo con el patrón de bits del exponente. Esto es lo que hace que este enfoque tome O (log n ) operaciones aritméticas para calcular el resultado para la longitud de la cadena n , asumiendo un número fijo de estados y, por lo tanto, un costo fijo para cada cuadratura de la matriz.

Ejemplo con autómata determinista.

Si fueras a hacer que mi autómata fuera determinista usando la construcción usual de la central, terminarías con

y clasificando los estados como a , bc , c , d , cf , cef , f uno obtendría la matriz de transición

⎛ 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⎠

y podría sumar los últimos tres elementos de la primera columna de su potencia 64 para obtener el mismo resultado que el anterior.