Metryka ciągu - String metric

„Odległość ciągu znaków” przekierowuje tutaj. Odległość między strunami a podstrunnicą w instrumentach muzycznych, patrz Akcja (muzyka) .

W matematyce i informatyce , o metrykę ciąg (znany również jako podobieństwa ciąg metrycznym lub funkcji odległości ciąg ) jest metryka , że środki odległość ( „odwrotny podobieństwo”) pomiędzy dwa ciągi tekstowe dla przybliżonego dopasowywania strun lub porównania i rozmyty poszukiwań strun . Wymaganiem dla metryki łańcuchowej (np. W przeciwieństwie do dopasowania łańcuchowego ) jest spełnienie nierówności trójkąta . Na przykład ciągi „Sam” i „Samuel” można uznać za bliskie. Metryka łańcuchowa zawiera liczbę wskazującą specyficzne dla algorytmu wskazanie odległości.

Najbardziej znaną metryką łańcuchową jest prymitywna 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 ciągów, takie jak odległość Levenshteina, zostały rozszerzone o metody porównań fonetycznych, tokenowych , gramatycznych i znakowych.

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

Lista metryk ciągów

Wybrane przykłady miar łańcuchowych

Nazwa Przykład
Odległość Hamminga „ ka rol in ” i „ ka thr in ” to 3.
Odległość Levenshteina i odległość Damerau – Levenshteina k itt e n i s itt i n g mają odległość 3.
  1. k itten → s itten (podstawienie "s" zamiast "k")
  2. sitt e n → sitt i n (podstawienie „i” zamiast „e”)
  3. sittin → sittin g (wstawienie "g" na końcu).
Odległość Jaro – Winklera JaroWinklerDist ("MARTHA", "MARHTA") =
  • to liczba pasujących znaków ;
  • to połowa liczby transpozycji ( "MARTHA"[3]!=H, "MARHTA"[3]!=T ).
Najczęstsze k znaków MostFreqKeySimilarity (' r e s e a r ch', 's ee king', 2) = 2


Bibliografia


Zewnętrzne linki