string - 将字符串与拼写错误匹配的快速方法

Question

我有一个巨大的字符串列表(城市名称)，即使用户打错了我也想找到城市的名称。

Example

User types "chcago" and the system finds "Chicago"

当然，我可以为列表中的所有字符串计算查询的编辑距离，但这会非常慢。

有什么有效的方法可以执行这种字符串匹配吗？

Answer 1

我认为基本思想是使用 Levenshtein 距离，但在名称的子集上。如果名称足够长，一种可行的方法是使用 n-gram。您可以存储 n-gram，然后使用更有效的技术来表示至少 x 个 n-gram 需要匹配。 las，您的示例拼写错误有 2 个与 Chicago 匹配的 3-grams(满分 5 个)(除非您计算开头和结尾的部分)。

对于较短的名称，另一种方法是存储每个名称中的字母。因此，“芝加哥”将变成 6 个“元组”:“c”、“h”、“i”、“a”、“g”、“o”。您会对输入的名称执行相同的操作，然后要求 4 或 5 匹配。这是一个相当简单的匹配操作，因此可以进行得非常快。

然后，在这个缩减的集合上，应用 Levenshtein 距离来确定最接近的匹配是什么。