语言特性的Damerau-Levenshtein距离

Question

对于说荷兰语的人来说，两个字符"ij“被认为是一个字母，很容易与"y”交换。

对于我正在做的一个项目，我希望有一个Damerau–Levenshtein distance的变体，它计算"ij“和"y”之间的距离为1，而不是当前的值2。

我自己也试过了，但是失败了。我的问题是，我不知道如何处理两个文本长度不同的事实。有没有人有关于如何解决这个问题的建议/代码片段？

谢谢。

Answer 1

维基百科的那篇文章中的术语相当松散。在“自然语言”中没有“字符串”这样的东西。自然语言中的音素可以通过书写字符和字符组合来表示。

一些字符组合是保留到现代的历史惯例的遗迹，比如在现代英语中，"gh“可能听起来像-f-，或者根本不发音。在我看来，在关注原始的“字符串”时，算法必须对语言和拼写约定的历史关系不可知，这导致了当字符组合与单个音素相关时产生一些任意的度量。它如何衡量“粗糙”到“联阵”？或者“通过”到“通过”？或者德语的"oe“变音？

在您的例子中，-y-可以与-ij-进行语音和拼写互换。那么，根据算法，是两次删除后插入，还是一次删除-j-或-i-，然后将剩余字符转置为-y-？或者-ij-正在合并，合并之后是转置？

在应用算法之前，我建议您使用另一个未使用的组合字符-ij-，可能是带有沉重重音的拉丁小写字母i U00EC。

该算法如何处理多个码点字符？

Answer 2

D-L距离本身不会为你处理它，因为它测量距离的方式。

因为这里不涉及代码(或语言)，所以我只能给您一个建议，以确保所有字符串都遵循相同的结构。

为了澄清你提出的一般问题，

请记住，D-L距离对字符进行比较，实际上并不读取字符串本身，因此您必须在比较之前进行解析，因为ij不应该与y交换的情况会导致其他问题。

Answer 3

一个想法是将每个字符串翻译成某种构造的正字法表示，其中有向词"ij“和英语的"gh”"th“和friends只有一个字符长。在执行Damerau-Levenshtein时，距离度量不必对所有类型的替换对象都相等，因此您可以使用任何您想要的惩罚，但是表需要在本地填充，因此您确实希望每个声音都是表中的一个单元格。

然而，当"ij“不是"ij”而是拼写错误或位于分词边界时(我不知道在荷兰语中是否会发生这种情况)，或者在任何其他情况下，它实际上不是一个有向图(意思是)，这种情况就会中断。

否则你将需要做一些环视，这将使事情变得复杂，但不应该改变算法的增长顺序(我相信)，如果你只看周围固定数量的单元。不过，恒定的因素仍然会大得多。