搜索数据库的算法
Algorithm for searching the database
我有一个包含大约 15000 个条目的数据库，我想为应用程序的前端部分实现一个搜索算法，但我不知道应该如何开始。
搜索算法应该对搜索结果进行排序，并且应该接受书写错误。
例子：
如果我搜索 "Pordlnd"，结果应该是 "Portland"。
而且它不应该关心字符串长度。
例子：
如果我搜索 "new" "New York" 和 "New Hampshire" 应该具有相同的排名，因为它们都包含单词 "new".
我想自己写，更多的是作为练习，所以如果你能指出正确的方向，你的帮助将不胜感激！
您要找的是 approximate/fuzzy 字符串搜索。这是一个非常庞大的主题，有很多不同的实现，但我最喜欢的初学者教程之一是：https://norvig.com/spell-correct.html（请注意，这并不完全符合您的要求，但仍然是一本不错的读物）。
你的问题的核心归结为：根据一些匹配标准，给你字典中的所有单词打 0 - 1 分，然后 return 根据该分数给前 N 个词条打分. （当然，你必须聪明地计算它，因为这需要大量的处理能力）。
以下是关于如何给出该分数的一些介绍：
编辑 Distance/Levenstein 距离让您 "minimum cost" 使用 insertions/deletions/substitutions 个字符将一个字符串转换为另一个字符串。您可以查看：https://en.wikipedia.org/wiki/Levenshtein_distance or this Youtube tutorial https://www.youtube.com/watch?v=Xxx0b7djCrs . You might want to use deletion cost of a character to be 0, because you want New York/New Hampshire to have the same rank when you search for New. Here's a little youtube video on how to use Levenstein Distance with BK Trees: 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?
我有一个包含大约 15000 个条目的数据库，我想为应用程序的前端部分实现一个搜索算法，但我不知道应该如何开始。 搜索算法应该对搜索结果进行排序，并且应该接受书写错误。 例子： 如果我搜索 "Pordlnd"，结果应该是 "Portland"。
而且它不应该关心字符串长度。 例子： 如果我搜索 "new" "New York" 和 "New Hampshire" 应该具有相同的排名，因为它们都包含单词 "new".
我想自己写，更多的是作为练习，所以如果你能指出正确的方向，你的帮助将不胜感激！
您要找的是 approximate/fuzzy 字符串搜索。这是一个非常庞大的主题，有很多不同的实现，但我最喜欢的初学者教程之一是：https://norvig.com/spell-correct.html（请注意，这并不完全符合您的要求，但仍然是一本不错的读物）。
你的问题的核心归结为：根据一些匹配标准，给你字典中的所有单词打 0 - 1 分，然后 return 根据该分数给前 N 个词条打分. （当然，你必须聪明地计算它，因为这需要大量的处理能力）。
以下是关于如何给出该分数的一些介绍： 编辑 Distance/Levenstein 距离让您 "minimum cost" 使用 insertions/deletions/substitutions 个字符将一个字符串转换为另一个字符串。您可以查看：https://en.wikipedia.org/wiki/Levenshtein_distance or this Youtube tutorial https://www.youtube.com/watch?v=Xxx0b7djCrs . You might want to use deletion cost of a character to be 0, because you want New York/New Hampshire to have the same rank when you search for New. Here's a little youtube video on how to use Levenstein Distance with BK Trees: 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?