使用自定义字符映射的Levenshtein算法

Question

我希望使用Levenshtein算法在字符串列表中进行搜索。为了能够输入拉丁字符并搜索带有希腊字符的项目，我想要实现自定义字符映射。

映射示例：

a = α, ά
b = β
i = ι,ί,ΐ,ϊ
... (etc)
u = ου, ού

在一个列表中使用abu进行搜索：

• αbu
• abού
• αού（所有希腊字符）

将返回列表中的所有项。（项目顺序不是问题）

如何在算法中应用映射？（这里是我开始的地方）

- Odys

---

Levenshtein算法基于编辑距离度量比较两个字符串。它通常定义一个替换规则，看起来可以涵盖你所说的内容。获取一些示例代码（示例代码通常会替换A-Z，而不考虑字符），然后将其替换为您特定的替换规则即可。 - Jeff Foster

@Jon 我如何在算法中应用映射？ - Odys

Answer 1

我认为最好的方法是预处理您的符号，使其变成一种确定的形式（例如全部使用拉丁字母），然后像平常一样使用Levenshtein算法。

伪代码如下：

int func(String latinStr, String greekStr) {
   String mappedStr = convertToLatin(greekStr); // e.g. now αβ would be ab 
   return Levenstein(latinStr, mappedStr);
}

在convertToLatin中，您可以逐个字符地使用包含映射替换的字典，并构建新字符串。

- om-nom-nom

---

你所指的过程被称为“规范化”。 - Nick Johnson