Что является хорошим показателем для принятия решения о том, что 2 строки являются "достаточно похожими"
Я работаю над очень грубым алгоритмом первого проекта, чтобы определить, насколько похожи 2 строки. Я также использую Levenshtein Distance для вычисления расстояния редактирования между строками.
То, что я делаю в настоящее время, в основном принимает общее количество изменений и делит его на размер более крупной строки. Если это значение ниже некоторого порога, в настоящее время в случайном порядке установлено значение 25%, то они "достаточно похожи".
Однако это абсолютно произвольно, и я не думаю, что это очень хороший способ рассчитать сходство. Существует ли какое-то математическое уравнение или метод вероятности/статистики для получения данных о расстоянии Левенштейна и использования его, чтобы сказать "да, эти строки достаточно похожи на количество внесенных изменений и размер строк"?
Кроме того, ключевым моментом здесь является то, что я использую произвольный порог, и я бы предпочел не делать этого. Как я могу вычислить этот порог, а не назначать его, чтобы я мог смело сказать, что 2 строки имеют "достаточно похожий" ?
UPDATE
Я сравниваю строки, представляющие трассировку стека Java. Причина, по которой я хочу это сделать, - группировать кучу заданных трассировок стека по подобию и использовать его как фильтр для сортировки "stuff":) Эта группировка важна для причины более высокого уровня, которую я не могу точно публиковать публично.
До сих пор мой алгоритм (псевдокод) примерно соответствовал строкам:
/*
* 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!
}
Ответы
Ответ 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
Итак, они "очень похожи".
Ответ 2
Трассировка стека в формате, пригодном для синтаксического анализа. Я просто разбирал бы трассировки стека, используя библиотеку синтаксического анализа, а затем вы можете извлечь любой семантический контент, который хотите сравнить.
Алгоритмы схожести будут медленнее и труднее отлаживать, когда строки не сравниваются, как вы ожидаете.
Ответ 3
Вот мой взгляд на это - просто долгая история, чтобы рассмотреть и не обязательно ответить на вашу проблему:
В прошлом я сделал что-то похожее, где я попытался бы определить, плагиат ли кто-то, просто переставляя предложения при сохранении такого же сообщения.
1 "дети должны играть, пока мы едим обед"
2 ", пока мы едим обед, дети должны играть"
3 "мы должны есть детей, пока мы играем"
Таким образом, levenshtein не будет иметь большого значения здесь, потому что он линейный, и каждый из них будет значительно отличаться. Стандартная разница прошла бы тест, и ученик избежал бы преступления.
Итак, я сломал каждое слово в предложениях и переформулировал предложения как массивы, затем сравнил друг друга, чтобы определить, существовало ли слово в каждом массиве и где оно было по отношению к последнему. Затем каждое слово проверяет следующее в массиве, чтобы определить, были ли последовательные слова, например, в моих примерах предложений выше строк 1 и 2.
Поэтому, если бы были последовательные слова, я бы составил строку каждой последовательности, общую для каждого массива, а затем попытался найти различия в остальных словах. Чем меньше оставшихся слов, тем больше вероятность, что они просто наполнители, чтобы они казались менее плагиатными.
", пока мы едим обед, я думаю, что дети должны играть"
Затем "Я думаю" оценивается и считается наполнителем на основе словарного словаря - эту часть трудно описать здесь.
Это был сложный проект, который сделал намного больше, чем то, что я описал, а не простой кусок кода, с которым я могу легко поделиться, но вышеприведенную идею не так сложно реплицировать.
Удачи. Меня интересует, что другие члены SO могут сказать о вашем вопросе.
Ответ 4
Поскольку расстояние Левенштейна никогда не превышает длину более длинной строки, я бы, конечно, изменил знаменатель от (length1 + length2) до Math.max(length1, length2). Это нормализовало бы метрику в пределах от нуля до единицы.
Теперь невозможно ответить на то, что "достаточно достаточно" для ваших нужд на основе предоставленной информации. Я лично стараюсь избегать ступенчатых функций, как у вас, с обрезкой 0,25, предпочитая непрерывные значения с известного интервала. Возможно, лучше было бы передавать непрерывные значения "сходства" (или "расстояния" ) в алгоритмы более высокого уровня вместо преобразования этих значений в двоичные?
