公开(公告)号：KR101322123B1

公开(公告)日：2013-10-28

申请号：KR1020130068361

申请日：2013-06-14

Applicant: 인하대학교 산학협력단

Inventor： 심정섭 ,  강대웅 ,  김영호

IPC: G06F17/00 ,  G06F17/10

CPC classification number: G06F17/16

Abstract: 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.

Abstract translation: 目的：提供一种用于计算包括交换操作的扩展编辑距离的方法，以并行计算包括交换操作的扩展编辑距离，从而在不考虑空间复杂性的情况下提高时间复杂度。 构成：用于存储包括在第一字符串中的字符与包括在第二字符串中的字符之间的扩展编辑距离的表被初始化。 通过使用分配给表的每一行或列的线程来并行计算位于表上的对角线方向上的单元的扩展编辑距离。 计算用于存储产生用于线程的第一字符串和第二字符串之间的交换操作的位置的辅助数据结构。 通过使用每个线程的辅助数据结构来计算对应于表的每个单元的扩展编辑距离。