Что такое хороший показатель для решения, если 2 строки "достаточно похожи"

Question

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

В настоящее время я в основном беру общее количество правок и делю его на размерСтрока большего размера.Если это значение ниже некоторого порогового значения, в настоящее время произвольно установленного на 25%, тогда они «достаточно похожи».

Однако это совершенно произвольно, и я не думаю, что это очень хороший способ для вычисления подобия.Существует ли какой-то математический подход или вероятностно-статистический подход к получению данных о расстоянии Левенштейна и их использованию, чтобы сказать «да, эти строки достаточно похожи, основываясь на количестве сделанных правок и размере строк»?

Кроме того, ключевым моментом здесь является то, что я использую произвольный порог и предпочел бы не делать этого.Как я могу вычислить этот порог вместо того, чтобы назначить его, чтобы я мог с уверенностью сказать, что 2 строки "достаточно похожи" ?

ОБНОВЛЕНИЕ

Я сравниваю строки,представляют трассировку стека Java.Причина, по которой я хочу сделать это, состоит в том, чтобы сгруппировать набор данных трассировок стека по сходству и использовать его в качестве фильтра для сортировки «вещей» :) Эта группировка важна по причине более высокого уровня, которой я не могу точно поделиться публично.

---

Пока что мой алгоритм (псевдокод) примерно такой:

/*
 * The input lists represent the Strings I want to test for similarity. The
 * Strings are split apart based on new lines / carriage returns because Java
 * stack traces are not a giant one-line String, rather a multi-line String.
 * So each element in the input lists is a "line" from its stack trace.
 */
calculate similarity (List<String> list1, List<String> list2) {

    length1 = 0;
    length2 = 0;
    levenshteinDistance = 0;

    iterator1 = list1.iterator();
    iterator2 = list2.iterator();

    while ( iterator1.hasNext() && iterator2.hasNext() ) {

        // skip blank/empty lines because they are not interesting
        str1 = iterator1.next();    length1 += str1.length();
        str2 = iterator2.next();    length2 += str2.length();

        levensteinDistance += getLevenshteinDistance(str1, str2);
    }

    // handle the rest of the lines from the iterator that has not terminated

    difference = levenshteinDistance / Math.max(length1, length2);

    return (difference < 0.25) ? true : false; // <- arbitrary threshold, yuck!
}

Answer 1

Как насчет использования косинусного сходства?Это общий метод оценки сходства между двумя текстами.Это работает следующим образом:

Возьмите все буквы из обеих строк и создайте таблицу, подобную этой:

Letter | String1 | String2

Это может быть простая хеш-таблица или что-то еще.

В столбце буквы укажите каждую букву, а в столбцах строки - их частоту внутри этой строки (если буква не появляется в строке, значение равно 0).

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

C = (V1 * V2) / (|V1| * |V2|)

Числитель - это скалярное произведение, то есть сумма произведений соответствующих компонентов, а знаменатель - произведениеразмеры векторов.

То, как близко C к 1, показывает, насколько похожи строки.

Это может показаться сложным, но это всего лишь несколько строк кода, как только вы поймете идею.

Давайте рассмотрим пример: рассмотрим строки

s1 = aabccdd
s2 = ababcd

Таблица выглядит следующим образом:

Letter a b c d
s1     2 1 2 2
s2     2 2 1 1

И, таким образом:

C = (V1 * V2) / (|V1| * |V2|) = 
(2 * 2 + 1 * 2 + 2 * 1 + 2 * 1) / (sqrt(13) * sqrt(10)) = 0.877

Итакони "довольно" похожи.

Answer 2

Трассировки стека находятся в формате, пригодном для анализа.Я бы просто проанализировал трассировки стека, используя библиотеку синтаксического анализа, и затем вы можете извлечь любой семантический контент, который вы хотите сравнить.

Алгоритмы подобия будут медленнее и сложнее в отладке, когда строки не сравниваются, как выожидать.

Answer 3

Вот мое мнение об этом - просто длинная история для рассмотрения и не обязательно ответ на вашу проблему:

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

1 «дети должны играть, когда мы ужинаем», «
2», пока мы ужинаем, дети должны играть «
3», что мы должны естьдети, пока мы играем "

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

Поэтому я разбил каждое слово в предложениях и перекомпоновал предложения как массивы, затем сравнил друг друга, чтобы сначала определить, существовало ли словов каждом массиве, и где это было по отношению к последнему.Затем каждое слово проверяет следующее в массиве, чтобы определить, были ли последовательные слова, как в моих примерах предложения над строками 1 и 2. Поэтому, если бы были последовательные слова, я бы составил строку каждой последовательности, общую для каждого массива, а затемпопытаться найти различия в оставшихся словах.Чем меньше оставшихся слов, тем больше шансов, что они будут просто наполнителями, чтобы они казались менее плагиатными.

«пока мы ужинаем, я думаю, что дети должны играть»

Тогда «я думаю»оцениваемый и рассматриваемый наполнитель на основе лексики ключевого слова - эту часть здесь сложно описать.

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

Удачи.Мне интересно, что другие члены SO скажут по вашему вопросу.

Answer 4

Поскольку расстояние Левенштейна никогда не превышает длину более длинной строки, я определенно изменил бы знаменатель с (length1 + length2) на Math.max(length1, length2). Это нормализует метрику от нуля до единицы.

Теперь невозможно ответить на то, что "достаточно похоже" для ваших нужд, основываясь на предоставленной информации. Я лично стараюсь избегать пошаговых функций, как у вас с отсечкой 0,25, предпочитая непрерывные значения из известного интервала. Возможно, было бы лучше передать непрерывные значения «сходства» (или «расстояния») в алгоритмы более высокого уровня вместо преобразования этих значений в двоичные?