我正在寻找专门用于处理歧义的算法或数据结构。
在我当前特别感兴趣的领域中，我正在研究自然语言的模棱两可的解析，但我认为在计算中一定有许多领域中模棱两可起了作用。
我可以找到很多关于试图避免歧义的信息，但在如何接受歧义和分析歧义数据方面却很少。
假设解析器生成这些替代标记流或解释：
A B1 CA B2 CA B3 B4 C可以看出，流的某些部分在解释（A... B）之间共享，而其他部分分支为替代解释，并且经常与主流相遇。
当然，可能还有更多的解释，替代方案的嵌套，以及没有主流的解释。
这显然是某种带有节点的图。我不知道它是否有固定的名称。
是否有我可以研究的现有算法或数据结构旨在处理这种模棱两可的图？
鉴于您的问题的普遍性，我试图匹配这种普遍性。
一旦您考虑f: A -> B非单射的映射或函数，就会出现歧义的概念。
单射函数（也称为一对一函数）是这样的，当 a≠a' then f(a) ≠ f(a')。给定一个函数 f，您通常对反转它感兴趣：给定 f 的共域 B 的元素 b，您想知道域 A 的哪个元素 a 是这样的f(a)=b。请注意，如果函数不是满射的（即到），则可能没有。
当函数不是单射时，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
第一行是关于 P 人发生的句子生成，第二行是关于 Q 人发生的句子分析。函数s代表语音传输，应该是身份函数。函数 f'、g' 和 h' 应该是函数 f、g 和 h 的逆函数，这些函数计算连续的表示，直至想法的口头表示。但是这些函数中的每一个都可能是非单射的（通常是），因此在每个级别都引入了歧义，使得 Q 很难反转然后从它接收的声音序列中检索原始含义（我故意使用单词sound来避免进入细节）。相同的图表适用于书面交流，但在细节上有一些变化。
我们忽略 f 和 f'，因为它们与语义有关，这可能不太正式，而且我没有能力。语法树通常由语法形式定义（这里我跳过了重要的改进，例如特征结构，但可以考虑它们）。
函数 g 和函数 h 通常都不是单射的，因此是歧义的来源。由于语音链固有的各种错误，实际上还有其他歧义来源，但为了简单起见，我们将忽略它，因为它不会太大改变问题的性质。由于句子生成或传输，或由于说话者和听者之间的语言规范不匹配而导致的错误的存在，是一个额外的歧义来源，因为听者试图纠正潜在的错误而不知道它们可能是什么或它们是否存在于全部。
我们假设听者不会犯错误，并且他试图根据自己的语言标准和知识（包括错误来源和统计知识）最好地“解码”句子。
给定一个声音序列，听力系统必须将词汇生成函数 g 的效果与函数 g' 进行反演。第一个问题是几个不同的词可能给出相同的声音序列，这是歧义的第一个来源。第二个问题是听力系统实际上接收到的是对应于一串单词的序列，并且可能没有指示单词从哪里开始或从哪里结束。因此，它们可能是将声音序列切割成对应于可识别单词的子序列的不同方式。当噪声在单词之间造成更多混淆时，这个问题可能会变得更糟。
一个例子是以下从网络上摘录的全息诗，它们的发音或多或少相似：
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 ...
这使得词法分析模棱两可。
概率可用于选择最佳序列。但也可以保留所有可能的阅读的歧义，并在句子分析的下一阶段使用它。
请注意，单词 lattice 可以看作是一个有限状态自动机，它生成或识别单词序列的所有可能的词汇阅读
句法结构通常基于上下文无关的语法框架。上下文无关语言的歧义问题是众所周知的并且被分析过。已经设计了许多通用的 CF 解析器来解析模棱两可的句子，并产生一个结构（略有不同），从中可以提取所有的解析。这种结构被称为解析森林或共享解析森林。
已知的是，在语言语法被二值化的条件下，即在每个规则右侧（或更多简单地说，每个规则右侧的符号不超过 2 个）。
实际上，所有这些通用 CF 解析算法或多或少都是围绕一个简单概念的复杂变体：有限状态自动机 A 的语言 L(A) 与 CF 文法 G 的语言 L(G) 的交集。一个交集可以追溯到关于上下文无关语言的早期论文（Bar-Hillel、Perles 和 Shamir 1961），旨在作为闭包属性的证明。在1995 年的一篇论文中，花了大约 30 年才意识到它也是一个非常通用的解析算法 。
这种经典的叉积构造为两种语言 L(A) 和 L(G) 的交集产生了一个 CF 语法。如果您考虑将要解析的句子w表示为一系列词汇元素，那么它也可以视为仅生成句子w的有限状态自动机W。例如：
this is a finite state automaton
=> (1)------(2)----(3---(4)--------(5)-------(6)-----------((7))
是一个有限状态自动机 W，只接受句子 w =“这是一个有限状态自动机”。所以 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生成的句子w具有与语法 G 完全相同的分析树（因此具有相同的歧义），直到对非终结符进行简单的重命名。
文法 G_ w是w的（共享）解析森林，而w的解析树集正是该文法的派生集。因此，这提供了一个非常简单的视图来组织概念，并解释共享解析森林和通用 CF 解析器的结构。
但它还有更多内容，因为它展示了如何泛化到不同的语法和要解析的不同结构。
通过叉积构造与常规集合的交集的建设性闭包对于许多将 CF 语法的力量扩展到上下文敏感领域的语法形式来说是很常见的。这包括树相邻语法和线性上下文无关重写系统。因此，这是关于如何为这些更强大的形式主义构建可以处理歧义并产生共享解析森林的通用解析器的指南，它们只是相同类型的专门语法。
另一种概括是，当存在词汇歧义，使得词汇分析产生许多由词格共享表示的候选句子时，该词格可以被解读为识别所有这些句子的有限状态自动机。然后，相同的交集构造将消除所有不在该语言中（非语法）的句子，并生成一个 CF 语法，该语法是一个共享解析森林，用于从词格中对所有可接受的（语法）句子进行所有可能的解析。
如问题所要求的，只要与可用的语言或话语信息兼容，所有可能的歧义读数都会被保留。
噪声和格式错误的句子的处理通常也使用有限状态设备进行建模，因此可以通过相同的技术来解决。
其实还有很多其他的问题需要考虑。例如，建立共享林的方法有很多种，或多或少都有共享。用于预编译下推自动机以用于一般无上下文解析的技术对共享的质量有影响。太聪明并不总是很聪明。
另请参阅我在 SE 上就该主题所做的其他答案：
我正在试验PFG ——使用 Marpa::R2 ASF 构建的Parse-Forest Grammars 。
该方法是将歧义解析表示为语法，设计一个标准来修剪不需要的规则，应用它，然后从 PFG 中删除非生产性和不可访问的符号，从而得到解析树。
这个测试用例是一个例子：它解析具有高度歧义语法的算术表达式，然后根据关联性和优先级修剪 PFG 规则，清理语法，将其转换为抽象语法树（来自引用来源的问题 3.10 — Grune 和 Jacobs） .
我将此数据结构称为lattice，例如参见Lexicalized Parsing (PDF)。