如何加快Levenshtein距离的计算

本文介绍了如何加快Levenshtein距离的计算的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在尝试进行仿真以测试随机之间平均 Levenshtein距离 二进制字符串.

I am trying to run a simulation to test the average Levenshtein distance between random binary strings.

我的程序在python中，但是我正在使用 C扩展.与此相关且花费大量时间的函数是计算两个字符串之间的Levenshtein距离的方法.

My program is in python but I am using this C extension. The function that is relevant and takes most of the time computes the Levenshtein distance between two strings and is this.

lev_edit_distance(size_t len1, const lev_byte *string1, size_t len2, const lev_byte *string2, int xcost) { size_t i; size_t *row; /* we only need to keep one row of costs */ size_t *end; size_t half; /* strip common prefix */ while (len1 > 0 && len2 > 0 && *string1 == *string2) { len1--; len2--; string1++; string2++; } /* strip common suffix */ while (len1 > 0 && len2 > 0 && string1[len1-1] == string2[len2-1]) { len1--; len2--; } /* catch trivial cases */ if (len1 == 0) return len2; if (len2 == 0) return len1; /* make the inner cycle (i.e. string2) the longer one */ if (len1 > len2) { size_t nx = len1; const lev_byte *sx = string1; len1 = len2; len2 = nx; string1 = string2; string2 = sx; } /* check len1 == 1 separately */ if (len1 == 1) { if (xcost) return len2 + 1 - 2*(memchr(string2, *string1, len2) != NULL); else return len2 - (memchr(string2, *string1, len2) != NULL); } len1++; len2++; half = len1 >> 1; /* initalize first row */ row = (size_t*)malloc(len2*sizeof(size_t)); if (!row) return (size_t)(-1); end = row + len2 - 1; for (i = 0; i < len2 - (xcost ? 0 : half); i++) row[i] = i; /* go through the matrix and compute the costs. yes, this is an extremely * obfuscated version, but also extremely memory-conservative and relatively * fast. */ if (xcost) { for (i = 1; i < len1; i++) { size_t *p = row + 1; const lev_byte char1 = string1[i - 1]; const lev_byte *char2p = string2; size_t D = i; size_t x = i; while (p <= end) { if (char1 == *(char2p++)) x = --D; else x++; D = *p; D++; if (x > D) x = D; *(p++) = x; } } } else { /* in this case we don't have to scan two corner triangles (of size len1/2) * in the matrix because no best path can go throught them. note this * breaks when len1 == len2 == 2 so the memchr() special case above is * necessary */ row[0] = len1 - half - 1; for (i = 1; i < len1; i++) { size_t *p; const lev_byte char1 = string1[i - 1]; const lev_byte *char2p; size_t D, x; /* skip the upper triangle */ if (i >= len1 - half) { size_t offset = i - (len1 - half); size_t c3; char2p = string2 + offset; p = row + offset; c3 = *(p++) + (char1 != *(char2p++)); x = *p; x++; D = x; if (x > c3) x = c3; *(p++) = x; } else { p = row + 1; char2p = string2; D = x = i; } /* skip the lower triangle */ if (i <= half + 1) end = row + len2 + i - half - 2; /* main */ while (p <= end) { size_t c3 = --D + (char1 != *(char2p++)); x++; if (x > c3) x = c3; D = *p; D++; if (x > D) x = D; *(p++) = x; } /* lower triangle sentinel */ if (i <= half) { size_t c3 = --D + (char1 != *char2p); x++; if (x > c3) x = c3; *p = x; } } } i = *end; free(row); return i; }

可以加快速度吗?

我将在AMD FX(tm)-8350八核处理器上的32位ubuntu中运行代码.

I will be running the code in 32 bit ubuntu on an AMD FX(tm)-8350 Eight-Core Processor.

这是调用它的python代码.

Here is the python code that calls it.

from Levenshtein import distance import random for i in xrange(16): sum = 0 for j in xrange(1000): str1 = bin(random.getrandbits(2**i))[2:].zfill(2**i) str2 = bin(random.getrandbits(2**i))[2:].zfill(2**i) sum += distance(str1,str2) print i,sum/(1000*2**i)

推荐答案

也许可以并行运行.在开始时生成一个庞大的随机变量列表，然后在循环中，一次生成线程(8个线程)以每个线程处理列表中的一个块并将其最终结果添加到sum变量中.或一次生成8个列表，然后一次生成8个.

You could run this parallel maybe. Generate one giant list of randoms at the start, then in your loop, spawn threads (8 threads) at a time to each process one chunk of the list and add its final result to the sum variable. Or generate a list of 8 at once and do 8 at a time.

openmp建议的问题是由于大量数据依赖关系，该算法并行性很差"-Wikipedia

The problem with the openmp suggestion is "This algorithm parallelizes poorly, due to a large number of data dependencies" - Wikipedia

from threading import Thread sum = 0 def calc_distance(offset) : sum += distance(randoms[offset][0], randoms[offset][1]) #use whatever addressing scheme is best threads = [] for i in xrange(8) : t = new Thread(target=calc_distance, args=(i)) t.start() threads.append(t)

稍后....

for t in threads : t.join()

我认为，如果有levenshtein距离内核可用(或可编码)，此方法也将在以后很好地移植到opencl.

i think this method would port nicely to opencl later as well if levenshtein distance kernel was available (or codable).

这只是记忆中的一则快速帖子，因此可能有一些问题需要解决.

This is just a quick post from memory so there are probably some kinks to work out.