Find longest matching block of a and b in a[alo:ahi] and b[blo:bhi]. `b2j` is a mapping of b high token ids -> list of position in b `len_good` is such that token ids smaller than `_good_good` are treated as good, non-junk tokens. `matchables` is a set of matchable positions. P
(a, b, alo, ahi, blo, bhi, b2j, len_good, matchables)
| 17 | |
| 18 | |
| 19 | def find_longest_match(a, b, alo, ahi, blo, bhi, b2j, len_good, matchables): |
| 20 | """ |
| 21 | Find longest matching block of a and b in a[alo:ahi] and b[blo:bhi]. |
| 22 | |
| 23 | `b2j` is a mapping of b high token ids -> list of position in b |
| 24 | `len_good` is such that token ids smaller than `_good_good` are treated as |
| 25 | good, non-junk tokens. `matchables` is a set of matchable positions. |
| 26 | Positions absent from this set are ignored. |
| 27 | |
| 28 | Return (i,j,k) Match tuple where: |
| 29 | "i" in the start in "a" |
| 30 | "j" in the start in "b" |
| 31 | "k" in the size of the match |
| 32 | |
| 33 | and such that a[i:i+k] is equal to b[j:j+k], where |
| 34 | alo <= i <= i+k <= ahi |
| 35 | blo <= j <= j+k <= bhi |
| 36 | |
| 37 | and for all (i',j',k') matchable token positions meeting those conditions, |
| 38 | k >= k' |
| 39 | i <= i' |
| 40 | and if i == i', j <= j' |
| 41 | |
| 42 | In other words, of all maximal matching blocks, return one that starts |
| 43 | earliest in a, and of all those maximal matching blocks that start earliest |
| 44 | in a, return the one that starts earliest in b. |
| 45 | |
| 46 | First the longest matching block (aka contiguous substring) is determined |
| 47 | where no junk element appears in the block. Then that block is extended as |
| 48 | far as possible by matching other tokens including junk on both sides. So |
| 49 | the resulting block never matches on junk. |
| 50 | |
| 51 | If no blocks match, return (alo, blo, 0). |
| 52 | """ |
| 53 | besti, bestj, bestsize = alo, blo, 0 |
| 54 | b2j_get = b2j.get |
| 55 | |
| 56 | # find longest matchable junk-free match |
| 57 | # during an iteration of the loop, j2len[j] = length of longest |
| 58 | # junk-free match ending with a[i-1] and b[j] |
| 59 | j2len = {} |
| 60 | j2lenget = j2len.get |
| 61 | nothing = [] |
| 62 | for i in range(alo, ahi): |
| 63 | newj2len = {} |
| 64 | # we cannot do LCS on junk or non matchable |
| 65 | cura = a[i] |
| 66 | if cura < len_good and i in matchables: |
| 67 | # look at all instances of a[i] in b; note that because |
| 68 | # b2j has no junk token, the loop is skipped if a[i] is junk |
| 69 | for j in b2j_get(cura, nothing): |
| 70 | # a[i] matches b[j] |
| 71 | if j < blo: |
| 72 | continue |
| 73 | if j >= bhi: |
| 74 | break |
| 75 | k = newj2len[j] = j2lenget(j - 1, 0) + 1 |
| 76 | if k > bestsize: |
no test coverage detected