R - Sottostringa comune più lunga

Question

Qualcuno conosce un pacchetto R che risolve il problema di sottostringa comune più lungo ? Sto cercando qualcosa di veloce che possa funzionare sui vettori.

Answer 1

Dai un'occhiata a " Rlibstree " pacchetto su omegahat: http://www.omegahat.org/Rlibstree/ .

Questo utilizza http://www.icir.org/christian/libstree/ .

Answer 2

Dovresti guardare la funzione LCS del pacchetto qualV . È implementato in C, quindi abbastanza efficiente.

Answer 3

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

Answer 4

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.