Оптимизация алгоритма Яро-Винклера

У меня есть этот код для алгоритма Яро-Винклера, взятый с этого сайта. Мне нужно пробежать 150000 раз, чтобы получить расстояние между различиями. Это занимает много времени, так как я работаю на мобильном устройстве 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

Источник

6 ответов

Решение

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

Этот ожидаемый патч Commons-Lang даст вам немного аромата.

Источник

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

Решение этой проблемы состоит в том, чтобы настроить 'm-1' на 'm' во внутреннем операторе for в методе getCommonCharacters. Код тогда работает как шарм:)

См. Также http://en.wikipedia.org/wiki/Jaro%E2%80%93Winkler_distance для некоторых примеров.

Источник

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

Вы можете найти мою реализацию здесь, и она должна быть намного быстрее. Это под лицензией Apache 2.0.

Источник

Вместо возврата общих символов с помощью метода GetCommonCharacters, используйте пару массивов для сохранения совпадений, аналогично версии C здесь https://github.com/miguelvps/c/blob/master/jarowinkler.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;
        }
    }
}

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

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

Источник

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

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

ISolvable.blogspot.com

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

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