根据DICOM规范,UID由:9.1 UID Encoding Rules定义。换句话说,以下是有效的DICOM UID:
以下是非法的DICOM UID:
因此,我知道该字符串最多为64个字节,并且应该与以下正则表达式[0-9\.]+
匹配。然而,这个正则表达式实际上是一个超集,因为它的可能性比(10+1)^64 (=4457915684525902395869512133369841539490161434991526715513934826241L)
少得多。
如何准确计算遵守DICOM UID规则的可能性?
阅读org根/后缀规则清楚地表明我至少需要一个点('.')。在这种情况下,组合至少是3个字节(字符),形式为: 0-9.0-9。在这种情况下,存在长度为3的UID的10x10=100
可能性。
看第一个答案,似乎有一些不清楚的地方:
除非组件是一位数,否则每个组件的第一位数不能为零。
这意味着:
因此,我想说一个恰当的表达应该是:
(([1-9][0-9]*)|0)(\.([1-9][0-9]*|0))+
使用简单的C代码,我可以找到:
<代码>H144f(4)=1800H245H146f(5)=27100H148f(6)=369000=369000H150f(7)=4753000H152f(8)= 59049000
根UID部分的验证超出了此问题的范围。第二个验证步骤可以负责拒绝一些可能无法注册的OID (例如,有些人提到了对第一个和第二个arc的限制)。为简单起见,我们将接受所有可能的(有效的) Root UID。
发布于 2016-09-09 18:30:00
单个组件
从寻找形成单个组件的方法开始。单个组件的对应正则表达式为
0|[1-9][0-9]*
所以它要么是零,要么是一个非零数字,后面跟着任意多个零数字。(一开始我错过了可能的唯一零案例,但malat的评论让我意识到了这一点。)如果这样的组件的总长度是n,并且您编写h(n)来表示形成长度正好为n的组件的方法的数量,那么您可以计算h(n)为
h(n) = if n = 1 then 10 else 9 * 10^(n - 1)
其中n=1的情况允许所有可能的数字,而其他情况确保第一个数字不为零。
一个或多个组件
第9.1节只写到UID是一堆由点分隔的数字组件,如上所述。因此,在正则表达式中,这将是
(0|[1-9][0-9]*)(\.(0|[1-9][0-9]*))*
假设f( n )是写入长度为n的UID的方式数。
f(n) = h(n) + sum h(i) * f(n-i-1) for i from 1 to n-2
第一项描述单个组件的情况,而sum用于处理由多个组件组成的情况。在这种情况下,你有一个长度为i的第一个分量,然后是一个点,它代表了公式中的-1,然后剩下的数字形成了一个或多个分量,通过递归使用f来表示。
两个或更多组件
正如cneller的评论所表明的那样,第9条9.1小节之前的部分表明至少必须有两个组成部分。因此,正确的正则表达式应该更像这样
(0|[1-9][0-9]*)(\.(0|[1-9][0-9]*))+
在结尾处有一个+
,表示我们希望括号中的表达式至少重复一次。为此导出一个表达式,简单地说就是在f的定义中省略了只有一个组件的情况
g(n) = sum h(i) * f(n-i-1) for i from 1 to n-2
如果将3(最小可能UID长度)到64之间的n的所有g(n)相加,则可能的UID数为
1474472506836676237371358967075549167865631190000000000000000000000
或者近似为1.5e66
。就绝对差而言,这比你从计算中得到的4.5e66
要小得多,尽管它绝对在同一个数量级上。顺便说一句,您的估计没有明确提到小于64的UID,但是您可以始终考虑在设置中用点填充它们。我使用a few lines of Python code进行了计算
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)
https://stackoverflow.com/questions/39388514
复制相似问题