python - 有人可以根据与另一个列表的比较来解释拆分列表元素吗？

Question

假设我有两个包含相同字符串但拆分不同的列表：

sentences = ["This is a sentence", "so is this"]
phrases = ["This is", "a sentence so", "is this"]

我要做的是检查“短语”列表中的任何元素是否由句子中的某个元素完全表示，然后相应地拆分该“短语”元素。例如，在这种情况下：

"a sentence so"

在“短语”中，部分在“句子”中的元素1和元素2中表示，所以应该在“一个句子”和“所以”之间分开，以便创建一个新的元素。
短语中的“this is”和“is this”应该被有效地忽略，因为它们都完全对应于句子中的一个元素。接下来，假设我想做一个元素计数来确定每个列表中有多少个，“句子”的结果仍然应该是2，但“短语”的结果应该是3到4。

Sentencecount=0
Phrasecount=0
for i in sentences:
    Sentencecount+=1
for n in phrases:
#code here should check each element with 'sentences' elements and split    accordingly
    Phrasecount += 1

#expected result: phrases = ["This is", "a sentence", "so", "is this"]

Answer 1

好吧，这更难——更有趣！--比我预料的要多。

from collections import deque

def align_wordlists(words1, words2):
    # Split every element of the word lists
    # >>> [e.split(" ") for e in ["This is", "a sentence"]]
    # [["This", "is"], ["a", "sentence"]]
    words1_split = [e.split(" ") for e in words1]
    words2_split = [e.split(" ") for e in words2]

    # Assert that the flattened lists are identical
    assert [word for split in words1_split for word in split] == \
            [word for split in words2_split for word in split]

    # Create a queue and two tracking lists
    Q = deque(enumerate(words2_split))
    result = []
    splits = []

    # Keep track of the current sublist in words1
    words1_sublist_id = 0
    words1_sublist_offset = 0

    # Keep iterating until the queue is empty
    while Q:
        sublist_id, sublist = Q.popleft()
        sublist_len = len(sublist)

        words1_sublist_len = len(words1_split[words1_sublist_id])
        words1_remaining_len = words1_sublist_len - words1_sublist_offset

        if sublist_len <= words1_remaining_len:
            # The sublist fits entirely into the current segment in words 1,
            # add sublist untouched to resulting list.
            result.append(" ".join(sublist))

            # Update the sublist tracking
            if (words1_sublist_len - words1_sublist_offset - sublist_len) == 0:
                # The sublist filled the remaining space
                words1_sublist_id += 1
                words1_sublist_offset = 0
            else:
                # The sublist only filled part of the remaining space
                words1_sublist_offset += sublist_len

        else:
            # Only part of the current sublist fits.
            # Split the segment at the point where the left
            # part fits into the current segment of words1.
            # Then add the remaining right list to the front
            # of the queue.
            left = " ".join(sublist[:words1_remaining_len])
            right = sublist[words1_remaining_len:]
            result.append(left)
            Q.appendleft((sublist_id, right))

            # Keep track of splits
            splits.append(sublist_id)

            # update indices
            words1_sublist_id += 1
            words1_sublist_offset = 0

    # Combine splits into sublists to get desired result
    for split in splits:
        if isinstance(result[split], str):
            result[split:split+2] = [[result[split], result[split + 1]]]
        else:
            result[split] = result[split] + [result[split + 1]]
            del result[split + 1]

    return result

实例

>>> words1 = ["This is a sentence", "so is this"]
>>> words2 = ["This is", "a sentence so", "is this"]
>>> align_wordlists(words1, words2)
['This is', ['a sentence', 'so'], 'is this']

>>> words1 = ["This is a longer", "sentence with", "different splits"]
>>> words2 = ["This is", "a longer sentence", "with different splits"]
>>> align_wordlists(words1, words2)
['This is', ['a longer', 'sentence'], ['with', 'different splits']]

>>> words1 = ["This is a longer", "sentence with", "different splits"]
>>> words2 = ["This is", "a longer sentence with different splits"]
>>> align_wordlists(words1, words2)
['This is', ['a longer', 'sentence with', 'different splits']]

算法综述
这里使用的算法的高级描述。
你所描述的问题归结为这个问题：
对于第二个单词列表中的每个短语，它属于第一个列表中的哪个句子？
为了回答这个问题，我们在上面的算法中采取了几个步骤：
将 words1和 words2中的词组分成子列表。我们一开始就这样做，因为这样以后处理短语中的单个单词就更容易了。

def align_wordlists(words1, words2):
    # Split every element of the word lists
    # >>> [e.split(" ") for e in ["This is", "a sentence"]]
    # [["This", "is"], ["a", "sentence"]]
    words1_split = [e.split(" ") for e in words1]
    words2_split = [e.split(" ") for e in words2]

为了确保这个算法能起作用，我添加了一个断言，它验证了如果我们忽略每个分裂和空间，这两个句子（即单词列表）是完全相同的：

    # Assert that the flattened lists are identical
    assert [word for split in words1_split for word in split] == \
            [word for split in words2_split for word in split]

