我正在寻找用于处理歧义的算法或数据结构。
在我目前感兴趣的领域中，我正在研究自然语言的歧义解析，但我认为在计算机领域中必定有许多涉及歧义的应用。
我可以找到很多关于避免歧义的内容，但很少有关于如何应对歧义并分析歧义数据的内容。
假设一个解析器生成了这些替代的标记流或解释：
A B1 CA B2 CA B3 B4 C可以看出流的某些部分在解释之间共享（A ... B），而其他部分则会分支成备选解释，并经常重新汇入主流。
当然，可能会有更多的解释、备选方案的嵌套和没有主流的解释。
显然，这是一种具有节点的图形。我不知道它是否有一个已经确定的名称。
是否存在既有的算法或数据结构可以处理这种歧义性图形，我可以进行学习研究吗？
考虑到您的问题比较普遍，我尽量匹配这种普遍性。
当你考虑一个映射或函数 f: A -> B 不是单射时，就会出现歧义的概念。
单射函数（也称为一对一函数）是指当a≠a'时，f(a) ≠ f(a')。给定一个函数f，通常希望反转它：给定值域B中的元素b，你需要知道定义域A中的元素a是什么，使得f(a)=b。请注意，如果函数不是满射（即到），则可能没有这样的元素a。
当函数不是单射时，可能有几个值a在A中使得f(a)=b。换句话说，如果你使用B中的值通过映射f来实际表示A中的值，那么你就有了一个模糊的表示b，可能无法唯一地确定值a。
f'(b)={a∈A | f(a)=b}或者根据某种最优性准则计算该集合中的最佳元素，则确实有一些技术可以帮助您处理那些可以分解为子问题并且经常出现相同参数的情况。然后，如果您记住了遇到的各种参数组合的结果，您就不会重复计算相同的内容（子问题被称为memo-ized）。请注意，子问题可能存在歧义，因此某些子问题实例可能有多个答案或多个最优答案。在语言学和语言处理方面，事情可以更具体。为此，您必须确定您正在处理的领域以及您使用这些领域的功能类型。
语言的目的是交换我们大脑中存储的信息、概念和想法，假设我们的大脑使用相同的功能来用语言表达这些想法。我必须大大简化事情（对此我很抱歉），因为这并不是一个完整的语言理论的地方，而且即使有，也会引起争议。我甚至不能考虑所有类型的句法理论。
因此，从人P到人Q的语言信息交流如下：
idea in P ---f--> syntactic tree ---g--> lexical sequence ---h--> sound sequence
|
s
|
V
idea in Q <--f'-- syntactic tree <--g'-- lexical sequence <--h'-- sound sequence
函数g和函数h通常都不是单射的，因此会产生歧义。实际上，由于语音链中固有的各种错误，还有其他来源的歧义，但为简单起见，我们将忽略它，因为它并没有太大改变问题的本质。由于句子生成或传输，或者说话者和听者之间的语言规范不匹配，存在错误也是一个额外的歧义来源，因为听者试图在不知道可能存在的错误或是否存在的情况下纠正潜在的错误。
我们假设听者不会犯错，并且尽力根据自己的语言标准和知识，包括错误来源和统计数据，最好地“解码”句子。
Ms Stephen, without a first-rate stakeholder sum or deal,
Must, even with outer fur straight, stay colder - some ordeal.
上面的示例提供了（相当简单的）单词格子图（从左到右定向）：
the-*-fun
/ \
Ms -*-- Stephen \ without --*-- a first -*- ...
/ \ / \ /
* * *
\ / \ / \
must --*-- even with -*- outer fur -*- ...
Ms Stephen, with outer first-rate ...
Must, even with outer first-rate ...
this is a finite state automaton
=> (1)------(2)----(3---(4)--------(5)-------(6)-----------((7))
有限状态自动机W只接受句子w=“this is a finite state automaton”。因此，L(W)={w}。
如果语言的文法是G，则交集构造会为语言L(G_w)=L(W)∩L(G)提供一个文法G_w。
如果句子w不在L(G)中，则L(G_w)为空，该句子无法识别。否则，L(G_w)={w}。此外，可以轻松证明，文法G_w以与文法G完全相同的解析树（因此具有相同的歧义性），仅需对非终结符进行简单重命名即可生成句子w。
文法G_w是w的（共享）解析森林，而w的解析树集合恰好是使用此文法的推导集合。因此，这提供了一种非常简单的视图来组织概念，并解释共享解析森林和一般CF解析器的结构。
但这还不止，因为它展示了如何推广到不同的语法和不同的结构进行解析。处理噪声和格式不正确的句子通常也使用有限状态设备进行建模，因此可以使用相同的技术来解决。
实际上还有许多其他问题需要考虑。例如，有许多构建共享森林的方法，共享程度更高或更低。用于预编译下推自动机以用于一般上下文无关分析的技术可能会影响共享的质量。过于聪明并不总是非常聪明。
请参见我在此主题上在SE上提供的其他答案：