8
votes

R - la plus longue sous-chaîne commune

Est-ce que quelqu'un connaît-il d'un package R qui résout Le plus long problème de substration commun ? Je cherche quelque chose de rapide qui pourrait travailler sur des vecteurs.

string r substring longest-substring

0 commentaires

4 Réponses :

5
votes

Consultez le "rlibstree" package sur omégahat github

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

2 commentaires

Pouvez-vous poster des exemples de code du résultat de la comparaison de 'Hello World' et 'Hella Old' ? Produit-t-il 'enfer' ou 'enfer vieux' ?


                                                
                                                                                            
                                                    Le premier lien est cassé


                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     Je ne sais pas r, mais j'avais l'habitude de mettre en œuvre l'algorithme de Hirschberg qui est rapide et ne consommant pas trop d'espace. 

 Comme je me souviens que c'est seulement 2 ou 3 appelé de courtes fonctions courtes. 

 Voici un lien:
 http://wordaligned.org/articles/longest-commmon-subence  

 N'hésitez pas à la mettre en œuvre dans R, cela vaut l'effort puisqu'il s'agit d'un algorithme très intéressant.                                 

                                                                    
                                    
                                    
                                        1 commentaires
                                        
                                                                                            
                                                    Mais Vereb, c'est-à-dire l'algorithme de recherche courante le plus long? La recherche suivante est différente de la sous-chaîne, non? Comme demandé ici:  Stackoverflow.com/q/28261825/1175496                                                 
                                                
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Vous devez regarder la fonction  LCS  de  Qualv . Il est mis en œuvre C, donc assez efficace.                                 


                                                                    
                                    
                                    
                                        1 commentaires
                                        
                                                                                            
                                                    Remarque: cette fonction trouvera la recherche courante la plus longue (dans le sens mathématique de la séquence), pas la sous-chaîne. Ainsi, par exemple Il ignorera les personnages au milieu des cordes pour trouver des matchs entre eux. Pour plus de détails, voir ici:  Stackoverflow.com/questions/28261825/...                                                 
                                                
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     La question ici n'est pas totalement claire sur l'application envisagée de la solution au plus long problème de sous-chaîne commun. Une application commune que je rencontre correspond à des noms de différents ensembles de données. Le package  stringdist  CODE> a une fonction utile  amorque ()  code> que je trouve approprié pour cette tâche. 
  en bref  strong>,  amorque ( )  code> prendra en entrée deux vecteurs, le premier est  x  code> le vecteur des chaînes que vous souhaitez trouver des correspondances (ceci peut aussi simplement être une seule chaîne), le second est  Table  Code>, qui est le vecteur des chaînes que vous souhaitez faire des comparaisons et choisir le match avec la plus longue sous-chaîne commune.  amorch ()  code> retournera ensuite un vecteur dont la longueur est égale à celle de  x  code> - chaque élément de ce résultat sera un index dans la table   code> qui contient le meilleure correspondance.  p> 
  Détails  strud>:  Amatch ()  code> prend une méthode  code> argument  code>, que vous spécifiez être  LCS  code> si vous souhaitez correspondre 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 par E. Levenshtein). Il existe également un argument obligatoire  maxdiste  code>. Si toutes les chaînes de  Table  code> sont plus grandes "distance" d'une chaîne donnée dans  x  code>, alors  amorch ()  code> retournera  na  code> pour cet élément de sa sortie. "Distance" est défini différemment en fonction de l'algorithme de correspondance de chaîne que vous choisissez. Pour LCS, il (plus ou moins) signifie simplement combien il y a de caractères différents (non correspondants). Voir la documentation pour plus de détails.  P> 
  parallélisation  strong>: une autre caractéristique intéressante de  Amatch ()  code> est-ce qu'il mettra automatiquement la mise en place de l'opération pour vous, faisant des suppositions raisonnables sur ressources système à utiliser. Si vous souhaitez plus de contrôle sur ceci, vous pouvez basculer l'argument  NTthread  code>.  P> 
  Exemple d'application  forte>:  p> 
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

                                

                                                                    
                                    
                                    
                                        0 commentaires