Я работаю над очень грубым алгоритмом первого проекта, чтобы определить, насколько похожи 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!
}
