计算UID可能性的大小
根据DICOM规范，UID由：9.1 UID Encoding Rules定义。换句话说，以下是有效的DICOM UID：
- "1.2.3.4.5"
- "1.3.6.1.4.35045.103501438824148998807202626810206788999"
- "1.2.826.0.1.3680043.2.1143.5028470438645158236649541857909059554"
以下是非法的DICOM UID：
- ".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"
因此，我知道该字符串最多为64个字节，并且应该与以下正则表达式[0-9\.]+匹配。然而，这个正则表达式实际上是一个超集，因为它的可能性比(10+1)^64 (=4457915684525902395869512133369841539490161434991526715513934826241L)少得多。
如何准确计算遵守DICOM UID规则的可能性？
阅读org根/后缀规则清楚地表明我至少需要一个点('.')。在这种情况下，组合至少是3个字节(字符)，形式为: 0-9.0-9。在这种情况下，存在长度为3的UID的10x10=100可能性。
看第一个答案，似乎有一些不清楚的地方：
除非组件是一位数，否则每个组件的第一位数不能为零。
这意味着：
- "0.0“是有效的，
- ”00.0“或"1.01”不是有效的
因此，我想说一个恰当的表达应该是：
(([1-9][0-9]*)|0)(\.([1-9][0-9]*|0))+使用简单的C代码，我可以找到：
- f(0) = 0
- f(1) = 0
- f(2) = 0
- f(3) =4753000
<代码>H144f(4)=1800H245H146f(5)=27100H148f(6)=369000=369000H150f(7)=4753000H152f(8)= 59049000
根UID部分的验证超出了此问题的范围。第二个验证步骤可以负责拒绝一些可能无法注册的OID (例如，有些人提到了对第一个和第二个arc的限制)。为简单起见，我们将接受所有可能的(有效的) Root UID。
回答 1
Stack Overflow用户
发布于 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
复制相似问题