计算UID可能性的大小

Question

根据DICOM规范,UID由以下内容定义:9.1 UID编码规则.换句话说,以下是有效的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规则的可能性数量？

---

读取组织根/后缀规则清楚地表明我至少需要一个点('.').在这种情况下,组合至少为3个字节(字符),格式为:[0-9].[0-9].在这种情况下10x10=100,UID的长度可能为3.

看一下第一个答案,似乎有些不清楚:

除非组件是单个数字,否则每个组件的第一个数字不应为零.

这意味着:

• "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)= 100
• f(4)= 1800
• f(5)= 27100
• f(6)= 369000
• f(7)= 4753000
• f(8)= 59049000

---

Root UID部分的验证超出了本问题的范围.第二个验证步骤可以处理拒绝一些不可能注册的OID(例如,有些人提到对第一和第二弧的限制).为简单起见,我们将接受所有可能的(有效)Root UID.

Answer 1

单一组件

首先,寻找形成单个组件的方法.单个组件的相应正则表达式是

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

所以它是零或非零数字后跟任意多个零数字.(我最初错过了可能唯一的零案例,但是马拉特的评论让我意识到这一点.)如果这个组件的总长度是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

第一个术语描述了单个组件的情况,而总和则考虑了由多个组件组成的情况.在这种情况下,你有一个长度为i的第一个分量,然后是一个代表公式中-1的点,然后剩下的数字组成一个或多个组件,这些组件通过f的递归使用来表示.

两个或更多组件

正如cneller的评论所指出的那样,第9.1节之前的第9节中的部分表明必须至少有两个组成部分.所以正确的正则表达式会更像

(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你得到尽可能的UID的数

1474472506836676237371358967075549167865631190000000000000000000000

或大约1.5e66.4.5e66从绝对差异的角度来看,这比计算得到的要少得多,尽管它肯定处于同一数量级.顺便说一句,你的估计没有明确提到短于64的UID,但你总是可以考虑在你的设置中用点填充它们.我使用几行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

虽然我的其他答案很好地照顾了这个特定的应用程序,但这是一个更通用的方法.它会处理您使用不同的正则表达式来描述相关语言的情况.它还允许相当长的字符串长度,因为它只需要O(log n)算术运算来计算长度最多为n的字符串的组合数.在这种情况下,字符串的数量增长如此之快,以至于这些算术运算的成本将急剧增长,但对于其他类似的情况可能并非如此.

构建有限状态自动机

从您所使用的语言的正则表达式描述开始.将该正则表达式转换为有限状态自动机.在您的情况下,正则表达式可以作为

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

自动机可能如下所示:

消除ε-过渡

该自动机通常包含ε-转换(即,不对应于任何输入字符的状态转换).删除它们,以便一个转换对应于一​​个输入字符.然后将ε-转换添加到接受状态.如果接受状态具有其他传出转换,则不要向它们添加ε-循环,而是将ε-转换添加到没有传出边缘的接受状态,然后将循环添加到该状态.这可以看作是在其末端用ε填充输入,而不允许中间的ε.总之,这种转换确保恰好执行n个状态转换对应于处理n个字符或更少字符的输入.修改后的自动机可能如下所示:

请注意,正则表达式中第一个自动机的构造和ε-过渡的消除都可以自动执行(甚至可以在一个步骤中执行.结果自动机可能比我在这里手动构造的更复杂,但原理是一样的.

确保独特的路径

从某种意义上说,对于源状态和输入字符的每个组合,只有一个目标状态,您不必使自动机具有确定性.我手动构建的情况也不是这样.但是你必须确保每个完整的输入只有一条通往接受状态的可能路径,因为你基本上是在计算路径.使自动机确定性也会确保这个较弱的属性,所以除非你可以确保没有这个的独特路径.在我的例子中,每个组件的长度明确规定了使用哪条路径,所以我没有确定它.但是我在本文末尾列举了一个确定性方法的例子.

构建转换矩阵

接下来,记下转换矩阵.将行和列与您的状态相关联(在我的示例中按顺序a,b,c,d,e,f).对于自动机中的每个箭头,请在与源状态关联的列中以及与该箭头的目标状态关联的行中写入该箭头标签中包含的字符数.

? 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?

从该矩阵中读取结果

现在将此矩阵与列向量一起应用具有以下含义:如果在输入向量中编码到达给定状态的可能方式的数量,则输出向量将为您提供稍后转换的方式的数量.取该矩阵的64次幂,集中于第一列(因为ste start情境被编码为(1,0,0,0,0,0),意味着只有一种方式结束于开始状态)并总结所有与接受状态相对应的条目(在这种情况下只是最后一个).该矩阵的64次幂的左下角元素是

1474472506836676237371358967075549167865631190000000000000000000000

这证实了我的另一个答案.

计算矩阵有效地提供动力

为了实际计算该矩阵的64次幂,最简单的方法是重复平方:在将矩阵平方6次后,你的指数为2 ⁶ = 64.如果在某些其他情况下你的指数(即最大字符串长度)是不是2的幂,你仍然可以通过根据指数的位模式乘以相关的平方来进行求幂.这使得该方法采用O(log n)算术运算来计算字符串长度n的结果,假设固定数量的状态,因此每个矩阵平方的固定成本.

确定性自动机的示例

如果你使用通常的powerset构造使我的自动机确定性,你最终会得到

并将状态分类为a,bc,c,d,cf,cef,f将获得转换矩阵

? 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?

并且可以将其第64个幂的第一列的最后三个元素相加以获得与上面相同的结果.