我正在寻找专门用于处理歧义的算法或数据结构。
在我目前特别感兴趣的领域中，我正在研究自然语言的歧义解析，但我认为在计算领域中一定有许多歧义起作用。
我可以找到很多关于如何避免歧义的内容，但是关于如何接受歧义和分析歧义数据的内容却很少。
假设解析器生成这些可选的令牌流或解释:
A B1 CA B2 CA B3 B4 C
可以看出，流的某些部分在解释(A…B)和其他部分分支成不同的解释，并经常与主流相遇。
当然可能有更多的解释，替代的嵌套，以及没有主流的解释。
这显然是某种有节点的图。我不知道它是否有一个既定的名称。
是否有现有的算法或数据结构，我可以研究，旨在处理这种模棱两可的图?
自然语言解析中的歧义与共享
一般意义上的歧义和共享
考虑到你问题的普遍性，我正试图匹配它普遍性。
当你考虑一个非内射的映射或函数f: A -> B时，歧义的概念就出现了。
内射函数(也称为一对一函数)就是这样一个函数当a≠a'时，则为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}，或根据某些最优性准则在该集合中的最佳元素，确实有一些技巧可以帮助你在这种情况下问题可以分解为经常重复出现的子问题用同样的论点。然后，如果你记住了考试的结果遇到的各种参数组合，永远不会计算两次同样的事情(子问题被称为备忘)。请注意,子问题也可能存在歧义，因此可能有几个某些子问题实例的答案，或其中的最优答案其他几个人。
这相当于在所有的需要用这组参数求解的情况。的整个技术称为动态规划，其难点在于通常找到正确的分解成子问题。动态编程主要是一种共享a的重复子计算的方法解决方案，从而降低复杂性。但是，如果每个子计算中递归重用的结构的片段更大的结构来寻找答案，这是一个结构化对象(a)图(例如)，那么可能导致子计算步骤的共享在它所在的所有地方也共享一个相应的子结构需要。当许多答案被发现时(因为模棱两可)，这些答案可以共享子部分。
可以使用动态规划，而不是找到所有的答案找出满足最优性准则的模型。这就要求问题的最优解使用的是的最优解子问题。
语言处理案例
在语言学和语言的情况下，事情可以更具体处理。为此，您必须确定您所在的域处理这些域，以及在这些域中使用的函数类型。
语言的目的是交换信息、概念、思想它们存在于我们的大脑中，我们有一个非常近似的假设我们的大脑用同样的功能来表达这些想法语言。我还必须大大简化事情(对不起)因为这不是一个完整理论的地方语言，这是有争议的。我甚至不能考虑所有类型的语法理论
一个思想的语言信息交换，从一个人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很难然后从声音序列中提取原意它接收(我故意使用这个词的声音来避免接收到细节)。同样的图表，在细节上有些不同，用于书面交流。
我们忽略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.
声音序列的分析可以用有限状态进行非确定性自动机，用动态规划解释模式，它产生一个有向无环图，其中节点将单词的分隔和边缘与已识别的单词相对应。图上任何最长的路径都对应一个可能的路径将声音序列分析为单词序列。
上面的例子给出了(相当简单的)单词lattice(面向的)从左到右):
the-*-fun
/
Ms -*-- Stephen without --*-- a first -*- ...
/ / /
* * *
/ /
must --*-- even with -*- outer fur -*- ...
这样声音序列也可以对应下面的单词序列(包括其他几个):
Ms Stephen, with outer first-rate ...
Must, even with outer first-rate ...
这使得词法分析有歧义。
概率可用于选择最佳序列。但这也是尽可能保留所有可能的阅读中的歧义并加以利用在句子分析的下一阶段也是如此。
注意晶格这个词可以看作是一个有限状态自动机的所有可能的词汇解读词序列
句法歧义
语法结构通常基于上下文无关的语法骨架。上下文无关语言的歧义问题很好了解和分析。已经设计了许多通用CF解析器解析模棱两可的句子，并产生一个结构(变化)可以从中提取所有解析。这样的结构被称为解析森林，或共享解析森林。
已知的是，该结构在最坏的情况下可以是长度为的立方所分析的句子，在语言语法的条件下是二值化，即在每个规则中不超过2个非终结符右手边(或者更简单地说，每条规则中不超过2个符号)眼睛)。
实际上，所有这些通用的CF解析算法都或多或少复杂的变化围绕着一个简单的概念:交集有限状态自动机A的语言L(A)和语言L(G)这种交集的构造可以追溯到关于上下文无关语言的早期论文(Bar-Hillel, Perles和Shamir 1961)，并打算作为闭包性的证明。花了大约三十年后才意识到，它也是一种非常通用的解析算法1995年的论文。
这个经典的交叉乘积构造为两种语言L(A)和L(G)的交集。如果你认为要解析的句子w，表示为词法元素序列;它也可以看作是有限状态自动机W，只产生句子w。例如:
this is a finite state automaton
=> (1)------(2)----(3---(4)--------(5)-------(6)-----------((7))
是一个只接受句子的有限状态自动机Ww="这是一个有限状态自动机"。L (W) = {W}。
如果语言的语法是G，那么交集构造给出了该语言的语法G_wL (G_w) = L (w)∩L (G)。
如果句子w不在L(G)中，则L(G_w)为空，则句子不被识别。其他的L (G_w) = {w}。此外，它是那时很容易证明语法G_w生成了带有的句子w与语法完全相同的解析树(因此具有相同的歧义)G，直到简单地重命名非终结符。语法G_w是w的(共享)解析林的集合的解析树w正是这个的派生集语法。这给出了一个非常简单的概念组织视图解释共享解析林和通用CF解析器的结构。
但还有更多，因为它展示了如何推广到不同的语法和不同的结构被解析。
正则集合交的构造闭包跨产品结构在很多语法中都很常见将CF语法的功能扩展到上下文敏感的领域。这包括树相邻语法和线性上下文无关的重写系统。因此，这是一个指导方针如何为这些更强大的形式化构建通用解析器呢可以处理歧义并生成共享的解析森林，这很简单相同类型的专门化语法。
另一个概括是，当存在词汇歧义时这种词法分析产生了许多候选句子由于由一个词格共享，这个词格可以读作有限状态自动机识别所有这些句子。然后，同样的交集结构将消除所有不在其中的句子语言(非语法)，并生成一个CF语法，该语法是为所有允许的所有可能的解析共享解析林(语法上的)句子来自单词格。
根据问题的要求，所有可能的歧义读数都是保留的:与可用的语言或话语相适应的时间信息。
对噪音和病态句子的处理通常也进行建模具有有限状态的器件，因此可以通过相同的方式进行寻址技术。
实际上还有许多其他问题需要考虑。例如,建立共享森林的方法有很多，或多或少共享。用于将下推自动机预编译为用于一般的无上下文解析可能对质量有影响分享。太聪明未必聪明。
参见其他答案我在这个话题上做了一个SE:
27952https://cs.stackexchange.com/questions/27937/how-do-i-reconstruct-the-forest-of-syntax-trees-from-the-earley-vector/27952
https://cstheory.stackexchange.com/questions/7374/recovering-a-parse-forest-from-an-earley-parser/18006 # 18006
我在<我>PFGs——Parse-Forest语法使用Marpa::R2 ASF.
该方法是将歧义解析表示为语法，设计一个标准来修剪不需要的规则，应用它，然后从PFG中删除非生产性和不可访问的符号，从而到达解析树。
这个测试用例是一个说明:它解析具有高度模糊语法的算术表达式，然后根据结合性和优先级修剪PFG规则，清理语法，将其转换为抽象语法树(来自引用的来源- Grune和Jacobs的问题3.10)。
我把这个数据结构称为格，参见Lexicalized Parsing(PDF)。