我有一个存储数百或数千个字符串的 SQLite 数据库，我保留了一个我增长的这些字符串的数组，以便我可以更轻松地更快地搜索我的数据库。但是，用户可以使用搜索字符串进行搜索，我将根据与搜索字符串的接近程度对数据库中的字符串进行排名。例如，假设他们搜索“foo”。如果我的数据库中有条目“foo”“foobar”和“foo foo”，是否有人对按顺序排列这些字符串的算法有任何想法:
1. “foo”(完全匹配)
2。 “foo foo”(它包含两次搜索字符串)
3。 “foobar”(它包含一次搜索字符串)
有没有人知道或有任何关于会产生此结果的算法的想法？如果有人希望发布任何代码片段，我同时使用 Java 和 C++，但我实际上只是在寻找算法的想法。
请注意，我希望像 fobar 或 fuo 这样的东西也出现在搜索结果中，因为它距离搜索有 1 个字母，
最佳答案
当您说您希望排名在线性时间内时，我猜您只想分析集合中的每个字符串一次。
一种相对简单的方法是根据您定义的一些规则计算分数。当然，您拥有的规则越多，所需的时间就越长，但只要您实现良好的分析，即使是数千个字符串也不会花费很长时间。
例如，您说完全匹配获得 100 分，而包含搜索字符串 n 次获得 10n 分，将它包含在另一个词中 n 次获得 5n 分，依此类推。如果您以相当分离的方式实现您的规则，您可以调整您的规则几次，看看它们在实际搜索中的表现如何，直到您对搜索的准确性感到满意为止。
一旦你有了一组分数，你就可以使用一些非常快速的排序算法来为你排序你的结果，从最好的分数到最差的。当然，您会排除分数小于 x 的结果。
(顺便说一句，这种技术可以很容易地实现高级搜索功能，例如 AND/OR/NOT，因为您可以拆分搜索词的分析，并结合每个结果的得分)
关于java - 基于线性时间搜索字符串对字符串进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7843050/