Сходство - Левенштейн

Question

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

Итак, я хочу знать, как рассчитать эти точки сходства.

Я также хотел бы знать, как вы, люди, делаете это и почему.

Answer 1

Расстояние Левенштейна между двумя строками определяется как минимальное количество правок, необходимых для преобразования одной строки в другую, с допустимыми операциями редактирования, такими как вставка, удаление или замена одногоперсонаж.(Википедия)

• Таким образом, расстояние Левенштейна, равное 0, означает: обе строки равны
• Максимальное расстояние Левенштейна (все символы различны) равно max (string1.length,string2.length)

Так что, если вам нужен процент, вы должны использовать его, чтобы указать масштаб.Например:

«Привет», «Привет» -> Расстояние Левенштейна 1 Максимальное расстояние Левенштейна для этих двух строк равно: 5. Таким образом, 20% символов не совпадают.

String s1 = "Hallo";
String s2 = "Hello";
int lfd = calculateLevensteinDistance(s1, s2);
double ratio = ((double) lfd) / (Math.max(s1.length, s2.length));

Answer 2

Вы можете скачать Apache Commons StringUtils и исследовать (и, возможно, использовать) их реализацию алгоритма расстояния Левенштейна.

Answer 3

 // Refer This: 100% working

public class demo 
{
public static void main(String[] args) 
{
    String str1, str2;

    str1="12345";
    str2="122345";


    int re=pecentageOfTextMatch(str1, str2);
    System.out.println("Matching Percent"+re);
}

public static int pecentageOfTextMatch(String s0, String s1) 
{                       // Trim and remove duplicate spaces
    int percentage = 0;
    s0 = s0.trim().replaceAll("\\s+", " ");
    s1 = s1.trim().replaceAll("\\s+", " ");
    percentage=(int) (100 - (float) LevenshteinDistance(s0, s1) * 100 / (float) (s0.length() + s1.length()));
    return percentage;
}

public static int LevenshteinDistance(String s0, String s1) {

    int len0 = s0.length() + 1;
    int len1 = s1.length() + 1;  
    // the array of distances
    int[] cost = new int[len0];
    int[] newcost = new int[len0];

    // initial cost of skipping prefix in String s0
    for (int i = 0; i < len0; i++)
        cost[i] = i;

    // dynamically computing the array of distances

    // transformation cost for each letter in s1
    for (int j = 1; j < len1; j++) {

        // initial cost of skipping prefix in String s1
        newcost[0] = j - 1;

        // transformation cost for each letter in s0
        for (int i = 1; i < len0; i++) {

            // matching current letters in both strings
            int match = (s0.charAt(i - 1) == s1.charAt(j - 1)) ? 0 : 1;

            // computing cost for each transformation
            int cost_replace = cost[i - 1] + match;
            int cost_insert = cost[i] + 1;
            int cost_delete = newcost[i - 1] + 1;

            // keep minimum cost
            newcost[i] = Math.min(Math.min(cost_insert, cost_delete),
                    cost_replace);
        }

        // swap cost/newcost arrays
        int[] swap = cost;
        cost = newcost;
        newcost = swap;
    }

    // the distance is the cost for transforming all letters in both strings
    return cost[len0 - 1];
}

}

Answer 4

Для подсчета очков вам нужна максимально возможная стоимость (вставка + выпадение + замена). Тогда используйте приведенную ниже формулу -

score = 1 - actual_cost/max_possible_cost

См. Это для справки - Функция подсчета баллов Левенштейна

Answer 5

Я думаю, что было бы полезно ссылка LevenshteinDistance

Может использоваться через зависимость maven

зависимость maven

Я думаю, что лучше использовать эту реализацию, чем писать свой собственный код.

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-text</artifactId>
    <version>1.3</version>
</dependency>

В качестве примера рассмотрим приведенный ниже код

import org.apache.commons.text.similarity.LevenshteinDistance;

public class MetricUtils {
    private static LevenshteinDistance lv = new LevenshteinDistance();

    public static void main(String[] args) {
        String s = "running";
        String s1 = "runninh";
        System.out.println(levensteinRatio(s, s1));
    }

    public static double levensteinRatio(String s, String s1) {
        return 1 - ((double) lv.apply(s, s1)) / Math.max(s.length(), s1.length());
    }
}

Answer 6

Максимальное значение разности Левенштейна между двумя строками будет равно максимальной длине двух струн. (Это соответствует изменению символа для каждого из символов вплоть до длины более короткой строки, плюс вставляет или удаляет в зависимости от того, переходите вы от более короткого к более длинному или наоборот.) Учитывая это, сходство двух строки должны быть отношением между этим максимумом и разницей между этим максимумом и фактической разностью Левенштейна.

Реализации алгоритма Левенштейна имеют тенденцию не записывать, какими должны быть эти правки, но это не должно быть так сложно вычислить, учитывая абстрактный алгоритм на странице Википедии .