algorithm - 如何将 Levenshtein 距离应用于一组目标字符串？

Question

• 令 TARGET 成为我希望被说出的一组字符串。
• 设 SOURCE 为语音识别器返回的字符串集(即它可能听到的句子)。

我需要一种从 TARGET 中选择字符串的方法。我读到了Levenshtein 距离 和Damerau-Levenshtein 距离，它基本上返回源字符串和目标字符串之间的距离，即转换所需的更改次数将源字符串转换为目标字符串。

但是，我如何将此算法应用于一组目标字符串？

我想我会使用以下方法:

1. 对于属于TARGET 的每个字符串，我计算与SOURCE 中每个字符串的距离。通过这种方式，我们获得了一个m×n矩阵，其中n是SOURCE的基数，n是TARGET的基数。我们可以说第 i 行表示语音识别器检测到的句子与第 i 个目标的相似度。
2. 计算每行值的平均值，可以得到第i个目标与语音识别器输出之间的平均距离。我们称它为 average_on_row(i)，其中 i 是行索引。
3. 最后，对于每一行，我计算该行中所有值的标准差。对于每一行，我还计算了所有标准差的总和。结果是一个列向量，其中每个元素(我们称它为 stadard_deviation_sum(i))指的是 TARGET 的字符串。

与最短的stadard_deviation_sum 关联的字符串可能是用户发音的句子。能算是我用的正确方法吗？或者还有其他方法吗？显然，过高的值表示用户发音的句子很可能不属于TARGET。

Answer 1

我不是专家，但您的建议没有意义。首先，在实践中，我希望 TARGET 的基数即使不是无限的也非常大。其次，我不相信 Levensthein 距离或一些类似的相似性度量会有用。

如果:

• 您真的可以定义 SOURCE 和 TARGET 集，
• SOURCE 中的所有字符串都是等概率的，
• TARGET 中的所有字符串都是等概率的，
• SOURCE 和 TARGET 中的字符串不是字符而是音素，

然后我相信你最好的选择是在 SOURCE 中找到 p 对，在 TARGET 中找到 q 使得 distance(p,q) 最小。特别是你不能保证等概率部分，我认为你应该从头开始思考这个问题，做一些研究并做出完全不同的设计。语音识别的常用方法是使用隐马尔可夫模型。我会从那里开始。

回答您的评论:选择最有可能的。如果不考虑概率，那是没有希望的。

[假设下面的例子是关于音素，而不是字符]

假设识别的单词是“chees”。设定的目标是“奶酪”、“国际象棋”。您必须计算 P(cheese|chees) 和 P(chess|chees) 我想说的是，并非每个替换都是等概率的。如果您将概率建模为字符串之间的距离，那么至少您必须允许，例如 d("c","s") < d("c","q") 。 (混淆 c 和 s 字母很常见，但混淆 c 和 q 并不常见)采用距离计算算法很容易，为所有对提供良好的值很困难。

此外，您还必须以某种方式估计 P(cheese|context) 和 P(chess|context) 如果我们谈论的是棋盘游戏，则更有可能是国际象棋。如果我们谈论的是乳制品，则更有可能是奶酪。这就是为什么您需要大量数据才能得出此类估算值的原因。这也是隐马尔可夫模型适用于此类问题的原因。