Mots clés correspondant hiérarchique à un document

Question

J'ai un arbre de mot-clé hiérarchique, représentée comme une liste de tuples où le premier argument est le « chemin » et le second est le mot-clé correspondant:

keys = [('0','key1'),('0,1','key2'),('0,1,12','key3'),('0,2','key4'),('0,2,30','key5')] 

Liste de connexion « chemins »et les documents correspondants (un doc peut avoir plus d'un « chemin »:

docs = [('0,1,12','doc1'),('0,2,30','doc1'),('0,1','doc2')] 

Je veux correspondre chaque document aux mots-clés et de produire un résultat comme celui-ci:

docdict={doc1:[('key1','key2','key3'),('key1','key4','key5')],doc2:[('key1','key2')]} 

Ma question est comment obtenir tout le mot-clé (parent) plus efficacement? Merci d'avance!

Answer 1

Une réponse plus lisible qui évoluera probablement mieux si vous en avez beaucoup.

docs = [('0,1,12','doc1'),('0,2,30','doc1'),('0,1','doc2')] 
keys = [('0','key1'),('0,1','key2'),('0,1,12','key3'),('0,2','key4'),('0,2,30','key5')] 

keydict = dict(keys) 
resultDict = {} 

for doc in docs: 
    (path, docname) = doc 
    pathList = path.split(',') 
    keyPath = [] 
    for i in range(0, len(pathList)): 
     aPath = ','.join(pathList[:i+1]) 
     keyPath.append(keydict[aPath]) 

    if docname not in resultDict : 
     resultDict[docname] = [] 
    resultDict[docname].append(tuple(keyPath)) 

print resultDict 

Answer 2

EDIT: J'ai d'abord créé une méthode pour obtenir le parent direct à partir d'un mot-clé, mais cela ne répond pas à l'exigence. D'après ce que je compris, obtenir tous les mots-clés parents d'un chemin est beaucoup mieux:

>>> def get_parents(keys, path): 
    """ Get all parent keywords """ 
    # Get parent path (remove after last ',') 
    parent_paths = [path] 
    while ',' in path: 
     path = ','.join(path.split(',')[:-1]) 
     parent_paths.append(path) 
    return [key for path, key in keys if path in parent_paths] 

>>> get_parents(keys, '0,2') 
['key1', 'key4'] 
>>> from collections import defaultdict 
>>> def create_doc_dict(keys, docs): 
    """ Create the required dict """ 
    docdict = defaultdict(list) 
    for path, doc in docs: 
     docdict[doc].append(get_parents(keys, path)) 
    return docdict 

>>> create_doc_dict(keys, docs) 
defaultdict(<type 'list'>, {'doc2': [['key1', 'key2']], 'doc1': [['key1', 'key2', 'key3'], ['key1', 'key4', 'key5']]}) 

Answer 3

Ce fait presque ce que vous voulez:

>>> docdict = {doc[-1]:[key[-1] for key in keys if doc[0].startswith(key[0])] for doc in docs} 
>>> docdict 
{'doc2': ['key1', 'key2'], 'doc1': ['key1', 'key4', 'key5']} 

ce qui fait exactement ce que vous avez spécifié:

>>> docdict = {} 
>>> for doc in docs: 
    docdict.setdefault(doc[-1],[]).append(tuple(key[-1] for key in keys if doc[0].startswith(key[0]))) 
>>> docdict 
{'doc2': [('key1', 'key2')], 'doc1': [('key1', 'key2', 'key3'), ('key1', 'key4', 'key5')]} 

les deux est O(n*m).

Answer 4

Ceci est également une autre solution:

keys = [('0','key1'),('0,1','key2'),('0,1,12','key3'),('0,2','key4'),('0,2,30','key5')] 
docs = [('0,1,12','doc1'),('0,2,30','doc1'),('0,1','doc2')] 

def get_path(p): 
    # tuples so that you can use them as dict keys 
    return tuple(p.split(',')) 

# we need to find the keys based on the paths, so make the path the dict's key 
keypaths = {get_path(p): key for p, key in keys} 

docdict = {} 
for p, doc in docs: 
    path = get_path(p) # we need the path as a tuple or list, so that you can get the parents via slicing 
    # get all parents of the path and the path itself. 
    # we remove one part of the path at a time and keep the original path also 
    all_paths = [path]+[path[:-i] for i in range(1,len(path))] 
    # you need to keep each doc/path combination alone, so you need a list to store it 
    if doc not in docdict: 
     docdict[doc] = [] 
    # add the keys whose path is in one of the parents or the path itself 
    docdict[doc].append([keypaths[path] for path in all_paths if path in keypaths]) 

print docdict # now, you see what you expect. :) 

Franchement, avec tous ces bons mots, le code devient illisible. Donc, si vous êtes d'accord, vous devriez aimer cette solution mieux.