Jak quasi dopasować dwa wektory ciągów (w R)?

Nie jestem pewien, jak to nazwać, więc popraw mnie, jeśli znasz lepszy termin.

Mam dwie listy. Jeden z 55 elementów (np .: wektor ciągów), drugi z 92. Nazwy elementów są podobne, ale nie identyczne.

Życzę, aby znaleźć najlepszego kandydata s w liście do pozycji na liście 55 (będę wtedy przejść przez to i wybrać prawidłowy montaż) 92.

Jak można to zrobić?

Pomysły, które miałem gdzie:

1. Zobacz wszystkie pasujące (używając listy czegoś? Dopasuj)
2. Wypróbuj macierz odległości między wektorami ciągów, ale nie jestem pewien, jak najlepiej to zdefiniować (liczba identycznych liter, co z kolejnością ciągów?)

Więc jaki pakiet / funkcje / dziedzina badań zajmuje się takim zadaniem i jak?

Aktualizacja: Oto przykład wektorów, które chcę dopasować

vec55 <- c("Aeropyrum pernix", "Archaeoglobus fulgidus", "Candidatus_Korarchaeum_cryptofilum", 
"Candidatus_Methanoregula_boonei_6A8", "Cenarchaeum_symbiosum", 
"Desulfurococcus_kamchatkensis", "Ferroplasma acidarmanus", "Haloarcula_marismortui_ATCC_43049", 
"Halobacterium sp.", "Halobacterium_salinarum_R1", "Haloferax volcanii", 
"Haloquadratum_walsbyi", "Hyperthermus_butylicus", "Ignicoccus_hospitalis_KIN4", 
"Metallosphaera_sedula_DSM_5348", "Methanobacterium thermautotrophicus", 
"Methanobrevibacter_smithii_ATCC_35061", "Methanococcoides_burtonii_DSM_6242"
)
vec91 <- c("Acidilobus saccharovorans 345-15", "Aciduliprofundum boonei T469", 
"Aeropyrum pernix K1", "Archaeoglobus fulgidus DSM 4304", "Archaeoglobus profundus DSM 5631", 
"Caldivirga maquilingensis IC-167", "Candidatus Korarchaeum cryptofilum OPF8", 
"Candidatus Methanoregula boonei 6A8", "Cenarchaeum symbiosum A", 
"Desulfurococcus kamchatkensis 1221n", "Ferroglobus placidus DSM 10642", 
"Halalkalicoccus jeotgali B3", "Haloarcula marismortui ATCC 43049", 
"Halobacterium salinarum R1", "Halobacterium sp. NRC-1", "Haloferax volcanii DS2", 
"Halomicrobium mukohataei DSM 12286", "Haloquadratum walsbyi DSM 16790", 
"Halorhabdus utahensis DSM 12940", "Halorubrum lacusprofundi ATCC 49239", 
"Haloterrigena turkmenica DSM 5511", "Hyperthermus butylicus DSM 5456", 
"Ignicoccus hospitalis KIN4/I", "Ignisphaera aggregans DSM 17230", 
"Metallosphaera sedula DSM 5348", "Methanobrevibacter ruminantium M1", 
"Methanobrevibacter smithii ATCC 35061", "Methanocaldococcus fervens AG86", 
"Methanocaldococcus infernus ME", "Methanocaldococcus jannaschii DSM 2661", 
"Methanocaldococcus sp. FS406-22", "Methanocaldococcus vulcanius M7", 
"Methanocella paludicola SANAE", "Methanococcoides burtonii DSM 6242", 
"Methanococcus aeolicus Nankai-3", "Methanococcus maripaludis C5", 
"Methanococcus maripaludis C6", "Methanococcus maripaludis C7", 
"Methanococcus maripaludis S2", "Methanococcus vannielii SB", 
"Methanococcus voltae A3", "Methanocorpusculum labreanum Z", 
"Methanoculleus marisnigri JR1", "Methanohalobium evestigatum Z-7303", 
"Methanohalophilus mahii DSM 5219", "Methanoplanus petrolearius DSM 11571", 
"Methanopyrus kandleri AV19", "Methanosaeta thermophila PT", 
"Methanosarcina acetivorans C2A", "Methanosarcina barkeri str. Fusaro", 
"Methanosarcina mazei Go1", "Methanosphaera stadtmanae DSM 3091", 
"Methanosphaerula palustris E1-9c", "Methanospirillum hungatei JF-1", 
"Methanothermobacter marburgensis str. Marburg", "Methanothermobacter thermautotrophicus str. Delta H", 
"Nanoarchaeum equitans Kin4-M", "Natrialba magadii ATCC 43099", 
"Natronomonas pharaonis DSM 2160", "Nitrosopumilus maritimus SCM1", 
"Picrophilus torridus DSM 9790", "Pyrobaculum aerophilum str. IM2", 
"Pyrobaculum arsenaticum DSM 13514", "Pyrobaculum calidifontis JCM 11548", 
"Pyrobaculum islandicum DSM 4184", "Pyrococcus abyssi GE5", "Pyrococcus furiosus DSM 3638", 
"Pyrococcus horikoshii OT3", "Staphylothermus hellenicus DSM 12710", 
"Staphylothermus marinus F1", "Sulfolobus acidocaldarius DSM 639", 
"Sulfolobus islandicus L.D.8.5", "Sulfolobus islandicus L.S.2.15", 
"Sulfolobus islandicus M.14.25", "Sulfolobus islandicus M.16.27", 
"Sulfolobus islandicus M.16.4", "Sulfolobus islandicus Y.G.57.14", 
"Sulfolobus islandicus Y.N.15.51", "Sulfolobus solfataricus P2", 
"Sulfolobus tokodaii str. 7", "Thermococcus gammatolerans EJ3", 
"Thermococcus kodakarensis KOD1", "Thermococcus onnurineus NA1", 
"Thermococcus sibiricus MM 739", "Thermofilum pendens Hrk 5", 
"Thermoplasma acidophilum DSM 1728", "Thermoplasma volcanium GSS1", 
"Thermoproteus neutrophilus V24Sta", "Thermosphaera aggregans DSM 11486", 
"Vulcanisaeta distributa DSM 14429", "uncultured methanogenic archaeon RC-I"
) 

