Metryka ciągu

„Odległość struny” przekierowuje tutaj. Aby zapoznać się z odległością między strunami a podstrunnicą w instrumentach muzycznych, zobacz Akcja (muzyka) .

W matematyce i informatyce metryka ciągów (znana również jako metryka podobieństwa ciągów lub funkcja odległości ciągów ) to metryka , która mierzy odległość („odwrotne podobieństwo”) między dwoma ciągami tekstowymi w celu przybliżonego dopasowania lub porównania ciągów oraz w wyszukiwaniu ciągów rozmytych . Wymogiem dla metryki łańcuchowej (np. w przeciwieństwie do dopasowywania ciągów ) jest spełnienie warunku nierówność trójkąta . Na przykład ciągi „Sam” i „Samuel” można uznać za zbliżone. Metryka łańcuchowa zawiera liczbę wskazującą specyficzne dla algorytmu wskazanie odległości.

Najbardziej znaną metryką struny jest podstawowa metryka zwana odległością Levenshteina (znana również jako odległość edycji). Działa między dwoma ciągami wejściowymi, zwracając liczbę odpowiadającą liczbie podstawień i usunięć potrzebnych do przekształcenia jednego ciągu wejściowego w inny. Uproszczone metryki łańcuchowe, takie jak odległość Levenshteina , zostały rozszerzone o fonetyczne, tokenowe , gramatyczne i oparte na znakach metody porównań statystycznych.

Metryki łańcuchowe są intensywnie wykorzystywane w integracji informacji i są obecnie wykorzystywane w takich obszarach, jak wykrywanie oszustw , analiza odcisków palców , wykrywanie plagiatu , łączenie ontologii , analiza DNA , analiza RNA, analiza obrazu , uczenie maszynowe oparte na dowodach , deduplikacja danych z baz danych , eksploracja danych , przyrostowe wyszukiwanie , integracja danych , wykrywanie złośliwego oprogramowania i semantyka integracja wiedzy .

Lista metryk łańcuchowych

• Odległość Levenshteina lub jej uogólniona odległość edycji
• Odległość Damerau-Levenshteina
• Współczynnik Sørensena-Dice'a
• Odległość bloku lub odległość L1 lub odległość bloku miasta
• Odległość Hamminga
• Prosty współczynnik dopasowania (SMC)
• Podobieństwo Jaccarda lub współczynnik Jaccarda lub współczynnik Tanimoto
• Indeks Twerskiego
• Współczynnik nakładania się
• Dystans zmienny
• Odległość Hellingera lub odległość Bhattacharyya
• Promień informacyjny ( dywergencja Jensena – Shannona )
• Rozbieżność skośna
• Prawdopodobieństwo zamieszania
• Metryka Tau , przybliżenie dywergencji Kullbacka – Leiblera
• Metryka Fellegiego i Suntersa (SFS)
• Maksymalne dopasowania
• Dystans oparty na gramatyce
• Metryka odległości TFIDF

Istnieją również funkcje, które mierzą odmienność między ciągami, ale niekoniecznie spełniają nierówność trójkąta i jako takie nie są metrykami w sensie matematycznym. Przykładem takiej funkcji jest odległość Jaro – Winklera .

Wybrane przykłady taktów smyczkowych

Nazwa	Opis	Przykład
Odległość Hamminga	Tylko dla łańcuchów o tej samej długości. Liczba zmienionych znaków.	„ ka rol in ” i „ ka thr in ” wynosi 3.
Odległość Levenshteina i odległość Damerau-Levenshteina	Uogólnienie odległości Hamminga, które pozwala na różne długości strun i (z Damerau) na transpozycje	k itt e n i s itt i n g mają odległość 3. k itten → s itten (podstawienie „s” na „k”) sitt e n → sitt i n (podstawienie „i” na „e”) siedzenie → siedzenie g (wstawienie „g” na końcu).
Odległość Jaro-Winklera		Rozkład Jaro-Winklera("MARTHA","MARHTA") = ${\ Displaystyle d_ {j} = {\ Frac {1} {3}} \ lewo ({\ Frac {m} {| s_ {1} |}} + {\ Frac {m} {| s_ {2} | }}+{\frac {mt}{m}}\right)={\frac {1}{3}}\left({\frac {6}{6}}+{\frac {6}{6} }+{\frac {6-{\frac {2}{2}}}{6}}\right)=0,944}$ ${\ displaystyle m}$ to liczba pasujących znaków ; ${\ displaystyle t}$ to połowa liczby transpozycji ( "MARTHA" [3]! = H, "MARHTA" [3]! = T ).
Najczęściej występujące k znaków		MostFreqKeySimilarity(' re s e a r ch', ' see king', 2) = 2

Linki zewnętrzne

• Metryki podobieństwa łańcuchów do integracji informacji Dość kompletny przegląd Indeks archiwum w Wayback Machine
• Biblioteka open source Uniwersytetu Carnegie Mellon
• StringMetric projektuje bibliotekę Scala zawierającą metryki łańcuchowe i algorytmy fonetyczne
• Projekt Natural to biblioteka przetwarzania języka naturalnego JavaScript , która zawiera implementacje popularnych metryk łańcuchowych