Function match_blocks

src/licensedcode/seq.py:107–176

Return a list of matching block Match triples describing matching subsequences of `a` in `b` starting from the `a_start` position in `a` up to the `a_end` position in `a`. `b2j` is a mapping of b "high" token ids -> list of positions in b, e.g. a posting list. `len_good` i

(a, b, a_start, a_end, b2j, len_good, matchables=frozenset(), *args, **kwargs)

def match_blocks(a, b, a_start, a_end, b2j, len_good, matchables=frozenset(), *args, **kwargs):
    """
    Return a list of matching block Match triples describing matching
    subsequences of `a` in `b` starting from the `a_start` position in `a` up to
    the `a_end` position in `a`.

    `b2j` is a mapping of b "high" token ids -> list of positions in b, e.g. a
    posting list.

    `len_good` is such that token ids smaller than `len_good` are treated as
    important, non-junk tokens.

    `matchables` is a set of matchable positions. Positions absent from this set
    are ignored.

    Each triple is of the form (i, j, n), and means that a[i:i+n] == b[j:j+n].
    The triples are monotonically increasing in i and in j.  It is also
    guaranteed that adjacent triples never describe adjacent equal blocks.
    Instead adjacent blocks are merged and collapsed in a single block.
    """

    # This non-recursive algorithm is using a list as a queue of blocks. We
    # still need to look at and append partial results to matching_blocks in a
    # loop. The matches are sorted at the end.

    queue = [(a_start, a_end, 0, len(b))]
    queue_append = queue.append
    queue_pop = queue.pop
    matching_blocks = []
    matching_blocks_append = matching_blocks.append
    while queue:
        alo, ahi, blo, bhi = queue_pop()
        i, j, k = x = find_longest_match(
            a, b, alo, ahi, blo, bhi, b2j, len_good, matchables)
        # a[alo:i] vs b[blo:j] unknown
        # a[i:i+k] same as b[j:j+k]
        # a[i+k:ahi] vs b[j+k:bhi] unknown
        if k:  # if k is 0, there was no matching block as the size is 0
            matching_blocks_append(x)
            if alo < i and blo < j:
                # there is unprocessed things remaining to the left
                queue_append((alo, i, blo, j))
            if i + k < ahi and j + k < bhi:
                # there is unprocessed things remaining to the right
                queue_append((i + k, ahi, j + k, bhi))

    matching_blocks.sort()

    # collapse adjacent blocks
    i1 = j1 = k1 = 0
    non_adjacent = []
    non_adjacent_append = non_adjacent.append
    for i2, j2, k2 in matching_blocks:
        # Is this block adjacent to i1, j1, k1?
        if i1 + k1 == i2 and j1 + k1 == j2:
            # Yes, so collapse them -- this just increases the length of the
            # first block by the length of the second, and the first block so
            # lengthened remains the block to compare against.