algorithm - 拼写检查城市名称？

Question

我认为这个问题比普通的拼写检查更容易，因为与所有已知的英语单词相比，美国城市的列表很小。

无论如何，这是问题所在：我有充满城市名称的文本文件；其中有些拼写正确，有些拼写不正确。

我可以使用什么样的算法来纠正城市名称的所有拼写错误？

Answer 1

您是否真的需要更正拼写错误或只是将它们标记为使用普通拼写检查器？如果是后者，您只需要获取正确拼写列表并确保每个名称与列表中的名称相同。

如果你想真正纠正它们，你可能想使用编辑距离的概念来比较拼写错误的字符串与参考列表中的相似度。然后，您可以用最接近的匹配替换拼写错误的单词。您可能还想处理目标城市不在您的列表中的可能性。

Levenshtein distance Wikipedia 文章是另一个很好的资源。

Answer 2

首先将正确的城市名称加载到数组中，然后遍历文件中的城市名称。通过查看当前城市名称是否在正确名称的数组中来检查当前城市名称的拼写是否正确。如果它不在数组中，请尝试将拼写错误单词的Soundex或Metaphone值与正确名称数组中的单词进行比较，以找到正确的拼写方式。

Answer 3

诀窍是知道该名称实际指的是哪个城市以及该城市名称的正确拼写方式。这与仅检查英语单词不同。

您要解决的真正任务是什么？您正在处理地址列表吗？您不应该为此编写自己的工具：整个行业都致力于这项看似简单的任务。:)

我必须为The Perl Review的订阅列表执行此操作。我已经非常熟悉世界各地不同邮局的网络服务。您通常可以访问邮政服务网站以获取地址的规范形式。有一些地理编码工具可以为您提供相同的数据。

Answer 4

我已经做到了。编辑距离方法是我所做的，它工作得很好，但是实时执行太慢了。

您将面临的一个挑战是，有许多城市与其他城市名称相距 1 编辑距离。你没有说文本文件中的名称来自哪里，这有很大的不同。在我的例子中，是随机输入城市名称进行搜索的人，他们偶尔会拼错他们想要的城市，但他们拼错的是一个真实的城市名称。在这种情况下，您必须对用户的意图进行一些猜测，一种简单的方法是考虑状态（如果提供）。

Answer 5

网络上有一些常见拼写错误的城市名称列表（例如 Pittsburg h）。除此之外，我和杰里米在一起。你只需要找到城市名称数据集，你可能想试试 USGS。Zillow 有您可能可以使用的社区数据。

Answer 6

如果同一城市名称在文件中出现多次，您可以使用每个城市名称的出现次数并标记仅出现一次的城市名称。