Оптимизация алгоритма aro-winkler

Question

У меня есть этот код для алгоритма Яро-Винклера, взятый из это Веб-сайт. Мне нужно пробежать 150 000 раз, чтобы получить расстояние между различиями. Это занимает много времени, так как я бегу на мобильном устройстве Android.

Можно ли оптимизировать больше?

public class Jaro {
    /**
     * gets the similarity of the two strings using Jaro distance.
     *
     * @param string1 the first input string
     * @param string2 the second input string
     * @return a value between 0-1 of the similarity
     */
    public float getSimilarity(final String string1, final String string2) {

        //get half the length of the string rounded up - (this is the distance used for acceptable transpositions)
        final int halflen = ((Math.min(string1.length(), string2.length())) / 2) + ((Math.min(string1.length(), string2.length())) % 2);

        //get common characters
        final StringBuffer common1 = getCommonCharacters(string1, string2, halflen);
        final StringBuffer common2 = getCommonCharacters(string2, string1, halflen);

        //check for zero in common
        if (common1.length() == 0 || common2.length() == 0) {
            return 0.0f;
        }

        //check for same length common strings returning 0.0f is not the same
        if (common1.length() != common2.length()) {
            return 0.0f;
        }

        //get the number of transpositions
        int transpositions = 0;
        int n=common1.length();
        for (int i = 0; i < n; i++) {
            if (common1.charAt(i) != common2.charAt(i))
                transpositions++;
        }
        transpositions /= 2.0f;

        //calculate jaro metric
        return (common1.length() / ((float) string1.length()) +
                common2.length() / ((float) string2.length()) +
                (common1.length() - transpositions) / ((float) common1.length())) / 3.0f;
    }

    /**
     * returns a string buffer of characters from string1 within string2 if they are of a given
     * distance seperation from the position in string1.
     *
     * @param string1
     * @param string2
     * @param distanceSep
     * @return a string buffer of characters from string1 within string2 if they are of a given
     *         distance seperation from the position in string1
     */
    private static StringBuffer getCommonCharacters(final String string1, final String string2, final int distanceSep) {
        //create a return buffer of characters
        final StringBuffer returnCommons = new StringBuffer();
        //create a copy of string2 for processing
        final StringBuffer copy = new StringBuffer(string2);
        //iterate over string1
        int n=string1.length();
        int m=string2.length();
        for (int i = 0; i < n; i++) {
            final char ch = string1.charAt(i);
            //set boolean for quick loop exit if found
            boolean foundIt = false;
            //compare char with range of characters to either side

            for (int j = Math.max(0, i - distanceSep); !foundIt && j < Math.min(i + distanceSep, m - 1); j++) {
                //check if found
                if (copy.charAt(j) == ch) {
                    foundIt = true;
                    //append character found
                    returnCommons.append(ch);
                    //alter copied string2 for processing
                    copy.setCharAt(j, (char)0);
                }
            }
        }
        return returnCommons;
    }
}

Я упоминаю, что во всем процессе я делаю только экземпляр сценария, поэтому только один раз

jaro= new Jaro();

Если вы собираетесь тестировать и нуждаетесь в примерах, поэтому не сломайте скрипт, вы найдете его здесь, в другой поток для оптимизации Python

Answer 1

Да, но вы не собираетесь наслаждаться этим. Заменить все те newEd StringBuffers с массивами CHAR, которые выделяются в конструкторе и никогда больше, используя целочисленные индексы, чтобы отслеживать то, что в них.

Это ожидается патч-ланг даст вам немного вкуса.

Answer 2

Я знаю, что этот вопрос, вероятно, был решен в течение некоторого времени, но я хотел бы прокомментировать саму алгоритм. При сравнении строки против самого себя ответ получается 1 / | String | выключенный. При сравнении слегка разных значений значения также оказываются ниже.

Решением для этого состоит в том, чтобы настроить «M-1» на «M» во внутреннем выписке в методе GetCommonChathoracher. Затем код работает как шарм :)

Видеть http://en.wikipedia.org/wiki/jaro%e2%80%93winkler_distance. Также для некоторых примеров.

Answer 3

1. Старайтесь избегать двух вложенных петель в петле GetCommonachatchatchatcher.
   Предложение относительно того, как: Хранить все символы в меньшей строке на карте какой-то сортировки (у Java есть несколько), где ключ - это символ, а значение - это положение, то, как вы все еще можете рассчитать расстояние, общими. Я не совсем понимаю алгоритм, но я думаю, что это выполнимо.
2. За исключением того, что ответа о том и BMARGulies я действительно не вижу дальнейших оптимизаций, кроме вещей, таких как биты и т. Д. Если это действительно важно, рассмотрим переписывание этой части в C?

Answer 4

Я не знаю много о Android и как он работает с базами данных. WP7 имеет (будет иметь :)) SQL CE. Следующий шаг, как правило, будет работать с вашими данными. Добавьте длину строки и ограничите ваши сравнения. Добавьте индексы на обоих столбцах и сортируйте по длине, а затем по значению. Индекс по длине также должен быть отсортирован. Я провел его на старом сервере с 150 000 медицинских терминов, дающих мне предложения и проверку орфографии в течение 0,5 секунды, пользователи едва могли бы еще заметить его, особенно если он работает на отдельной резьбе.

Я имел в виду блог об этом долгое время (например, 2 года :)) потому что есть необходимость. Но я наконец-то удастся писать несколько слов об этом и предоставлять несколько советов. Пожалуйста, проверьте это здесь:

Isolvable.blogspot.com.

Хотя это для Microsoft Platform, все еще общие принципы одинаковы.

Answer 5

Да, это можно сделать намного быстрее. Для одной вещи вам не нужны StringBuffers вообще. Для другого вам не нужен отдельный цикл для подсчета транспозиций.

Ты можешь найти Моя реализация здесь, И это должно быть намного быстрее. Это при лицензии Apache 2.0.

Answer 6

Вместо этого возвращают общие символы с использованием метода GetCommonCharacher, используйте пару массивов, чтобы сохранить матчи, аналогично версии C здесь https://github.com/miguelvps/c/blob/master/jarovinkler.c.

/*Calculate matching characters*/
for (i = 0; i < al; i++) {
    for (j = max(i - range, 0), l = min(i + range + 1, sl); j < l; j++) {
        if (a[i] == s[j] && !sflags[j]) {
            sflags[j] = 1;
            aflags[i] = 1;
            m++;
            break;
        }
    }
}

Другая оптимизация - предварительно рассчитать растровую маску для каждой строки. Используя это, проверьте, присутствует ли текущий символ на первой строке на втором. Это можно сделать с использованием эффективных побитовых операций.

Это будет пропустить вычисление максимального / мин и зацикливаться для отсутствующих символов.