Comment rechercher des sous-chaînes de manière récursive dans Python?

Question

nous vous remercions de votre aide à l'avance.

J'ai une liste de chaînes

full_name_list = ["hello all","cat for all","dog for all","cat dog","hello cat","cat hello"] 

je dois faire un match pour cent entre chaque élément à tous les éléments de la liste. Par exemple, je dois d'abord décomposer "hello all" en ["hello", "all"] et je peux voir que "hello" est en "hello cat" donc ce serait une correspondance de 50%. Voici ce que j'ai jusqu'à présent,

hello all [u'hello', u'hello all', u'hello cat', u'cat hello'] [u'all', u'hello all', u'cat for all', u'dog for all'] 
    cat for all [u'cat', u'cat for all', u'cat dog', u'hello cat', u'cat hello'] [u'for', u'cat for all', u'dog for all'] [u'all', u'hello all', u'cat for all', u'dog for all'] 
    dog for all [u'dog', u'dog for all', u'cat dog'] [u'for', u'cat for all', u'dog for all'] [u'all', u'hello all', u'cat for all', u'dog for all'] 
    cat dog  [u'cat', u'cat for all', u'cat dog', u'hello cat', u'cat hello'] [u'dog', u'dog for all', u'cat dog']  
    hello cat [u'hello', u'hello all', u'hello cat', u'cat hello'] [u'cat', u'cat for all', u'cat dog', u'hello cat', u'cat hello']  
    cat hello [u'cat', u'cat for all', u'cat dog', u'hello cat', u'cat hello'] [u'hello', u'hello all', u'hello cat', u'cat hello']  

Comme vous pouvez le voir le premier mot de chaque sous-liste contient la sous-chaîne qui est en cours de recherche suivi par les éléments qui contiennent cette sous-chaîne. Je suis capable de faire cela pour des correspondances d'un mot, et j'ai réalisé que je peux continuer ce processus en prenant simplement l'intersection entre des mots individuels pour obtenir des correspondances doubles, par ex.

cat for all [(cat,for) [u'cat for all']] [(for,all) [u'cat for all', u'dog for all']] 

Le problème que j'ai est de le faire récursivement puisque je ne sais pas combien de temps ma chaîne la plus longue va être. Aussi, y a-t-il une meilleure façon de faire cette recherche de chaîne? En fin de compte, je veux trouver les chaînes qui correspondent à 100% parce que de façon réaliste "hello cat" == "cat hello". Je veux aussi trouver les 50% et ainsi de suite.

Une idée m'a été donnée en utilisant un arbre binaire, mais comment puis-je faire ça en python? Voici mon code à ce jour, je ne suis pas un programmeur et je sais que cela ne regarde pas si bon si nu avec moi:

logical_list = [] 
logical_list_2 = [] 
logical_list_3 = [] 
logical_list_4 = [] 
match_1 = [] 
match_2 = [] 
i = 0 

logical_name_full = logical_df['Logical'].tolist() 
for x in logical_name_full: 
    logical_sublist = [x]+x.split() 
    logical_list.append(logical_sublist) 



for sublist in logical_list: 
    logical_list_2.append(sublist[0]) 
    for split_words in sublist[1:]: 
     match_1.append(split_words) 
     for logical_names in logical_name_full: 
      if split_words in logical_names: 
       match_1.append(logical_names) 
     logical_list_2.append(match_1) 
     match_1 = [] 
    logical_list_3.append(logical_list_2) 
    logical_list_2 = [] 

Answer 1

Si je comprends bien la question correctement, vous avez une liste de chaînes, et vous voulez trouver le% correspondant d'un mot dans cette chaîne, le pourcentage étant déterminé par combien de mots de la chaîne, à partir du nombre total de mots, est ledit mot. Si oui, cet exemple de code devrait être suffisant:

