تحسين خوارزمية Jaro-Winkler

Question

لدي هذا الرمز لخوارزمية Jaro-Winkler مأخوذة من هذه موقع الكتروني. أحتاج إلى تشغيل 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();

إذا كنت ستختبر وتحتاج إلى أمثلة حتى لا تكسر البرنامج النصي ، فستجده هنا, ، في موضوع آخر لتحسين بيثون

Answer 1

نعم ، لكنك لن تستمتع به. استبدل كل هؤلاء newEd StringBuffers مع صفائف Char التي يتم تخصيصها في المنشئ وليس مرة أخرى ، باستخدام مؤشرات عدد صحيح لتتبع ما هو فيها.

هذا التصحيح المعلق مع المشاع سوف يعطيك بعض النكهة.

Answer 2

أعلم أن هذا السؤال ربما تم حله لبعض الوقت ، لكنني أود التعليق على الخوارزمية نفسها. عند مقارنة سلسلة على نفسها ، تبين أن الإجابة 1/| سلسلة | إيقاف. عند مقارنة القيم المختلفة قليلاً ، تتحول القيم أيضًا إلى انخفاض.

الحل لهذا هو ضبط "M-1" إلى "M" في المنصة الداخلية داخل طريقة getCommoncharacters. ثم يعمل الرمز مثل السحر :)

يرى http://en.wikipedia.org/wiki/jaro٪E2٪80٪93Winkler_Distance كذلك لبعض الأمثلة.

Answer 3

1. حاول تجنب الحلقتين المتداخلتين في حلقة GetCommoncharacters.
   اقتراح لكيفية: تخزين جميع chars في السلسلة الأصغر في خريطة من نوع ما (Java لديها عدد قليل) ، حيث المفتاح هو الحرف والقيمة هي الموضع ، وبهذه الطريقة لا يزال بإمكانك حساب المسافة ، في حالة ما هي المشتركة. أنا لا أفهم تمامًا الخوارزمية ، لكنني أعتقد أن هذا أمر قابل للتنفيذ.
2. باستثناء إجابة bmargulies ، لا أرى حقًا مزيد من التحسينات التي تتجاوز أشياء مثل البتات وما إلى ذلك. إذا كان هذا أمرًا بالغ الأهمية ، ففكر في إعادة كتابة هذا الجزء في C؟

Answer 4

لا أعرف الكثير عن Android وكيف يعمل مع قواعد البيانات. WP7 لديه (سيكون :)) sql ce. عادة ما تكون الخطوة التالية هي العمل مع بياناتك. أضف أطوال السلسلة وحد من مقارناتك. أضف فهارس على كلا العمودين وفرزها حسب الطول ثم بالقيمة. يجب فرز الفهرس على الطول كذلك. لقد تم تشغيله على خادم قديم به 150 000 مصطلح طبي يمنحني اقتراحات وفحص إملائي في أقل من 0.5 ثانية ، بالكاد يمكن للمستخدمين ملاحظة ذلك ، خاصةً إذا كان الجري على موضوع منفصل.

قصدت التدوين حول هذا الموضوع لفترة طويلة (مثل عامين :)) لأن هناك حاجة. لكنني أتمكن أخيرًا من كتابة كلمات قليلة حول هذا الموضوع وتقديم بعض النصائح. يرجى التحقق من ذلك هنا:

ariolvable.blogspot.com

على الرغم من أنها مخصصة لمنصة Microsoft ، إلا أن المبادئ العامة هي نفسها.

Answer 5

نعم ، يمكن أن يكون هذا أسرع بكثير. لسبب واحد ، لا تحتاج إلى StringBuffers على الإطلاق. لآخر ، لا تحتاج إلى حلقة منفصلة لحساب النقل.

يمكنك إيجاد تنفيذي هنا, ، ويجب أن يكون أسرع بكثير. إنه تحت رخصة Apache 2.0.

Answer 6

بدلاً من ذلك ، إرجاع الأحرف الشائعة باستخدام طريقة 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;
        }
    }
}

التحسين الآخر هو التخلص مسبقًا لعمق Bitmask لكل سلسلة. باستخدام ذلك ، تحقق مما إذا كان الحرف الحالي في السلسلة الأولى موجودة في الثانية. يمكن القيام بذلك باستخدام عمليات فعالة.

سيؤدي ذلك إلى تخطي حساب الحد الأقصى/دقيقة والحلقات للشخصيات المفقودة.