METHOD FOR PARALLEL COMPUTATION OF EXTENDED EDIT DISTANCE INCLUDING SWAP OPERATION

摘要

PURPOSE: A method for calculating an expansion editing distance including an exchange operation is provided to calculate the expansion editing distance including the exchange operation in parallel, thereby improving time complexity without considering space complexity. CONSTITUTION: A table for storing an expansion editing distance between a character included in a first character string and a character included in a second character string is initialized. An expansion editing distance of a cell located in a diagonal direction on the table is calculated in parallel by using threads assigned to each row or column of the table. An auxiliary data structure for storing a position, which an exchange operation between the first character string and the second character string for the threads is generated, is calculated. The expansion editing distance corresponding to each cell of the table is calculated by using the auxiliary data structure per thread.