我的情况是：我有从名字到事物的无序映射。
客户可以输入名称（例如fooo），这些名称将被搜索（使用find()），但找不到键将显示“找不到”。
我想为客户提供更好的输出：“找不到fooo。您是说foo吗？”
我认为除非实现一个反映密钥集合的特里树，然后在其上应用“查找最小的莱文斯坦距离”算法，否则这是不可能的。我算错了还是算错了？
几乎是[[几乎可以肯定]]在这里不值得花哨。实现迭代所有可能键的蛮力解决方案，计算距离，然后采用最小值。对它进行分析，您可能会发现它足够快。但是如果您想玩得开心...
字符串编辑距离遵循三角形不等式，这意味着可以采用任意距离函数的任何几何近似邻居数据结构在这里都适用。我喜欢LSH。
但是随着尺寸的增加，ANN变得更糟，尺寸大约是字符串的长度。因此，您可能需要一种不太严格的方法。 BLAST（基因组搜索）执行基于子字符串的精确查找。您的琴弦较短，因此您可能需要二元组或三元组。另外，您可能会认为
length
接近正确，并只需检查所有与之接近的匹配项即可。如果可以访问大型错别字数据库，则可以尝试训练卷积神经网络（对每个字符进行一次热编码），以将字符串映射到具有成本函数的低维特征向量，从而使错别字接近其预期字串。然后将合法字符串的特征向量保留在KD树中。但是所有这些都是为了好玩。如果代码很重要，请保持简单。