Řetězcová metrika - String metric

"Řetězcová vzdálenost" přeadresuje tady. Vzdálenost mezi strunami a hmatníkem v hudebních nástrojích viz Akce (hudba).

v matematika a počítačová věda, a řetězec metrický (také známý jako metrika podobnosti řetězce nebo funkce vzdálenosti řetězce) je metrický to měří vzdálenost („inverzní podobnost“) mezi dvěma textové řetězce pro přibližná shoda řetězců nebo srovnání a v fuzzy vyhledávání řetězců. Požadavek na řetězec metrický (např. na rozdíl od shoda řetězce ) je naplněním nerovnost trojúhelníku. Například řetězce „Sam“ a „Samuel“ lze považovat za blízké.[1] Řetězcová metrika poskytuje číslo označující indikaci vzdálenosti specifické pro algoritmus.

Nejznámější metrikou řetězce je elementární metrika, která se nazývá Levenshteinova vzdálenost (také známý jako upravit vzdálenost).[2] Funguje mezi dvěma vstupními řetězci a vrací číslo ekvivalentní počtu substitucí a delecí potřebných k transformaci jednoho vstupního řetězce na jiný. Zjednodušené metriky řetězce, jako je Levenshteinova vzdálenost rozšířili o fonetické, žeton, gramatické a znakové metody statistických srovnání.

Řetězcové metriky jsou hojně používány v informační integrace a v současné době se používají v oblastech včetně detekce podvodů, analýza otisků prstů, detekce plagiátů, sloučení ontologie, Analýza DNA, Analýza RNA, analýza obrazu na základě důkazů strojové učení, databáze deduplikace dat, dolování dat, přírůstkové vyhledávání, integrace dat a sémantické znalostní integrace.

Seznam metrik řetězců

Vybrané příklady měřících řetězců

názevPříklad
Hammingova vzdálenost"karolv" a "kathrv"je 3.
Levenshteinova vzdálenost a Vzdálenost Damerau – LevenshteinkittEn a sittinG mít vzdálenost 3.
  1. kitten → sitten (nahrazení „s“ slovem „k“)
  2. sittEn → sittin (nahrazení „i“ slovem „e“)
  3. sedět → sedětG (vložení „g“ na konec).
Vzdálenost Jaro – WinklerJaroWinklerDist ("MARTHA", "MARHTA") =
  • je počet odpovídající znaky;
  • je poloviční počet transpozice(„MARTHA“ [3]! = H, „MARHTA“ [3]! = T).
Nejčastější k znakyMostFreqKeySimilarity ('rEsEArch ',' seeking ', 2) = 2

Reference

  1. ^ Lu, Jiaheng; et al. (2013). „Měření podobnosti řetězců a spojení se synonymy“. Sborník mezinárodní konference ACM SIGMOD o správě dat z roku 2013: 373–384. doi:10.1145/2463676.2465313. ISBN  9781450320375.
  2. ^ Navarro, Gonzalo (2001). Msgstr "Prohlídka s cílem přiblížit shodu řetězců". ACM Computing Surveys. 33 (1): 31–88. doi:10.1145/375360.375365.
  3. ^ Cohen, William; Ravikumar, Pradeep; Fienberg, Stephen (01.08.2003). „Srovnání metrik vzdálenosti řetězce pro úkoly přiřazování jmen“: 73–78. Citovat deník vyžaduje | deník = (Pomoc)

externí odkazy