R - Maior subcadeia comum

Question

Alguém sabe de um pacote de R que resolve a maior subcadeia comum problema?Eu estou procurando algo mais rápido que podia trabalhar em vetores.

Answer 1

Confira o pacote "Rlibstree" no Omegahat: http://www.omegahat.org/rlibstree/.

Isso usa http://www.icir.org/christian/libstree/.

Answer 2

Você deve olhar para o LCS função de qualV pacote. É implementado em C, portanto, bastante eficiente.

Answer 3

A questão aqui não é totalmente clara a intenção de aplicação da solução para a maior subcadeia comum problema.Uma aplicação comum de que eu encontro é a correspondência entre nomes em diferentes conjuntos de dados.O stringdist o pacote tem uma função útil amatch() o que eu acho adequado para esta tarefa.

Em breve, amatch() terá como entrada dois vetores, o primeiro é x o vetor de cadeias de caracteres que você deseja localizar correspondências (isso também pode ser apenas uma única cadeia de caracteres), o segundo é table, que é o vetor de cadeias de caracteres que você deseja fazer comparações e escolher o jogo com o maior subcadeia comum. amatch() então irá retornar um vetor cujo comprimento é igual ao x - cada elemento de este resultado será um índice em table que contém a melhor correspondência.

Detalhes: amatch() toma uma method argumento, o que você especificar para ser lcs se você deseja correspondência em maior subcadeia comum.Existem muitas outras opções para diferentes seqüência de técnicas de correspondência (por exemplo,A distância de Levenshtein).Há também um obrigatórios maxDist argumento.Se todas as seqüências de caracteres em table são maior "distância" de uma determinada seqüência de caracteres em x, e , em seguida, amatch() vai voltar NA para que o elemento de sua saída."a distância" é definido de forma diferente dependendo da seqüência algoritmo de correspondência que você escolher.Para lcs, ele (mais ou menos) significa apenas como diferentes (não casado) caracteres não são.Veja a documentação para detalhes.

Paralelização:outro recurso interessante do amatch() é que ele automaticamente irá colocar em paralelo a operação para você, tornando razoável palpites sobre os recursos do sistema para usar.Se você deseja ter mais controle sobre isso, você pode alternar a nthread argumento.

Exemplo de aplicação:

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')

Além disso, ao contrário de funções como LCS a partir de qualV, isso não vai considerar "subsequence" jogos que envolvem ignorando intermediário personagens, a fim de formar um jogo (como discutido aqui).Por exemplo, veja esta:

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

Não conheço R, mas eu costumava implementar o algoritmo de Hirschberg, que é rápido e não consome muito espaço.

Pelo que me lembro, são apenas 2 ou 3 denominadas funções curtas.

Aqui está um link:http://wordaligned.org/articles/longest-common-subsequence

Portanto, não hesite em implementá -lo em r, vale a pena o esforço, pois é um algoritmo muito interessante.