为了跟踪需要查看的短语，我们使用 deque，它是python collections库的一部分。

    # Create a queue and two tracking lists
    Q = deque(enumerate(words2_split))
    result = []
    splits = []

我们用第二个单词列表的每个短语来初始化这个队列，并与单词列表中的索引相结合。见 enumerate。
因为我们正在比较第二个单词表中的短语和第一个单词表中的句子，所以我们必须以某种方式跟踪我们在哪里以及我们已经在第一个单词表中查找过的位置。

    # Keep track of the current sublist in words1
    words1_sublist_id = 0
    words1_sublist_offset = 0

由于队列是我们的“工作堆栈”，只要队列中有项，我们就执行以下代码：

    # Keep iterating until the queue is empty
    while Q:

首先要做的是：从队列前面获取项目。在初始化过程中，我解压缩了在步骤3中被推到列表中的元组。 sublist_id是子列表在第二个单词列表中的位置的索引， sublist是单词的实际列表，即短语。此外，我们还计算短语的长度，稍后我们将需要。

        sublist_id, sublist = Q.popleft()
        sublist_len = len(sublist)

现在我们需要检查现在的短语是否符合我们正在看的句子。（在算法开始时， words1_sublist_id为0，所以我们正在看第一个单词列表中的第一个组。

        words1_sublist_len = len(words1_split[words1_sublist_id])
        words1_remaining_len = words1_sublist_len - words1_sublist_offset

它的意思是：“它适合吗？”如果这个短语适合这个句子，这个短语完全可以用这个句子来表示。
如果：短语的长度比剩余句子的长度短，即：我们不必分开！

        if sublist_len <= words1_remaining_len:

因为我们不需要拆分，所以我们可以将短语附加到 result列表中（我在一个空格 join上将短语组合成一个字符串）。

        # The sublist fits entirely into the current segment in words 1,
        # add sublist untouched to resulting list.
        result.append(" ".join(sublist))

因为我们刚刚把这个短语放进句子中，所以我们必须更新跟踪以反映我们所取得的进展。在做这件事的时候，我们必须注意遵守句子的界限。

        # Update the sublist tracking
        if (words1_sublist_len - words1_sublist_offset - sublist_len) == 0:
            # The sublist filled the remaining space
            words1_sublist_id += 1
            words1_sublist_offset = 0
        else:
            # The sublist only filled part of the remaining space
            words1_sublist_offset += sublist_len

else：短语的长度比剩余的句子长，即短语不能用句子来表示。

        else:

在这种情况下，我们必须在短语溢出到下一句时将其拆分。我们根据句子中剩余单词的数量来确定“分割点”（例如，如果这个短语有3个单词长，但这个句子只剩下2个单词，我们将这个短语在2个单词后分割）。

        # Only part of the current sublist fits.
        # Split the segment at the point where the left
        # part fits into the current segment of words1.
        # Then add the remaining right list to the front
        # of the queue.
        left = " ".join(sublist[:words1_remaining_len])
        right = sublist[words1_remaining_len:]

（因为分割的 " "部分是“完成的”，所以我将它转换成一个字符串。 left部分还没有完成，我们仍然关心它被拆分成单个单词。）
拆分短语后，我们可以将 join部分推到 right列表中，因为我们现在知道它在当前句子中完全表示。不过，我们对 left部分一无所知：它可能适合下一个句子，也可能会溢出那个句子（参见示例4）。
因为我们不知道如何处理 result部分，所以我们必须把它当作一个新的短语来对待：也就是说，我们只是把它添加到我们的工作队列的前面，以便在下一次运行时进行处理。

        result.append(left)
        Q.appendleft((sublist_id, right))

我们的 right列表将不包括我们拆分的点，因此我们会跟踪拆分点。

        # Keep track of splits
        splits.append(sublist_id)

同样，我们必须在 right-列表中跟踪我们当前的位置。因为我们知道我们已经溢出了当前语句，所以我们可以简单地增加索引并重置偏移量。

        # update indices
        words1_sublist_id += 1
        words1_sublist_offset = 0

在工作队列为空的情况下，我们可以获取已拆分短语的子列表。这有点棘手：

    # Combine splits into sublists to get desired result
    for split in splits:

如果我们看到的分裂点是一个字符串，我们可以推断出我们在这个位置还没有分裂。因此，我们可以用包含两个单词的列表替换分割点上的项和之后的项。（我们使用的是 result而不是 words1，因为范围不包括在内。）

    if isinstance(result[split], str):
        result[split:split+2] = [[result[split], result[split + 1]]]

然而，如果拆分点是一个列表，我们知道我们已经在一个点上进行了拆分（即一个短语至少溢出一个句子两次，请参见示例4）。
在本例中，我们将项目追加到列表之后， split+2追加到列表中，并使用 split+1删除现在追加的项目。

    else:
        result[split] = result[split] + [result[split + 1]]
        del result[split + 1]

一言一行，皆可报答！

    return result