jaka jest dobra metryka przy podejmowaniu decyzji, czy 2 ciągi są " wystarczająco podobne"
Pracuję nad bardzo szorstkim algorytmem pierwszego szkicu, aby określić, jak podobne są 2 ciągi. Używam również Levenshtein Distance aby obliczyć odległość edycji między łańcuchami.
To, co obecnie robię, to w zasadzie biorąc całkowitą liczbę edycji i dzieląc ją przez rozmiar większego ciągu. Jeśli wartość ta jest poniżej pewnego progu, obecnie losowo ustawiona na 25%, to są one "wystarczająco podobne".
Jednak jest to całkowicie arbitralne i nie sądzę, aby było bardzo dobry sposób na obliczenie podobieństwa. Czy istnieje jakieś równanie matematyczne lub Prawdopodobieństwo / statystyka podejście do podejmowania Levenshtein dane odległości i używając go, aby powiedzieć "tak, te ciągi są wystarczająco podobne w oparciu o liczbę edycji wykonanych i rozmiar ciągów"?
Kluczowe jest również to, że używam arbitralnego progu i wolałbym tego nie robić. Jak mogę obliczyć ten próg zamiast przypisać go tak, że mogę bezpiecznie powiedzieć, że 2 ciągi są "wystarczająco podobne" ?
UPDATE
Porównuję ciągi znaków, które reprezentują ślad stosu Javy. Powodem, dla którego chcę to zrobić, jest pogrupowanie kilku podanych śladów stosu według podobieństwa i użycie go jako filtra do sortowania "rzeczy":) to grupowanie jest ważne z powodu wyższego poziomu, którego nie mogę dokładnie udostępnić publicznie.
Jak na razie mój algorytm (pseudo kod) jest mniej więcej w linii:
/*
* 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!
}
4 answers
A co powiesz na użycie podobieństwa cosinusowego? Jest to ogólna technika oceny podobieństwa między dwoma tekstami. Działa on w następujący sposób:
Weź wszystkie litery z obu łańcuchów i zbuduj tabelę w ten sposób:
Letter | String1 | String2
To może być prosta tabela hash lub cokolwiek innego.
W kolumnie litera umieść każdą literę, a w kolumnach łańcuchowych umieść ich częstotliwość wewnątrz tego łańcucha (jeśli litera nie pojawia się w łańcuchu, wartość jest równa 0).
Nazywa się podobieństwem cosinusa, ponieważ ty interpretuje każdą z dwóch kolumn łańcuchowych jako wektory, gdzie każdy składnik jest liczbą powiązaną z literą. Następnie Oblicz cosinus "kąta" między wektorami jako:
C = (V1 * V2) / (|V1| * |V2|)
Licznik jest iloczynem punktowym, czyli sumą iloczynów odpowiednich składników, a mianownik jest iloczynem wielkości wektorów.
Jak blisko C jest do 1 daje Ci, jak podobne są łańcuchy.
To może wydawać się skomplikowane, ale to tylko kilka linijek kodu kiedy zrozumiesz pomysł.
Spójrzmy na przykład: rozważmy ciągi
s1 = aabccdd
s2 = ababcd
Tabela wygląda następująco:
Letter a b c d
s1 2 1 2 2
s2 2 2 1 1
I tak:
C = (V1 * V2) / (|V1| * |V2|) =
(2 * 2 + 1 * 2 + 2 * 1 + 2 * 1) / (sqrt(13) * sqrt(10)) = 0.877
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-09 23:52:53
Ślady stosu są w formacie umożliwiającym analizę. Chciałbym po prostu parsować ślady stosu za pomocą biblioteki parsowania, a następnie można wyodrębnić jaką treść semantyczną chcesz porównać.
Algorytmy podobieństwa będą wolniejsze i trudne do debugowania, gdy ciągi znaków nie będą porównywane tak, jak się spodziewasz.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-09 21:27:09
Oto moje zdanie na ten temat - po prostu długa historia do rozważenia i niekoniecznie odpowiedź na twój problem:
Zrobiłem coś podobnego w przeszłości, gdzie starałem się ustalić, czy ktoś jest plagiatem, po prostu zmieniając zdania, zachowując ten sam rodzaj wiadomości.
1 "dzieci powinny bawić się, gdy jemy obiad"
2 "gdy jemy obiad, dzieci powinny się bawić"
3 "powinniśmy jeść dzieci podczas zabawy"
Więc levenshtein nie byłby zbyt użyj tutaj, ponieważ jest liniowy i każdy z nich byłby znacznie inny. Standardowa różnica zdałaby egzamin i studentowi uszłoby to na sucho.
Więc złamałem każde słowo w zdaniach i rekomponowałem zdania jako tablice, a następnie porównałem je do pierwszego określenia, czy słowo istniało w każdej tablicy i gdzie było w stosunku do ostatniego. Następnie każde słowo będzie sprawdzać następne w tablicy, aby określić, czy istnieją kolejne słowa, jak w moim przykładzie zdania powyżej linii 1 i 2. Więc gdyby były słowa sekwencyjne, skomponowałbym ciąg każdej sekwencji wspólny dla każdej tablicy, a następnie spróbowałbym znaleźć różnice w pozostałych słowach. Im mniej pozostałych słów, tym bardziej prawdopodobne jest, że są one tylko wypełniaczem, aby wydawały się mniej plagiatowane.
"kiedy jemy obiad, myślę, że dzieci powinny się bawić"
Następnie" myślę " jest oceniany i uważany za wypełniacz na podstawie leksykonu słów kluczowych - ta część jest tutaj trudna do opisania.
To był to złożony projekt, który zrobił o wiele więcej niż tylko to, co opisałem, a nie prosty fragment kodu, który mogę łatwo udostępnić, ale powyższy pomysł nie jest zbyt trudny do powielenia.
Powodzenia. Interesuje mnie, co inni członkowie SO mają do powiedzenia na temat Twojego pytania.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-09 21:31:56
Ponieważ odległość Levenshteina nigdy nie jest większa niż długość dłuższego ciągu, z pewnością zmieniłbym mianownik z (length1 + length2) na Math.max(length1, length2). To znormalizowałoby metrykę w przedziale od zera do jedynki.
Teraz nie można odpowiedzieć na to, co jest" wystarczająco podobne " dla Twoich potrzeb na podstawie dostarczonych informacji. Osobiście staram się unikać funkcji krokowych, jak masz z odcięcia 0.25, preferując ciągłe wartości ze znanego interwału. Być może lepiej byłoby nakarmić ciągłe "podobieństwo" (lub "odległość") wartości do algorytmów wyższego poziomu zamiast przekształcania tych wartości w binarne?
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-09 21:48:08