处理歧义的算法或数据结构

Question

我正在寻找专门用于处理歧义的算法或数据结构。

在我当前感兴趣的特定领域中，我正在研究自然语言的歧义解析，但我认为在计算中一定有许多领域存在歧义。

我可以在尝试避免歧义方面找到很多东西，但在如何接受歧义和分析歧义数据方面却知之甚少。

假设解析器生成这些替代 token 流或解释:

A B1 C

A B2 C

A B3 B4 C

可以看出，流的某些部分在解释之间共享( A ... B )，而其他部分分支为替代解释并经常与主流相遇。

当然，可能还有更多的解释，替代方案的嵌套，以及没有主流的解释。

这显然是某种带有节点的图。我不知道它是否有一个既定的名称。

是否有我可以研究的现存算法或数据结构旨在处理这种模棱两可的图？

Answer 1

自然语言解析中的歧义和共享

歧义和一般共享

鉴于你的问题的普遍性，我试图匹配
概论。

当您考虑一个不是单射的映射或函数 f: A -> B 时，歧义的概念就会出现。

单射函数(也称为一对一函数)就是这样一个
当 a≠a' 那么 f(a) ≠ f(a') 。给定一个函数 f，你经常
有兴趣反转它:给定 f 的 codomain B 的元素 b，
您想知道域 A 的哪个元素 a 是 f(a)=b 。
请注意，如果函数不是满射的，则可能没有
(即到)。

当函数不是单射时，A中可能有几个值a
这样 f(a)=b 。换句话说，如果你使用 B 中的值来实际
通过映射 f 表示 A 中的值，你有一个不明确的
可能无法唯一确定值 a 的表示 b。

由此你意识到歧义的概念是如此普遍以至于
不太可能有关于它的统一知识体系，
即使将其限制为计算机科学和编程。

但是，如果您想考虑反转创建这样的函数
歧义，例如计算集合 f'(b)={a∈A | f(a)=b} ，或
根据某些最优性标准，该集合中的最佳元素，
有一些技巧可以在以下情况下帮助您
问题可以分解为经常重复出现的子问题
具有相同的论点。然后，如果你记住了结果
遇到的各种参数组合，你永远不会计算两次
同样的事情(据说子问题是 memo-ized )。注意
子问题也可能存在歧义，因此可能有几个
某些子问题实例的答案，或其中的最佳答案
其他几个。

这相当于在所有子问题之间共享一个子问题的副本
需要用这组参数解决它的情况。这
整个技术称为 dynamic programming ，难度为
经常找到正确的分解子问题。动态的
编程主要是一种共享重复子计算的方法
解决方案，以降低复杂性。但是，如果每个子计算
产生一个结构的片段，在
更大的结构来找到一个结构化对象的答案(一个
例如图)，那么 子计算步骤的共享可能会导致
在它所在的所有地方也共享一个相应的子结构
需要 。当要找到许多答案时(因为对
例如)，这些答案可以共享子部分。

而不是找到所有的答案，可以使用动态规划
找到满足某些最优性标准的那些。这要求
问题的最优解使用以下最优解
子问题。

语言加工案例

在语言学和语言的情况下，事情可以更具体
加工。为此，您必须确定您所在的域
处理，以及您在这些域中使用的函数类型。

语言的目的是交流信息、概念、思想
存在于我们的大脑中，非常近似的假设是
我们的大脑使用相同的功能来表示这些想法
语言上。我还必须大大简化事情(对不起
它)因为这不是一个完整的理论的地方
语言，无论如何都会有争议。我什至不能考虑
所有类型的句法理论。

因此，从一个人 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。第一个
问题是几个不同的词可能发出相同的声音
序列，这是歧义的第一个来源。第二个问题是
听音系统实际接收到相应的序列
到一串单词，并且可能没有指示单词的位置
开始或结束。所以它们可能是不同的切割声音的方式
序列成对应于可识别单词的子序列。
当噪音造成更多困惑时，这个问题可能会恶化
字之间。

一个例子是以下全息诗节 taken from the web ，即
或多或少类似地发音:

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 个
右侧(或更简单地说，每个规则中不超过 2 个符号
右侧)。

其实这些通用的CF解析算法都差不多
围绕一个简单概念的复杂变化:交集
有限状态自动机 A 的语言 L(A) 和语言 L(G)
CF 文法 G. 这种交集的构造可以追溯到
关于上下文无关语言的早期论文 ( Bar-Hillel, Perles andShamir 1961)，旨在作为闭包属性的证明。花了
大约 30 年才意识到它也是一个非常通用的解析算法
1995 paper。

这种经典的叉积构造为
两种语言 L(A) 和 L(G) 的交集。如果你考虑一个
要解析的句子 w，表示为词法元素序列，
它也可以被视为有限状态自动机 W，它只生成
句子 w。例如:

        this     is    a     finite     state     automaton
 => (1)------(2)----(3---(4)--------(5)-------(6)-----------((7))

是一个仅接受句子的有限状态自动机 W
w="这是一个有限状态自动机"。所以 L(W)={w}。

如果语言的语法是 G，那么交集
构造给出了该语言的语法 G_w
L(G_w)=L(W)∩L(G)。

如果句子 w 不在 L(G) 中，则 L(G_w) 为空，并且
句子不被识别。否则 L(G_w)={w}。此外，这时
很容易证明语法 G_w 生成了句子 w
与语法完全相同的解析树(因此具有相同的歧义)
G，最多对非终结符进行简单的重命名。

语法 G_w 是 w 的(共享)解析森林，以及
w 的解析树正是具有这个的推导集
语法。所以这给出了一个非常简单的组织概念的 View ，并且
解释共享解析森林和通用 CF 解析器的结构。

但还有更多内容，因为它展示了如何推广到
不同的语法和不同的结构来解析。

与正则集相交的 build 性闭包
交叉产品结构在很多语法中都很常见
将 CF 文法的力量扩展到
上下文敏感的领域。这包括树邻接文法，以及
线性上下文无关重写系统。因此，这是一个指导方针
如何为这些更强大的形式主义构建通用解析器
可以处理歧义并产生共享的解析森林，这很简单
相同类型的专门语法。

另一种概括是，当存在词汇歧义时
词法分析产生许多表示的候选句子
通过一个词格共享，这个词格可以读作一个
识别所有这些句子的有限状态自动机。那么，同样
交集构造将消除所有不在的句子
语言(非语法)，并产生一个 CF 语法
共享解析森林，用于所有可接受的所有可能的解析
(语法)词格的句子。

根据问题的要求，所有可能的歧义读数都是
只要与可用的语言或话语兼容，就可以保留
信息。

噪音和格式错误的句子的处理通常也被建模
具有有限状态设备，因此可以由相同的
技术。

其实还有很多其他的问题需要考虑。例如，
构建共享森林的方法很多，或多或少
分享。用于将下推自动机预编译为的技术
用于一般上下文无关解析我对质量有影响
的分享。太聪明并不总是很聪明。

另请参阅其他答案 我在 SE 上就该主题进行了讨论:

https://cs.stackexchange.com/questions/27937/how-do-i-reconstruct-the-forest-of-syntax-trees-from-the-earley-vector/27952#27952

https://cstheory.stackexchange.com/questions/7374/recovering-a-parse-forest-from-an-earley-parser/18006#18006