Python:如何根据子字符串相关性对字符串列表进行排序？

Question

我有一些字符串列表，例如：

["foo bar SOME baz TEXT bob",
"SOME foo bar baz bob TEXT",
"SOME foo TEXT",
"foo bar SOME TEXT baz",     
"SOME TEXT"]

我希望它按照SOME TEXT子字符串的精确性进行排序(大写并不重要)。类似这样的命令：

["SOME TEXT",
"foo bar SOME TEXT baz",
"SOME foo TEXT",
"foo bar SOME baz TEXT bob",
"SOME foo bar baz bob TEXT"]

这个想法是-最好的分数得到字符串与子字符串单词位置的最佳匹配。对于更大数量的“草率”词，子字符串的单词之间的排序越低。

我已经找到了一些库，如模糊集或Levenshtein距离，但我不确定这是否是我所需要的。我知道准确的子串，根据我想要的排序和那些李子搜索相似的词，正如我所理解的。

实际上，我需要在Django项目中的一些数据库查询(Postgresql)之后进行这种排序。我已经尝试过使用ORM进行全文搜索，但是没有得到相关的排序顺序(它不计算子字符串单词之间的距离)。接下来，我尝试了Haystack+Whoosh，但同时也没有找到信息，如何在那里这样做。因此，现在的想法是获取查询集，下一次将其从数据库中排序(是的，我知道这可能是一个错误的决定，但现在我希望它能工作)。但是，如果有人告诉我如何在任何一种技术中做到这一点，我在这里已经提到了--这也是超级酷的。谢谢!

附注：子串的长度应在最多20个字串中为2-10个字。

Answer 1

您可以使用SequenceMatcher实现与所需输出非常类似的功能：

>>> import difflib
>>> l = ["foo bar SOME baz TEXT bob", "SOME foo bar baz bob TEXT", "SOME foo TEXT", "foo bar SOME TEXT baz", "SOME TEXT"]
>>> sorted(l, key=lambda z: difflib.SequenceMatcher(None, z, "SOME TEXT").ratio(), reverse=True)
['SOME TEXT', 'SOME foo TEXT', 'foo bar SOME TEXT baz', 'foo bar SOME baz TEXT bob', 'SOME foo bar baz bob TEXT']

如果您不知道唯一的区别是，与所需的输出相比，"foo bar SOME TEXT baz"和"SOME foo TEXT"这两个元素的位置是交换的。

Answer 2

看看你的友好邻里排序教程。你需要一种带钥匙的。这里有一个简单的函数来给出这个想法；它可以找到两个单词之间的距离，并将其作为差异度量返回。

sentence = ["foo bar SOME baz TEXT bob",
            "SOME foo bar baz bob TEXT",
            "SOME foo TEXT",
            "foo bar SOME TEXT baz",
            "SOME TEXT"]

def match_score(sentence):
    some_pos = sentence.find("SOME")
    text_pos = sentence.find("TEXT")
    return abs(text_pos - some_pos)

sentence.sort(key = lambda x: match_score(x))

for item in sentence:
    print(item)

输出：

foo bar SOME TEXT baz
SOME TEXT
foo bar SOME baz TEXT bob
SOME foo TEXT
SOME foo bar baz bob TEXT

Answer 3

这是我对它的看法。

l = ["foo bar SOME baz TEXT bob",
"SOME foo bar baz bob TEXT",
"SOME foo TEXT",
"foo bar SOME TEXT baz",     
"SOME TEXT"]

l.sort(key=lambda x: (x.find("SOME")-x.find("TEXT"))*0.9-0.1*x.find("SOME"), reverse=True)

print(l)

产出：

['SOME TEXT', 'foo bar SOME TEXT baz', 'SOME foo TEXT', 'foo bar SOME baz TEXT bob', 'SOME foo bar baz bob TEXT']

因此，我们所做的是根据“一些”和“文本”之间的距离的主要权重对列表进行排序，而对字符串中的“一些”的出现有一些次要的权重。

另一种更长的方法是首先根据列表与文本之间的距离对列表进行分组。然后根据“一些”的位置对每一组进行排序。