for i in full_name_list: 
    if word in i.split(" "): 
     total_words = len(i.split(" ")) 
     match_words = 0 
     for w in i.split(" "): 
      if word == w: 
       match_words += 1 
     print(i + " Word match: " + str((match_words/total_words)*100) + "%") 

Pour correspondance avec des chaînes à plusieurs mots, où l'ordre des mots dans la chaîne trouvée est pas important: mot = « chaîne de test » full_name_list = [ "quelque chose de test », "chaîne de test quelque chose", "chaîne de test", "test de chaîne", "chaîne quelque chose test"] résultats = []

for i in full_name_list: 
    if len([item for item in word if item in i]) > 0: 
     total_words = len(i.split(" ")) 
     match_words = 0.0 
     for single_word in word.split(" "): 
      for w in i.split(" "): 
       if single_word == w: 
        match_words += 1 
     results.append(i + "," + str((match_words/total_words)*100) + "%") 

with open("file.csv", "w") as f: 
    for i in results: 
     f.write(i+"\n") 

Answer 2

Je pense que je sais ce que vous demandez (sinon, juste commenter ma réponse, je vais essayer d'aider). J'ai écrit un petit programme qui fait ce que je pense que vous demandez:

full_name_list = ["hello all","cat for all","dog for all","cat dog","hello cat","cat hello"] 

for i in range(len(full_name_list)): 
    full_name_list[i] = full_name_list[i].split(' ') 

def match(i, j): 
    word = full_name_list[i][j] 

    for fullname in full_name_list: 
     if full_name_list.index(fullname) == i: continue 

     for name in fullname: 
      if word == name: 
       fullname_str = fullname[0] 

       for i in range(1,len(fullname)): 
        fullname_str += ' ' + fullname[i] 

       return '"{}" is a {}% match to "{}"'.format(name, int(100/len(fullname)), fullname_str) 

print(match(0,1)) 

entrée Vous deux paramètres, i pour l'indice du nom dans la liste, et j pour l'indice du nom dans le fullname . Il renvoie ensuite la chaîne à laquelle la fonction correspond le nom, et à quel point il correspond. Cela évite également de faire correspondre le mot à lui-même. J'ai couru la fonction une fois en bas. Il trouve une correspondance du mot all comme dans hello all, et réussit.

Encore une fois, s'il vous plaît dites-moi si je n'ai pas bien répondu. Il ne renvoie que le premier résultat trouvé, mais il peut être facilement modifié pour les renvoyer tous.

Answer 3

J'ai apporté les modifications que vous avez demandées. Juste pour que vous sachiez, j'ai utilisé une fonction de sous-ensemble que j'ai obtenu de here, et il importe de itertools (qui est construit avec python). Si c'est un problème, informez-moi.

Voici le nouveau code. Je l'ai couru en bas juste pour que vous puissiez voir ce que c'est en action. Vous entrez un index i dans la fonction matches, où i est l'index du nom dans full_name_list. Je crois que c'est tout ce que vous avez demandé.

from itertools import chain, combinations 

full_name_list = ["hello all","cat for all","dog for all","cat dog","hello cat","cat hello"] 

for i in range(len(full_name_list)): 
    full_name_list[i] = full_name_list[i].split(' ') 

def powerset(iterable): 
    s = list(iterable) 
    return list(chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))) 


def subset(string, container): 
    if string not in powerset(container): return False 

    return True 

def makestring(names): 
    fullname_str = names[0] 

    for i in range(1,len(names)): 
     fullname_str += ' ' + names[i] 

    return fullname_str 

def matches(i): 
    results = [] 

    fullname = full_name_list[i] 
    fullnamePS = powerset(fullname) 

    for fullname in full_name_list: 
     if full_name_list.index(fullname) == i: continue 

     for names in fullnamePS: 
      if subset(names, fullname): 

       results.append((int(100 * len(names)/len(fullname)), makestring(names), makestring(fullname))) 

    return results 

for result in matches(1): 
    print('"{}" is a {}% match to "{}"'.format(result[1],result[0],result[2]))