计算 UID 可能性的大小
Computing the size of UID possibilities
根据 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 规则的可能性的数量？
阅读组织根/后缀规则清楚地表明我至少需要一个点（'.'）。在这种情况下，组合至少为 3 个字节 (char)，格式为：[0-9].[0-9]。在这种情况下，长度为 3 的 UID 有 10x10=100 种可能性。
看第一个回答，好像有不清楚的地方：
The first digit of each component shall not be zero unless the
component is a single digit.
这意味着：
- “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
根 UID 部分的验证不在本问题的讨论范围内。第二个验证步骤可以负责拒绝一些不可能注册的 OID（例如，有些人提到对第一和第二弧的限制）。为简单起见，我们将接受所有可能的（有效的）根 UID。
单一成分
首先寻找形成单个组件的方法。单个组件对应的正则表达式为
0|[1-9][0-9]*
所以它要么是零，要么是一个非零数字，后跟任意多个零数字。 （一开始我错过了可能的唯一零情况，但 malat 的评论让我意识到了这一点。）如果这样一个组件的总长度是 n，你写h(n) 来表示形成这样一个长度恰好为 n 的组件的方法数，那么你可以计算 h(n) as
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[=64的UID的方法数=].那么你有
f(n) = h(n) + sum h(i) * f(n-i-1) for i from 1 to n-2
第一项描述了单个组件的情况，而总和则处理了它由多个组件组成的情况。在这种情况下，您有一个长度为 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
如果你对所有 g(n) 求和 n 从 3 (最小可能的 UID 长度）到 64 你得到可能的 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)
虽然我的其他答案很好地处理了这个特定的应用程序，但这里有一个更通用的方法。它会处理您使用不同的正则表达式来描述相关语言的情况。它还允许相当长的字符串长度，因为它只需要 O(log n) 算术运算来计算长度最大为 n[= 的字符串的组合数81=]。在这种情况下，字符串的数量增长如此之快，以至于这些算术运算的成本将急剧增加，但对于其他类似情况，情况可能并非如此。
构建有限状态自动机
从您所用语言的正则表达式描述开始。将该正则表达式翻译成有限状态自动机。在您的情况下，正则表达式可以给出为
(([1-9][0-9]*)|0)(\.([1-9][0-9]*|0))+
自动机可能看起来像这样：
消除 ε 跃迁
这个自动机通常包含ε-转换（即不对应于任何输入字符的状态转换）。删除那些，以便一个转换对应于输入的一个字符。然后向接受状态添加一个 ε-转换。如果接受状态有其他传出转换，不要向它们添加 ε-循环，而是向没有传出边的接受状态添加一个 ε-转换，然后向其添加循环。这可以看作是在其末尾用 ε 填充输入，中间不允许 ε 。总而言之，此转换可确保准确执行 n 状态转换对应于处理 n 个字符或更少的输入。修改后的自动机可能如下所示：
注意两者都是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。生成的自动机可能比我这里手动构造的更复杂，但原理是一样的。
确保唯一路径
你不必让自动机 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 也能确保这个较弱的 属性，所以去吧，除非你可以确保没有这个的唯一路径。在我的示例中，每个组件的长度清楚地规定了要使用的路径，因此我没有使其具有确定性。但我在本 post.
末尾包含了一个确定性方法的示例
构建转换矩阵
接下来，记下转换矩阵。将行和列与您的状态相关联（在我的示例中，顺序为 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 开始情况被编码为 (1,0,0,0,0,0)，这意味着只有一种方式可以结束开始状态）并总结所有对应于接受状态的条目（在这种情况下只有最后一个）。这个矩阵的64次方左下角的元素是
1474472506836676237371358967075549167865631190000000000000000000000
这证实了我的另一个答案。
高效计算矩阵幂
为了实际计算该矩阵的 64 次方，最简单的方法是重复平方：对矩阵进行 6 次平方后得到的指数为 26 = 64 . 如果在其他一些情况下你的指数（即最大字符串长度）不是二的幂，你仍然可以通过根据指数的位模式乘以相关平方来执行 exponentiation by squaring 。这就是使这种方法采用 O(log n) 算术运算来计算字符串长度 n 的结果的原因，假设状态数固定且因此每个矩阵平方的成本都是固定的。
确定性自动机示例
如果你要使用通常的幂集构造使我的自动机具有确定性，你最终会得到
并将状态排序为 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次方相加得到与上述相同的结果。
根据 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 规则的可能性的数量？
阅读组织根/后缀规则清楚地表明我至少需要一个点（'.'）。在这种情况下，组合至少为 3 个字节 (char)，格式为：[0-9].[0-9]。在这种情况下，长度为 3 的 UID 有 10x10=100 种可能性。
看第一个回答，好像有不清楚的地方：
The first digit of each component shall not be zero unless the component is a single digit.
这意味着：
- “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
根 UID 部分的验证不在本问题的讨论范围内。第二个验证步骤可以负责拒绝一些不可能注册的 OID（例如，有些人提到对第一和第二弧的限制）。为简单起见，我们将接受所有可能的（有效的）根 UID。
单一成分
首先寻找形成单个组件的方法。单个组件对应的正则表达式为
0|[1-9][0-9]*
所以它要么是零，要么是一个非零数字，后跟任意多个零数字。 （一开始我错过了可能的唯一零情况，但 malat 的评论让我意识到了这一点。）如果这样一个组件的总长度是 n，你写h(n) 来表示形成这样一个长度恰好为 n 的组件的方法数，那么你可以计算 h(n) as
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[=64的UID的方法数=].那么你有
f(n) = h(n) + sum h(i) * f(n-i-1) for i from 1 to n-2
第一项描述了单个组件的情况，而总和则处理了它由多个组件组成的情况。在这种情况下，您有一个长度为 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
如果你对所有 g(n) 求和 n 从 3 (最小可能的 UID 长度）到 64 你得到可能的 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)
虽然我的其他答案很好地处理了这个特定的应用程序，但这里有一个更通用的方法。它会处理您使用不同的正则表达式来描述相关语言的情况。它还允许相当长的字符串长度，因为它只需要 O(log n) 算术运算来计算长度最大为 n[= 的字符串的组合数81=]。在这种情况下，字符串的数量增长如此之快，以至于这些算术运算的成本将急剧增加，但对于其他类似情况，情况可能并非如此。
构建有限状态自动机
从您所用语言的正则表达式描述开始。将该正则表达式翻译成有限状态自动机。在您的情况下，正则表达式可以给出为
(([1-9][0-9]*)|0)(\.([1-9][0-9]*|0))+
自动机可能看起来像这样：
消除 ε 跃迁
这个自动机通常包含ε-转换（即不对应于任何输入字符的状态转换）。删除那些，以便一个转换对应于输入的一个字符。然后向接受状态添加一个 ε-转换。如果接受状态有其他传出转换，不要向它们添加 ε-循环，而是向没有传出边的接受状态添加一个 ε-转换，然后向其添加循环。这可以看作是在其末尾用 ε 填充输入，中间不允许 ε 。总而言之，此转换可确保准确执行 n 状态转换对应于处理 n 个字符或更少的输入。修改后的自动机可能如下所示：
注意两者都是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。生成的自动机可能比我这里手动构造的更复杂，但原理是一样的。
确保唯一路径
你不必让自动机 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 也能确保这个较弱的 属性，所以去吧，除非你可以确保没有这个的唯一路径。在我的示例中，每个组件的长度清楚地规定了要使用的路径，因此我没有使其具有确定性。但我在本 post.
末尾包含了一个确定性方法的示例构建转换矩阵
接下来，记下转换矩阵。将行和列与您的状态相关联（在我的示例中，顺序为 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 开始情况被编码为 (1,0,0,0,0,0)，这意味着只有一种方式可以结束开始状态）并总结所有对应于接受状态的条目（在这种情况下只有最后一个）。这个矩阵的64次方左下角的元素是
1474472506836676237371358967075549167865631190000000000000000000000
这证实了我的另一个答案。
高效计算矩阵幂
为了实际计算该矩阵的 64 次方，最简单的方法是重复平方：对矩阵进行 6 次平方后得到的指数为 26 = 64 . 如果在其他一些情况下你的指数（即最大字符串长度）不是二的幂，你仍然可以通过根据指数的位模式乘以相关平方来执行 exponentiation by squaring 。这就是使这种方法采用 O(log n) 算术运算来计算字符串长度 n 的结果的原因，假设状态数固定且因此每个矩阵平方的成本都是固定的。
确定性自动机示例
如果你要使用通常的幂集构造使我的自动机具有确定性，你最终会得到
并将状态排序为 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次方相加得到与上述相同的结果。