R - La plus longue sous-chaîne commune

Question

Est-ce que quelqu'un connaît un package R qui résout le le plus long problème de sous-chaîne commun ? Je cherche quelque chose de rapide qui pourrait fonctionner sur les vecteurs.

Answer 1

Découvrez le " Rlibstree " package sur omégahat: http://www.omegahat.org/Rlibstree/ .

Ceci utilise http://www.icir.org/christian/libstree/ .

Answer 2

Vous devriez regarder la fonction LCS du paquetage qualV . C-implémenté, donc très efficace.

Answer 3

La question ici n’est pas tout à fait claire sur l’application envisagée de la solution au plus long problème de sous-chaîne commune. Une application courante que je rencontre est la correspondance entre les noms de différents jeux de données. Le package stringdist a une fonction utile amatch () qui, à mon avis, convient à cette tâche.

En bref , amatch () prendra en entrée deux vecteurs, le premier est x le vecteur de chaînes que vous souhaitez rechercher. correspond à (cela peut aussi être juste une seule chaîne), la deuxième est table , qui est le vecteur des chaînes que vous souhaitez comparer et choisir la correspondance avec la plus longue sous-chaîne commune. amatch () renverra alors un vecteur de longueur égale à celle de x - chaque élément de ce résultat sera un index de la table qui contient le meilleur match.

Détails : amatch () prend un argument de la méthode , que vous spécifiez comme lcs si vous le souhaitez. correspondance sur la plus longue sous-chaîne commune. Il existe de nombreuses autres options pour différentes techniques de correspondance de chaînes (par exemple, la distance de Levenshtein). Il existe également un argument obligatoire maxDist . Si toutes les chaînes de la table sont plus grandes, " distance " à partir d'une chaîne donnée dans x , puis amatch () renverra NA pour cet élément de sa sortie. " distance " est défini différemment en fonction de l'algorithme de correspondance de chaîne choisi. Pour les Lcs, cela signifie (plus ou moins) simplement combien de caractères différents (non appariés) il y a. Voir la documentation pour plus de détails.

Parallélisation : une autre fonctionnalité intéressante de amatch () est la parallélisation automatique de l'opération pour vous, ce qui permet de deviner de manière raisonnable les ressources système à utiliser. Si vous souhaitez davantage de contrôle sur cela, vous pouvez basculer l’argument nthread .

Exemple d'application :

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

De même, contrairement aux fonctions telles que LCS de qualV , ceci ne prendra pas en compte la "sous-séquence". correspondances qui impliquent d'ignorer les caractères intermédiaires afin de former une correspondance (comme indiqué ici ). Par exemple, voir ceci:

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

Je ne connais pas R, mais j'avais l'habitude de mettre en oeuvre l'algorithme de Hirschberg qui est rapide et ne consomme pas trop d'espace.

Si je me souviens bien, seules 2 ou 3 fonctions récursives sont appelées fonctions courtes.

Voici un lien: http://wordaligned.org/articles/longest-common-subsequence

Alors n'hésitez pas à l'implémenter dans R, cela en vaut la peine car c'est un algorithme très intéressant.