ADAPTIVE-WINDOW EDIT DISTANCE ALGORITHM COMPUTATION

摘要

The present invention relates to an apparatus and method for performing computation using adaptive-window edit distance algorithm to determine matching possibilities by optimizing ratio of similarity values and weighted order of string, wherein the computation on string performed using parallel forward and backward computation on each sub-string to determine sequential order. The apparatus for parallel moving adaptive window filtering edit distance computation includes: a central processing unit (1), a storage unit (2), a memory module (6), a plurality of input devices (4), a random access memory (7) having connected to the memory module (6), an Input-Output hub (3) having connected to the memory module (6), the input devices (4) and the storage unit (2), and a parallel computation acceleration device (5) having connected to the central processing unit (1) via memory module (6), whereby the parallel computation acceleration device (5) further includes: a match filtering scoping unit to extract a first string from at least one reference list that is most similar to a second string from at least one search list for matching operation, a eliminator unit to extract at least one unmatched string from the first string and second string, a comparator unit to compute the unmatched string, wherein the unmatched string are split to at least one sub-string using a space character and eliminate at least one patronymic character, and at least one edit distance adaptive window determining unit to prepare for adaptive window setting based on the unmatched string and to calculate adaptive distance values on at least one critical path.