AN APPARATUS AND METHOD FOR PARALLEL MOVING ADAPTIVE WINDOW FILTERING EDIT DISTANCE COMPUTATION

摘要

The present invention relates to an apparatus (200) and method (500) for parallel moving adaptive window filtering edit distance computation that utilizes an adaptive window filtering mechanism to accelerate edit distance computation for increased efficiency and shorter times by searching along a critical path that provides a high rate for string similarity matching. The apparatus (200) of the present invention comprising at least one central processing unit (202); at least one storage unit (210); at least one memory module (204, 206); at least one 1/0 hub (212); a plurality of input devices (214); and at least one parallel computation acceleration device (208). The at least one parallel computation acceleration device (208) further comprising at least one match filtering scoping unit (302) which scopes a region of interest of a reference list that is most similar to a search string for matching operation; at least one edit distance adaptive window determining unit (304) to prepare for window setting based on user input and to calculate distance values on critical path. String filtering is performed automatically, wherein strings are sorted based on character offset to ensure all possibilities of matching are covered. Further, a feedback mechanism is provided for the automatic threshold based filtering to initialize the adaptive window setting based on user input to prepare for the threshold-based filtering and to calculate the distance values on the critical path; and to obtain the final distance value to determine whether the comparison is the intended match or not.