compare - 语言特定怪癖的 Damerau-Levenshtein 距离

Question

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

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

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

谢谢。

Answer 1

维基百科文章的术语相当松散。“自然语言”中没有“字符串”之类的东西。自然语言中的音素可以用书写字符和字符组合来表示。

一些字符组合是保留到现代的历史惯例的遗迹，例如在现代英语“rough”中，“gh”可以听起来像 -f- 或根本不发声。在我看来，在关注原始“字符串”时，算法必须不知道语言和正字法约定的历史关系，这会在字符组合与单个音素相关时导致一些任意度量。它如何衡量“粗糙”到“ruf”？还是“通过”到“通过”？还是德语 o-umlaut 到“oe”？

在您的情况下，-y- 可以与 -ij- 进行语音和拼写交换。那么根据算法，两个删除后插入一个，还是一个删除 -j- 或 -i- 然后将剩余字符转置为 -y- 是什么？或者是 -ij- 被合并并且合并之后是转置？

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

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

Answer 2

好吧，DL 距离本身不会为您处理它，因为它测量距离的方式。

由于这里没有涉及代码（或语言），我只能给您一个建议，以确保所有字符串都遵循相同的结构。

为了澄清自您笼统地询问以来的情况，

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

Answer 3

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

但是，当“ij”不是“ij”而是拼写错误或在分词边界（我不知道这是否会在荷兰语中发生）或在任何其他情况下实际上不是（意思是as) 一个有向图。

否则你需要做一些环顾四周，这会使事情复杂化，但不应该改变算法的增长顺序（我相信），只要你只看周围恒定数量的细胞。不过，常数因素仍然会大得多。