Procentowa pozycja meczów za pomocą Levenshtein Dopasowywanie odległości

Próbuję dopasować pojedynczy termin do wyszukania w słowniku możliwych wyników za pomocą algorytmu odległości Levenshteina. Algorytm zwraca odległość wyrażoną jako liczba operacji wymaganych do przekształcenia ciągu wyszukiwania w dopasowany ciąg. Chcę przedstawić wyniki w rankingu procentowej listy najlepszych "N" (powiedzmy 10) meczów.Procentowa pozycja meczów za pomocą Levenshtein Dopasowywanie odległości

Ponieważ szukany ciąg może być dłuższy lub krótszy niż poszczególne ciągi słowników, jaka byłaby odpowiednia logika wyrażania odległości jako wartości procentowej, co w sposób jakościowy zmieniłoby dopasowanie "jako procent" do wyniku każdego zapytania ciąg, przy czym 100% oznacza dokładne dopasowanie.

Rozważałem następujące opcje:

Q = query string 
M = matched string 
PM = Percentage Match 
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100 
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100

Opcja 1 ma możliwość negatywnych procentowych w przypadku, gdy odległość jest większa niż długość ciągu wyszukiwania, gdzie ciąg mecz jest długa. Na przykład zapytanie "ABC" pasujące do "ABC Corp." spowoduje wynik ujemny.

Opcja 2 nie wydaje się zapewniać stałego udziału procentowego w całym zestawie Mi, ponieważ każde obliczenie prawdopodobnie używa innego mianownika, w związku z czym wynikowe wartości procentowe nie zostaną znormalizowane.

Jedyny inny sposób, jaki mogę wymyślić, to porzucić porównanie wartości lev_distance do obu długości łańcuchów, ale zamiast tego przedstawimy odległości względne najwyższych "N" jako odwrotną pozycję percentyla (100-percentile-rank).

Jakieś myśli? Czy istnieją lepsze podejścia? Muszę czegoś pomijać, ponieważ odległość Levenshteina jest prawdopodobnie najczęstszym algorytmem dla dopasowań rozmytych i to musi być bardzo powszechny problem.

Źródło

2012-05-01 user1368587

Co o swoim 1st opcją ale kiedy wynik jest ujemny, po prostu zwraca 0? PS: Wysłałem problem również tutaj http://math.stackexchange.com/questions/1776860/convert-levenshtein-distance-to-percent –

Nie rozumiem, jaki jest problem z Option2, ponieważ zaimplementowałem dokładnie ta sama logika, którą opisujesz i wydaje się działać poprawnie. Czy możesz wyjaśnić to lepiej? – Roberto14

(1 - (levNum/Math.max(s.length,t.length))) *100

powinny być poprawne

Źródło

2013-01-09 14:51:50

Wstępne pytanie już ma to rozwiązanie jako "Opcja 2". Szuka alternatywnego rozwiązania problemu. –

Ta opcja 2 jest zasadniczo wspomniane w moim pytaniem. Jednak pozwól mi zademonstrować problem z tym podejściem.

Q = "ABC Corp" (len = 8) 
M1 = "ABC" 
M2 = "ABC Corporati" 
M3 = "ABC Corp"

Wybrałem M1 i M2 w taki sposób, że ich odległości Lev są takie same (po 5). Korzystanie z opcji 2, procenty mecz byłby

M1 = (1 - 5/8)*100 = 37.5% 
M2 = (1 - 5/13)*100 = 61.5% 
M3 = 100%

Jak widać, jeśli przedstawię mecze w tej kolejności, istnieje ogromna różnica ranga pomiędzy M1 i M2, choć mają taką samą odległość Lev. Widzisz problem?

Źródło

2013-01-11 01:01:45

Po pewnym czasie myślę, że to jest prawidłowe podejście. Załóżmy, że masz bardzo krótkie łańcuchy, których LevDisstance wynosi 5. Załóżmy, że masz bardzo długie łańcuchy, których LevDist ma równe 5. To prawda, że najkrótsze struny są mniej podobne niż dłuższe. –

Tbh, nie widzę problemu, ponieważ jak powiedział @ Wakan Tanka, ten sam dystans do dłuższego napisu oznacza, że więcej postaci pasowało między nimi. W związku z tym nie ma problemu, a opcja 2 jest poprawną opcją. – Roberto14

Moje podejście do tego problemu polegało na obliczeniu maksymalnych dozwolonych operacji, czyli na odległość Levenshtein. Zastosowany wzór:

percent = 0.75; // at least 75% of string must match 
maxOperationsFirst = s1.length() - s1.length() * percent; 
maxOperationsSecond = s2.length() - s2.length() * percent; 
maxOperations = round(min(maxOperationsFirst, maxOperationsSecond));

Oblicza maksymalne operacje dla każdego ciągu, uważam, że obliczenia są łatwe do zrozumienia. Używam minimalnej wartości obu wyników i zaokrąglaję ją do najbliższej liczby całkowitej. Możesz pominąć tę część i użyć tylko wartości maksymalnej operacji z jednego z ciągów, to naprawdę zależy od twoich danych.

Po osiągnięciu maksymalnej liczby operacji można porównać ją z wynikiem levenshtein i określić, czy ciąg znaków jest akceptowalny. W ten sposób można użyć dowolnych rozszerzonych metod levenshtein, na przykład Damerau–Levenshtein distance, które liczą błędy pisowni, np. , np.test -> tset, tylko jako 1 operacja, co jest bardzo przydatne przy sprawdzaniu danych wprowadzanych przez użytkownika, gdy te błędy występują często.

Mam nadzieję, że pomoże ci to zorientować się, jak rozwiązać ten problem.

Źródło

2013-08-14 23:11:45

Wydaje mi się to dobre. – tonix

Miałem podobny problem i ten wątek pomógł mi znaleźć rozwiązanie. Mam nadzieję, że może pomóc także innym.

int levDis = Lev_distance(Q, Mi) 
int bigger = max(strlen(Q), strlen(Mi)) 
double pct = (bigger - levDis)/bigger

Powinno zwrócić 100%, jeśli oba ciągi są dokładnie takie same, a 0%, jeśli są one całkowicie różne.

(przepraszam, jeśli mój angielski nie jest dobry)

Źródło

2014-02-11 14:49:52

To nie jest poprawne, ponieważ daje różne wyniki dla '(" ABC Corp "," ABC ")' i '(" ABC Corp "," ABC Corporati ")' –

to jest zła odpowiedź. –

Co z tego:

100 - (((2*Lev_distance(Q, Mi))/(Q.length + Mi.length)) * 100)

Daje taką samą odległość na (Q, M1) i (Q,M2)

Źródło

2016-05-08 09:06:52

Procentowa pozycja meczów za pomocą Levenshtein Dopasowywanie odległości

Odpowiedz

Powiązane problemy