Compute Levenshtein distance with aparapi

Question

I'm looking at the possibility of implementing a Levenshtein distance algorithm using APARAPI, but I'm running into some problems with the limitations posed - specifically that I need to create an array in the kernel which is prohibited.

Is there a way around this, or better has anyone got a method for Levenshtein distance that works with APARAPI?

The attached code is just in place to try to sort the APARAPI stuff out, I know that I'm not doing anything with the result and I'm just executing once at the moment.

   Kernel kernel = new Kernel() {


        @Override
        public void run() {
            ld("hello", "heya");
        }

        public int ld(String s, String t) {
            int d[]; // matrix
            int n; // length of s
            int m; // length of t
            int i; // iterates through s
            int j; // iterates through t
            int s_i; // ith character of s
            int t_j; // jth character of t
            int cost; // cost

            // Step 1

            n = s.length();
            m = t.length();
            if (n == 0) {
                return m;
            }
            if (m == 0) {
                return n;
            }
            int firstSize = n+1;
            d = new int[firstSize*(m + 1)]; //THIS ISN'T ALLOWED

            // Step 2

            for (i = 0; i <= n; i++) {
                d[firstSize*i+0] = i;
            }

            for (j = 0; j <= m; j++) {
                d[firstSize*0+j] = j;
            }

            // Step 3

            for (i = 1; i <= n; i++) {

                s_i = s.charAt(i - 1);

                // Step 4

                for (j = 1; j <= m; j++) {

                    t_j = t.charAt(j - 1);

                    // Step 5

                    if (s_i == t_j) {
                        cost = 0;
                    } else {
                        cost = 1;
                    }

                    // Step 6
                    int a = d[firstSize*(i - 1)+j] + 1;
                    int b = d[firstSize*i+(j - 1)] + 1;
                    int c = d[firstSize*(i - 1)+(j - 1)] + cost;

                    int mi;

                    mi = a;
                    if (b < mi) {
                        mi = b;
                    }
                    if (c < mi) {
                        mi = c;
                    }

                    d[firstSize*i+j] = mi;

                }
            }

            return d[firstSize*n+m];

        }
    };
    kernel.execute(1);

Answer 1

As you indicate Aparapi does not allow any form of new in the Kernel body, however you could pre-allocate a buffer of ints which the Kernel code can access.

Furthermore because you can determine the group size at runtime your buffer does not have to be huge, but some reasonable proportion/ratio of Kernel.getGroupSize().

Of course you will need to convert the arguments from String to char[] to satisfy Aparapi's Object restriction (Strings are not allowed), but I think from a similar thread on aparapi discussion lists you had already found a workaround for that.

If you are prepared to experiment with some 'experimental code' I have a branch in SVN tagged SupportLocalMemory which will allow you to place your temporary int[] buffer in local memory which should also be more performant.

Gary