我有一个大约15000个条目的数据库，我想为应用程序的开头部分实现搜索算法，但是我不知道应该如何开始。搜索算法应对搜索结果进行排名，并应接受书面错误。例：如果我搜索“ Pordlnd”，结果应该是“ Portland”。
而且它也不应该在乎字符串的长度。例：如果我搜索“新”，则“纽约”和“新罕布什尔州”的排名应相同，因为它们都包含“新”一词。
我想把它写成自己，更多是作为练习，因此，如果您能为我指明正确的方向，将非常感谢您的帮助！
您正在寻找的被称为近似/模糊字符串搜索。这是一个非常广泛的主题，有很多不同的实现，但是我最喜欢的初学者教程之一是：https://norvig.com/spell-correct.html（请注意，这并不完全符合您的要求，但是仍然很不错）。
从根本上讲，您的问题可以归结为：根据某些匹配条件，为词典中的所有单词提供0-1的得分，并根据该得分返回前N个条目。 （当然，由于这需要大量的处理能力，因此您必须在如何计算它方面很聪明）。
以下是有关如何给该分数的介绍：编辑距离/ Levenstein距离为您提供了“最小成本”，可以使用字符的插入/删除/替换来将一个字符串转换为另一个字符串。您可以签出：https://en.wikipedia.org/wiki/Levenshtein_distance或此Youtube教程https://www.youtube.com/watch?v=Xxx0b7djCrs。您可能希望将字符的删除成本设为0，因为您希望纽约/新罕布什尔州在搜索“新”时具有相同的等级。这是一个有关如何在BK树中使用Levenstein距离的youtube视频：https://www.youtube.com/watch?v=oIsPB2pqq_8。
余弦距离是两个向量之间相似度的另一种度量，这是一个很好的解释：https://blog.nishtahir.com/2015/09/19/fuzzy-string-matching-using-cosine-similarity/
经过一番谷歌搜索后，这是一个旧的SO答案：Fastest way to find most similar string to an input?