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

Question

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.

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.

Answer 1

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

powinny być poprawne

Answer 2

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?

Answer 3

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.

Answer 4

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)

Answer 5

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)