[プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記ふと、ビット並列アルゴリズムを使った編集距離を計算するアルゴリズムを書きたくなったので書いてみた。 まず、通常の編集距離であるLevenshtein Distanceを求めるアルゴリズムは以下のように書ける int levenshteinDistance(String A, String B) { int m = A.length(); int n = B.length(); int dp[] = new int[n + 1]; int next[] = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i; for (int i = 1; i <= m; i++) { next[0] = i; for (int j = 1; j <= n; j++) { if (A.charAt(i - 1) == B.charAt(j - 1))
![[プログラミング] ビット並列アルゴリズムを使った編集距離 - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/466673dcf501fbd428f9b1a630d943c8246acf97/height=288;version=1;width=512/https%3A%2F%2Fcdn.image.st-hatena.com%2Fimage%2Fscale%2Fbf0812ca52ab03f4abef108e09e49c6a9ef9fb9e%2Fbackend%3Dimagemagick%3Bheight%3D1200%3Bversion%3D1%3Bwidth%3D1200%2Fhttps%253A%252F%252Fcdn-ak.f.st-hatena.com%252Fimages%252Ffotolife%252Ft%252Ftsubosaka%252F20091103%252F20091103000001.jpg)
