将字符串与拼写错误匹配的快速方法
Fast way to match strings with typo
我有一个巨大的字符串列表（城市名称），即使用户打错了我也想找到城市的名称。
Example
User types "chcago" and the system finds "Chicago"
当然，我可以为列表中的所有字符串计算查询的编辑距离，但这会非常慢。
有什么有效的方法可以执行这种字符串匹配吗？
我认为基本思想是使用 Levenshtein 距离，但在名称的子集上。如果名称足够长，一种可行的方法是使用 n-gram。您可以存储 n-gram，然后使用更有效的技术来表示至少 x 个 n-gram 需要匹配。 las，您的示例拼写错误有 2 个与 Chicago 匹配的 3-grams（满分 5 个）（除非您计算开头和结尾的部分）。
对于较短的名字，另一种方法是存储每个名字中的字母。所以，"Chicago" 会变成 6 "tuples"："c"、"h"、"i"、"a"、"g"、"o".您会对输入的名称执行相同的操作，然后要求 4 或 5 匹配。这是一个相当简单的匹配操作，因此可以进行得相当快。
然后，在这个缩小的集合上，应用 Levenshtein 距离来确定最接近的匹配项。
您要求在不使用 Levenshtein 的情况下确定 Levenshtein。
您必须确定单词在被识别之前可以偏离多远，并查看应用这种不太准确的算法是否可以接受。例如，您可以查找常用切换类型的字母并将其限制为该字母。或应用此 paper 中的 first/last 字母规则。您还可以假设前几个字母是正确的，然后在排序列表中查找城市，如果没有找到，则将 Levenshtein 应用于 n-1 和 n+1 个单词，其中 n 是最后一次查找的位置（或者它的一些变体）。
有几种想法，但我认为如果没有更多假设，就没有一个最佳解决方案可以解决您的问题。
根据 Levenshtein 距离（或任何其他服从三角不等式的度量）在文本字符串上搜索模糊匹配的有效方法是 Levenshtein automaton. It's implemented in a Lucene project (Java) and particulary in a Lucene.net project (C#)。此方法速度快，但实现起来非常复杂
我有一个巨大的字符串列表（城市名称），即使用户打错了我也想找到城市的名称。
Example
User types "chcago" and the system finds "Chicago"
当然，我可以为列表中的所有字符串计算查询的编辑距离，但这会非常慢。
有什么有效的方法可以执行这种字符串匹配吗？
我认为基本思想是使用 Levenshtein 距离，但在名称的子集上。如果名称足够长，一种可行的方法是使用 n-gram。您可以存储 n-gram，然后使用更有效的技术来表示至少 x 个 n-gram 需要匹配。 las，您的示例拼写错误有 2 个与 Chicago 匹配的 3-grams（满分 5 个）（除非您计算开头和结尾的部分）。
对于较短的名字，另一种方法是存储每个名字中的字母。所以，"Chicago" 会变成 6 "tuples"："c"、"h"、"i"、"a"、"g"、"o".您会对输入的名称执行相同的操作，然后要求 4 或 5 匹配。这是一个相当简单的匹配操作，因此可以进行得相当快。
然后，在这个缩小的集合上，应用 Levenshtein 距离来确定最接近的匹配项。
您要求在不使用 Levenshtein 的情况下确定 Levenshtein。
您必须确定单词在被识别之前可以偏离多远，并查看应用这种不太准确的算法是否可以接受。例如，您可以查找常用切换类型的字母并将其限制为该字母。或应用此 paper 中的 first/last 字母规则。您还可以假设前几个字母是正确的，然后在排序列表中查找城市，如果没有找到，则将 Levenshtein 应用于 n-1 和 n+1 个单词，其中 n 是最后一次查找的位置（或者它的一些变体）。
有几种想法，但我认为如果没有更多假设，就没有一个最佳解决方案可以解决您的问题。
根据 Levenshtein 距离（或任何其他服从三角不等式的度量）在文本字符串上搜索模糊匹配的有效方法是 Levenshtein automaton. It's implemented in a Lucene project (Java) and particulary in a Lucene.net project (C#)。此方法速度快，但实现起来非常复杂