Apparatus and method for aligning token sequences with block permutations
US10318523B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Feb 5, 2015 |
| Grant date | Jun 11, 2019 |
| Priority date | — |
| Expiry date | Jul 26, 2037 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F21/566
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method of determining matching between at least a first sample comprising a sequence of tokens A and a second sample comprising a sequence of tokens B may include, for monotonically decreasing values of n, performing operations including recording a subset SA of n-grams of A in a hash table LA, such that a value of each n-gram determines an index in LA and a location of each respective n-gram in A is recorded as the value in LA, recording a subset SB of n-grams of B in a hash table LB, such that a value of each n-gram determines an index in LB and a location of each respective n-gram in B is recorded as the value in LB, for each location L that is occupied in both LA and LB, examining a region in A centered on LA(L) and a region in B centered on LB(L), and reporting a largest matching region aligning LA(L) with LB(L) that does not include already-matched tokens in A or B and marking the largest matching region as matched.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.