Miałem podobne problemy. (widoczne tutaj: https://stackoverflow.com/questions/2231993/merging-two-data-frames-using-fuzzy-approximate-string-matching-in-r )

Większość zaleceń, które otrzymałem, dotyczyło:

pmatch()I agrep(), grep(), grepl()trzy funkcje, które, jeśli masz trochę czasu, aby przejrzeć zapewni Ci pewien wgląd przybliżonego dopasowywania strun albo przybliżonej sznurka lub przybliżonej regex.

Nie widząc ciągów, trudno jest podać twardy przykład tego, jak je dopasować. Jeśli możesz podać nam przykładowe dane, jestem pewien, że możemy znaleźć rozwiązanie.

Inną opcją, która według mnie działa dobrze, jest spłaszczenie ciągów, tolower()sprawdzenie pierwszej litery każdego słowa w ciągu, a następnie porównanie. Czasami działa to bez żadnych problemów. Są też bardziej skomplikowane rzeczy, takie jak odległości wymienione w innych odpowiedziach. Czasami te prace, czasem są okropne - to naprawdę zależy od strun.

Czy możemy je zobaczyć?

Aktualizacja

Wygląda na to, że agrep () załatwi sprawę w większości z nich. Zauważ, że agrep () jest po prostu implementacją odległości Levenshteina przez R.

agrep(vec55[1],vec91,value=T)

Niektóre nie obliczają, chociaż nie jestem nawet pewien, czy Ferroplasm acidaramus jest taki sam jak Ferroglobus placidus DSM 10642, na przykład:

agrep(vec55[7],vec91,value=T) 

Myślę, że możesz być trochę SOL dla niektórych z nich i być może stworzenie indeksu od zera jest najlepszym wyborem. to znaczy,. Utwórz tabelę z numerami identyfikacyjnymi dla vec55, a następnie ręcznie utwórz odwołanie do identyfikatorów w vec55 w vec91. Wiem, że bolesne, ale wiele z tego można zrobić za pomocą agrep ().

Istnieje wiele sposobów pomiaru odległości między dwoma łańcuchami. Dwa ważne (standardowe) podejścia szeroko stosowane w R to Levenshtein i dystans Hamminga. Pierwszy z nich jest dostępny w pakiecie „MiscPsycho”, a drugi w „e1071”. Korzystając z nich, po prostu obliczę macierz 92 na 55 odległości parami, a następnie przejdę od tego momentu (tzn. Najlepszym dopasowanym kandydatem dla ciągu „1” na liście 1 jest ciąg „x” z listy 2 o najmniejszej odległości do ciągu „1 „).

Alternatywnie istnieje funkcja Compare () w pakiecie RecordLinkage, która wydaje się być zaprojektowana do robienia tego, co chcesz i używa tak zwanej odległości Jaro-Winklera, która wydaje się bardziej odpowiednia do danego zadania, ale nie miałem z tym doświadczenia. .

EDYCJA: edytuję swoją odpowiedź, aby dołączyć komentarz Brandona, a także kod Tala, aby znaleźć dopasowanie do „Aeropyrum pernix”, pierwszego wpisu vec55 :

agrep(vec55[1],vec91,ignore.case=T,value=T,max.distance = 0.1, useBytes = FALSE)
[1] "Aeropyrum pernix K1"

Aby uzupełnić użyteczną odpowiedź Kwaka, pozwól mi dodać kilka prostych zasad i pomysłów. Dobrym sposobem na określenie metryki jest rozważenie, w jaki sposób łańcuchy mogą różnić się od celu. „Edytuj odległość” jest przydatna, gdy odmiana jest kombinacją błędów typograficznych, takich jak transpozycja sąsiadów lub błędne wpisanie pojedynczego klawisza.

Innym przydatnym podejściem (z nieco inną filozofią) jest mapowanie każdego łańcucha na jednego przedstawiciela klasy powiązanych łańcuchów. Metoda „ Soundex ” robi to: kod Soundex dla słowa jest sekwencją czterech znaków kodujących główną spółgłoskę i grupy o podobnie brzmiących konsekwencjach wewnętrznych. Jest używany, gdy słowa są fonetycznymi błędami ortograficznymi lub wariantami siebie. W przykładowej aplikacji można pobrać wszystkie słowa docelowe, których kod Soundex jest równy kodowi Soundex dla każdego słowa sondy. (W ten sposób można pobrać zero lub wiele celów).

Sugerowałbym również sprawdzenie N-gramów i odległości Damerau – Levenshtein, oprócz innych sugestii Kwaka.

Ten artykuł porównuje dokładność kilku różnych odległości edytowania wymienionych tutaj (i jest bardzo cytowany według Google Scholar).

Jak widać, istnieje wiele różnych sposobów podejścia do tego, a nawet można łączyć różne wskaźniki (artykuł, który podłączyłem do dyskusji na ten temat). Myślę, że Levenshtein i powiązane pomiary mają najbardziej intuicyjny sens, szczególnie jeśli wystąpią błędy z powodu pisania na klawiaturze. N-gramy są również proste i mają sens w przypadku danych, które nie są nazwami ani słowami na słowo.

Podczas gdy soundex jest opcją, trochę pracy, którą widziałem (co jest naprawdę niewielką ilością) soundex nie działa tak dobrze, jak Levenshstein lub inne odległości edycji dla pasujących nazw. A Soundex ogranicza się do fonetycznych fraz prawdopodobnie wprowadzanych przez ludzkie maszyny do pisania, gdzie jako Levenshtein i N-gram mają potencjalnie szerszy zakres (szczególnie N-gram, ale oczekiwałbym, że odległość Levenshteina będzie skuteczniejsza również w przypadku słów innych niż słowa).

Nie mogę pomóc, jeśli chodzi o pakiety, ale koncepcja N-gramów jest dość prosta (ostatnio zrobiłem makro SPSS, aby zrobić N-gramów, ale dla tak małego projektu po prostu poszedłbym z już wykonanymi pakietami w R inne plakaty sugerują). Oto przykład obliczania odległości Levenshteina w pythonie.

Przebadałem kilka pakietów i sposoby rozwiązania tego problemu i myślę, że najlepszym kandydatem jest fuzzywuzzyRpakiet.

Pakiet fuzzywuzzyR jest rozmytym ciągiem pasującym do implementacji pakietu fuzzywuzzy python. Wykorzystuje odległość Levenshteina do obliczania różnic między sekwencjami. Więcej szczegółów na temat funkcjonalności fuzzywuzzyR można znaleźć w blogu i paczce Winieta.

Zrobiłem proste rozwiązanie twojego problemu, ale jest mały haczyk. Musisz zainstalować Python, a jeśli używasz Winodows, musisz również zainstalować narzędzia do kompilacji dla Visual Studio . Musisz wybrać te:

• Windows 10 SDK 10.0.17763.0 i MSVC v140
• Narzędzia do budowania VS 2015 C ++ (wersja 14v00)

Rozwiązanie jest proste. Główna funkcja ExtractOnezwraca listę dwóch wartości. Pierwszy to dopasowanie jednego ciągu, a drugi to odpowiedni wynik (w zakresie 0–100). fuzzywuzzyRPakiet zawiera również inne funkcje, które mogą być użyteczne. Główna dokumentacja znajduje się tutaj . Mam nadzieję, że ten kod pomoże rozwiązać problem.

library(fuzzywuzzyR)

# The Fuzzy initialization
init_proc = FuzzUtils$new()
PROC = init_proc$Full_process # class process-method
PROC1 = tolower # base R function
init_scor = FuzzMatcher$new()
SCOR = init_scor$WRATIO    
init <- FuzzExtract$new()

match_strings <- function(vector_to_process, base_vector){  
  new_vec = c()
  for(i in 1:length(vector_to_process)){      
    new_word <- init$ExtractOne(string = vector_to_process[i], sequence_strings = base_vector, processor = PROC1, scorer = SCOR, score_cutoff = 0L)
    new_vec[i] <- new_word[[1]]
  }     
  return(new_vec)
}

# Check if all python modules are available
if (check_availability()){    
  new_vec <- match_strings(vec55, vec91)
  print(new_vec)   
}

Wydajność:

[1] "Aeropyrum pernix K1"                                 "Archaeoglobus fulgidus DSM 4304"                    
[3] "Candidatus Korarchaeum cryptofilum OPF8"             "Candidatus Methanoregula boonei 6A8"                
[5] "Cenarchaeum symbiosum A"                             "Desulfurococcus kamchatkensis 1221n"                
[7] "Thermoplasma volcanium GSS1"                         "Haloarcula marismortui ATCC 43049"                  
[9] "Halobacterium sp. NRC-1"                             "Halobacterium salinarum R1"                         
[11] "Haloferax volcanii DS2"                              "Haloquadratum walsbyi DSM 16790"                    
[13] "Hyperthermus butylicus DSM 5456"                     "Ignicoccus hospitalis KIN4/I"                       
[15] "Metallosphaera sedula DSM 5348"                      "Methanothermobacter thermautotrophicus str. Delta H"
[17] "Methanobrevibacter smithii ATCC 35061"               "Methanococcoides burtonii DSM 6242"       

Na podstawie funkcji adist

Oblicz przybliżoną odległość ciągu między wektorami znaków. Odległość jest uogólnioną odległością Levenshteina (edycja), dającą minimalną możliwą ważoną liczbę wstawek, usunięć i podstawień potrzebnych do przekształcenia jednego łańcucha w inny

Funkcja stringdistz pakietu o tej samej nazwie ma kilka metod (patrz ?stringdist):

method = c („osa”, „lv”, „dl”, „hamming”, „lcs”, „qgram”, „cosine”, „jaccard”, „jw”, „soundex”)

Dzięki temu możesz wybrać maksymalną dywergencję (próg):

firstvector<-vec55
secondvector<-vec91

match<-character()
threshold<-14 # max 14 characters of divergence
mindist<-integer()
sortedmatches<-character()

for (i in 1:length(firstvector) ) {
  matchdist<-adist(firstvector[i],secondvector)[1,]
  # matchdist<-stringdist(firstvector[i],secondvector) # several methods available

  matchdist<-ifelse(matchdist>threshold,NA,matchdist)
  sortedmatches[i]<-paste(secondvector[order(matchdist, na.last=NA)], collapse = ", ")
  mindist[i]<- tryCatch(ifelse(is.integer(which.min(matchdist)),matchdist[which.min(matchdist)],NA), error = function(e){NA})
  match[i]<-ifelse(length(secondvector[which.min(matchdist)])==0,NA,
                  secondvector[which.min(matchdist)] )
}
res<-data.frame(firstvector=firstvector,match=match,divergence=mindist, sortedmatches=sortedmatches, stringsAsFactors = F)
res

Ta ramka danych pokazuje pierwszy wektor w pierwszym wektorze kolumny, najlepsze dopasowanie drugiego wektory w dopasowaniu kolumny, jego odległość w rozbieżności kolumn i wszystkie znaczące dopasowania uporządkowane w dopasowanych kolumnach jak w OP.