R - Sottostringa comune più lunga
-
07-07-2019 - |
Domanda
Qualcuno conosce un pacchetto R che risolve il problema di sottostringa comune più lungo ? Sto cercando qualcosa di veloce che possa funzionare sui vettori.
Soluzione
Dai un'occhiata a " Rlibstree " pacchetto su omegahat: http://www.omegahat.org/Rlibstree/ .
Questo utilizza http://www.icir.org/christian/libstree/ .
Altri suggerimenti
Dovresti guardare la funzione LCS
del pacchetto qualV
. È implementato in C, quindi abbastanza efficiente.
La domanda qui non è completamente chiara sull'applicazione prevista della soluzione al problema di sottostringa comune più lungo. Un'applicazione comune che incontro è la corrispondenza tra nomi in set di dati diversi. Il pacchetto stringdist
ha un'utile funzione amatch ()
che trovo adatta a questo compito.
In breve , amatch ()
prenderà come input due vettori, il primo è x
il vettore di stringhe che si desidera trovare corrispondenze da (questa può anche essere solo una singola stringa), la seconda è table
, che è il vettore di stringhe con cui si desidera effettuare un confronto e scegliere la corrispondenza con la sottostringa comune più lunga. amatch ()
restituirà quindi un vettore la cui lunghezza è uguale a x
- ogni elemento di questo risultato sarà un indice nella tabella
che contiene il migliore corrispondenza.
Dettagli : amatch ()
accetta un argomento method
, che si specifica essere lcs
se si desidera corrispondenza sulla sottostringa comune più lunga. Esistono molte altre opzioni per diverse tecniche di abbinamento delle stringhe (ad es. Distanza di Levenshtein). C'è anche un argomento maxDist
obbligatorio. Se tutte le stringhe nella tabella
sono maggiori "distanza" da una determinata stringa in x
, quindi amatch ()
restituirà NA
per quell'elemento del suo output. & Quot; distanza " viene definito in modo diverso a seconda dell'algoritmo di corrispondenza delle stringhe scelto. Per lcs, significa (più o meno) quanti caratteri diversi (non corrispondenti) ci sono. Vedere la documentazione per i dettagli.
Parallelizzazione : un'altra bella caratteristica di amatch ()
è che parallelizzerà automaticamente l'operazione, facendo ipotesi ragionevoli sulle risorse di sistema da usare. Se vuoi un maggiore controllo su questo, puoi attivare l'argomento nthread
.
Applicazione di esempio :
library(stringdist)
Names1 = c(
"SILVER EAGLE REFINING, INC. (SW)",
"ANTELOPE REFINING",
"ANTELOPE REFINING (DOUGLAS FACILITY)"
)
Names2 = c(
"Mobile Concrete, Inc.",
"Antelope Refining, LLC. ",
"Silver Eagle Refining Inc."
)
Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)
Match_Idx
# [1] 3 2 2
Matches = data.frame(Names1, Names2[Match_Idx])
Matches
# Names1 Names2.Match_Idx.
# 1 silver eagle refining, inc. (sw) silver eagle refining inc.
# 2 antelope refining antelope refining, llc.
# 3 antelope refining (douglas facility) antelope refining, llc.
### Compare Matches:
Matches$Distance = stringdist(Matches$Names1, Matches$Match, method = 'lcs')
Inoltre, a differenza di funzioni come LCS
da qualV
, questo non prenderà in considerazione " sottosequenza " partite che comportano l'ignoranza di caratteri intermedi al fine di formare una corrispondenza (come discusso qui ). Ad esempio, vedi questo:
Names1 = c(
"hello"
)
Names2 = c(
"hel123l5678o",
"hell"
)
Match_Idx = amatch(tolower(Names1), tolower(Names2), method = 'lcs', maxDist = Inf)
Matches = data.frame(Names1, Match = Names2[Match_Idx])
Matches
# 1 hello hell
Non conosco R, ma implementavo l'algoritmo di Hirschberg che è veloce e non consuma troppo spazio.
Come ricordo, sono solo 2 o 3 chiamate brevi in ??modo ricorsivo.
Ecco un link: http://wordaligned.org/articles/longest-common-subsequence
Quindi non esitate a implementarlo in R, ne vale la pena poiché è un algoritmo molto interessante.