Return list of triples describing matching subsequences. 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. New in Python 2.5, it's also guaranteed that if (i, j, n) and (i', j', n') ar
(self)
| 419 | return Match(besti, bestj, bestsize) |
| 420 | |
| 421 | def get_matching_blocks(self): |
| 422 | """Return list of triples describing matching subsequences. |
| 423 | |
| 424 | Each triple is of the form (i, j, n), and means that |
| 425 | a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in |
| 426 | i and in j. New in Python 2.5, it's also guaranteed that if |
| 427 | (i, j, n) and (i', j', n') are adjacent triples in the list, and |
| 428 | the second is not the last triple in the list, then i+n != i' or |
| 429 | j+n != j'. IOW, adjacent triples never describe adjacent equal |
| 430 | blocks. |
| 431 | |
| 432 | The last triple is a dummy, (len(a), len(b), 0), and is the only |
| 433 | triple with n==0. |
| 434 | |
| 435 | >>> s = SequenceMatcher(None, "abxcd", "abcd") |
| 436 | >>> list(s.get_matching_blocks()) |
| 437 | [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)] |
| 438 | """ |
| 439 | |
| 440 | if self.matching_blocks is not None: |
| 441 | return self.matching_blocks |
| 442 | la, lb = len(self.a), len(self.b) |
| 443 | |
| 444 | # This is most naturally expressed as a recursive algorithm, but |
| 445 | # at least one user bumped into extreme use cases that exceeded |
| 446 | # the recursion limit on their box. So, now we maintain a list |
| 447 | # ('queue`) of blocks we still need to look at, and append partial |
| 448 | # results to `matching_blocks` in a loop; the matches are sorted |
| 449 | # at the end. |
| 450 | queue = [(0, la, 0, lb)] |
| 451 | matching_blocks = [] |
| 452 | while queue: |
| 453 | alo, ahi, blo, bhi = queue.pop() |
| 454 | i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi) |
| 455 | # a[alo:i] vs b[blo:j] unknown |
| 456 | # a[i:i+k] same as b[j:j+k] |
| 457 | # a[i+k:ahi] vs b[j+k:bhi] unknown |
| 458 | if k: # if k is 0, there was no matching block |
| 459 | matching_blocks.append(x) |
| 460 | if alo < i and blo < j: |
| 461 | queue.append((alo, i, blo, j)) |
| 462 | if i+k < ahi and j+k < bhi: |
| 463 | queue.append((i+k, ahi, j+k, bhi)) |
| 464 | matching_blocks.sort() |
| 465 | |
| 466 | # It's possible that we have adjacent equal blocks in the |
| 467 | # matching_blocks list now. Starting with 2.5, this code was added |
| 468 | # to collapse them. |
| 469 | i1 = j1 = k1 = 0 |
| 470 | non_adjacent = [] |
| 471 | for i2, j2, k2 in matching_blocks: |
| 472 | # Is this block adjacent to i1, j1, k1? |
| 473 | if i1 + k1 == i2 and j1 + k1 == j2: |
| 474 | # Yes, so collapse them -- this just increases the length of |
| 475 | # the first block by the length of the second, and the first |
| 476 | # block so lengthened remains the block to compare against. |
| 477 | k1 += k2 |
| 478 | else: |