将字符串列表的序列一致为多序列对齐？

Question

我正在开发一个程序，其目标是制作一个“流畅”的播放列表。为此，我从 Spotify 获取每首歌曲所属流派的列表。我假设这个列表的顺序启发式地从“更大”的类型到“更小的”类型。实际上，我的数据结构是一个字符串列表

[["rock", "American rock", "synth rock"], ["rock", "French rock", "synth rock"], ["pop", "rock", "alt rock"]]

。

现在，为了弄清楚如何排序我的播放列表，我需要所有类型的“共识序列”。因为我有计算生物学背景，所以我的第一个想法是尝试将这些列表对齐在一起并从该对齐中获得共识。

你知道有哪些软件包可以在 python 中的字符串集而不是 DNA/RNA/蛋白质字母表上实现这种算法吗？

谢谢你。

Answer 1

听起来是一个有趣的项目！我没有比较生物背景，所以我无法谈论这些对齐算法的使用，但从自然语言处理的角度来看，这似乎类似于Bag-of-Words设置，只是目标是查看两个袋子的对齐/重叠/相似性，而不是将这些袋子转换成可以输入机器学习模型的东西。因此，您可以按如下方式计算两首歌曲的相似度：

def similarity(
    genres_1: list[str], genres_2: list[str], type: str = "genre_set"
) -> float:
    """
    Compute the similarity between two lists of genres.

    Parameters
    ----------
    genres_1 : list[str]
        A list of genres.
    genres_2 : list[str]
        A list of genres.

    Returns
    -------
    float
        A value between 0 and 1 (inclusive) representing the similarity between the two lists of genres.
    """
    match type:
        case "genre_set":
            genre_set_1, genre_set_2 = set(genres_1), set(genres_2)
            intersection = len(genre_set_1 & genre_set_2)
            union = len(genre_set_1 | genre_set_2)
        case "word_set":
            word_set_1, word_set_2 = set(" ".join(genres_1).split()), set(
                " ".join(genres_2).split()
            )
            intersection = len(word_set_1 & word_set_2)
            union = len(word_set_1 | word_set_2)

    return intersection / union

在这里，

type="genre_set"

表示您只关心两首歌曲是否与给定流派的名称完全重叠，而

type="word_set"

表示流派为“Classic Funk Rock”和“Classic Psychedelic Rock”的两首歌曲将获得一些相似点尽管整个流派并不匹配，但“经典”和“摇滚”有共同点。

如果你想对此更加感兴趣，你可以考虑使用TF-IDF矢量化，它根据不同单词出现的频率来权衡重叠的重要性（因此两首歌曲有一个罕见的流派单词共同点）会比具有共同流派词的词更相似）。乍一看，这个教程似乎很有用。