"Tags". Wie kann man rekursiv Tag-Gruppen erzeugen?

lightos · Donnerstag 25. April 2013, 21:10

import sys

class TagIndexer(object):
    """
    class to help to organize list of comma separated tags


    """

    def __init__(self):
        self.__tagDic = {}
        self.__groups = {}
    def add(self, key, taglist):
        """add new entry to list: key is a string, taglist contains all tags as comma separated list"""
        tags = taglist.split(',')
        for t in tags:
            try:
                tmp = self.__tagDic[t]
                self.__tagDic[t]['keys'].append(key)
            except:
                if (t != ''):
                    self.__tagDic[t] = {}
                    self.__tagDic[t]['keys'] = []
                    self.__tagDic[t]['keys'].append(key)
    
    def update_groups(self):
        """ Update Reverse Dictionary to get tag-groups by key"""
        max = 0
        maxtag = ''
        keylist = []
        for t in self.__tagDic.items():
            print(t)
            keylist.append(t[1]['keys'])
        
        """
        Missing code to create self.__groups in the following way (based on current static input in main)
        Ethernet: A,C,E,F,G
        USB: F,G
        Ethernet,USB: F,G
        Ethernet,MOST: C,E,F
        ...
        """
        self.__groups['Ethernet']=['A','C','E','F','G'] # static code for demo
        self.__groups['Ethernet,USB']=['F','G'] # static code for demo (example only!)
    @property
    def MaxTag(self):
        """Return tag with maximum occurance"""
        max = 0
        maxtag = ''
        for t in self.__tagDic:
            c = self.__tagDic[t]['count']
            if c > max:
                max = c
                maxtag = t
        return((max, maxtag))

    def dump(self):
        print('--- Dump Tags Start ---')
        for t in self.__tagDic:
            print('Tag: ', t)
            print('   Keys: ', self.__tagDic[t]['keys'])
        print('--- Dump Tags End  ---')
        print('--- Dump Groups Start ---')
        for g in self.__groups:
            print('Group: ', g, self.__groups[g])
        print('--- Dump Groups End ---')


def main(args):
    ti = TagIndexer()
    ti.add('A', 'Ethernet')
    ti.add('B', 'MOST')
    ti.add('C', 'Ethernet,MOST')
    ti.add('D', 'CAN,MOST')
    ti.add('E', 'Ethernet,MOST,CAN')
    ti.add('F', 'Ethernet,MOST,USB')
    ti.add('G', 'Ethernet,USB')
    ti.dump()
    ti.update_groups()
    ti.dump()

if __name__ == '__main__':
    main(sys.argv)

Sirius3 · Donnerstag 25. April 2013, 21:38

Was meinst Du mit rekursiv?

Code: Alles auswählen

import collections

class TagIndexer(object):
    """
    class to help to organize list of comma separated tags
    """

    def __init__(self):
        self._tag2key = collections.defaultdict(list)
        self._key2tag = collections.defaultdict(list)
        
    def add(self, key, tags):
        """add new entry to list: key is a string, tags are the tags"""
        tags = tags.split(',')
        for t in tags:
            self._tag2key[t].append(key)
        self._key2tag[key].extend(tags)

    @property
    def max_tag(self):
        """Return tag with maximum occurance"""
        return max(self._tag2key.iteritems(), key=lambda item: len(item[1]))

    def dump(self):
        print('--- Dump Tags Start ---')
        for tag, keys in self._tag2key.iteritems():
            print('Tag: ', tag)
            print('   Keys: ', keys)
        print('--- Dump Tags End  ---')
        print('--- Dump Groups Start ---')
        for group, tags in self._key2tag.iteritems():
            print('Group: ', group, tags)
        print('--- Dump Groups End ---')


def main():
    ti = TagIndexer()
    ti.add('A', 'Ethernet')
    ti.add('B', 'MOST')
    ti.add('C', 'Ethernet,MOST')
    ti.add('D', 'CAN,MOST')
    ti.add('E', 'Ethernet,MOST,CAN')
    ti.add('F', 'Ethernet,MOST,USB')
    ti.add('G', 'Ethernet,USB')
    ti.dump()
    print ti.max_tag

if __name__ == '__main__':
    main()

lightos · Montag 29. April 2013, 08:47

Nun ja.

Alle möglichen Gruppen (also wohl eher Permutationen). Das läuft ja meistens auf einen rekursiven Ansatz raus.

Ich verwende Python 3 und kann den Vorschlag so leider nicht testen (iteritems() gibts nicht mehr).

Wie würde man das mit Python3 umsetzen?

/me · Montag 29. April 2013, 09:44

lightos hat geschrieben:Ich verwende Python 3 und kann den Vorschlag so leider nicht testen (iteritems() gibts nicht mehr).

iteritems ist jetzt einfach items.

lightos · Dienstag 7. Mai 2013, 13:09

Der indirekte Tipp mit den collections von Sirius3 hat mir geholfen.
Mit "set" bekomme ich nun, was ich wollte.
Die groups enthalten nun wie gewünscht die "virtuellen" Tag-Gruppen.

Als nächstes fehlt nur noch die Sortierung nach der 'Mächtigkeit' (Anzahl der Tags in jeder Gruppe).

Code: Alles auswählen

import sys
import collections

class TagIndexer(object):
    """
    class to help to organize list of comma separated tags
    simple dictionary to organize key <-> tag-list pairs
    with auto-groups on tags
    """

    def __init__(self):
        self.__tag2key=collections.defaultdict(list)
        self.__key2tag=collections.defaultdict(list)
        self.__groups=collections.defaultdict(set)
    def add(self, key, taglist):
        """add new entry to list: key is a string, taglist contains all tags as comma separated list"""
        tags = taglist.split(',')
        for t in tags:
            self.__tag2key[t.strip()].append(key.strip())
            self.__key2tag[key.strip()].append(t.strip())
    def delete(self, key):
        pass

    def set2key(self, setaslist):
        s=''
        for item in setaslist:
            if (len(s) > 0):
                s = s + ',' + item
            else:
                s = item
        return(s)
    
    def update_groups(self):
        """ Update Reverse Dictionary to get tag-groups by key"""
        for k in self.__key2tag:
            for k2 in self.__key2tag:
                if (k != k2):
                    set1=set(self.__key2tag[k])
                    set2=set(self.__key2tag[k2])
                    interset=set1.intersection(set2)
                    #print('Intersection:', interset)
                    #verify if at least 2 tags are identical
                    if (len(interset) > 0):
                        gn = self.set2key(sorted(list(interset)))
                        self.__groups[gn].add(k)
        
    @property
    def MaxTag(self):
        """Return tag with maximum occurance"""
        max = 0
        for g in self.__groups:
            if (len(self.__groups[g]) > max):
                max = len(self.__groups[g])
                group = g
        return(max)

    def dump(self):
        print('--- Dump Keys Start ---')
        for k in self.__key2tag:
            print('Key: ', k)
            print('   Keys: ', self.__key2tag[k])
        print('--- Dump Keys End  ---')

        print('--- Dump Tags Start ---')
        for t in self.__tag2key:
            print('Tag: ', t)
            print('   Keys: ', self.__tag2key[t])
        print('--- Dump Tags End  ---')
        print('--- Dump Groups Start ---')
        for g in self.__groups:
            print('Group: <', g, '>', self.__groups[g])
        print('--- Dump Groups End ---')


def main(args):
    ti = TagIndexer()
    ti.add('A_E', 'Ethernet')
    ti.add('B_M', 'MOST')
    ti.add('C_EM', 'Ethernet,MOST')
    ti.add('D_CM', 'CAN,MOST')
    ti.add('E_CEM', 'Ethernet,MOST,CAN')
    ti.add('F_EMU', 'Ethernet,MOST,USB')
    ti.add('G_EU', 'Ethernet,USB')
    ti.update_groups()
    ti.dump()
    print('Max: ', ti.MaxTag)

if __name__ == '__main__':
    main(sys.argv)

BlackJack · Dienstag 7. Mai 2013, 14:35

@lightos: Ein paar Anmerkungen zum Quelltext:

Quelltextformarierung und Namenskonvention weicht teilweise vom Style Guide for Python Code ab.

Doppelte führende Unterstriche braucht man nur sehr selten, nämlich dann wenn man Namenskollisionen bei tiefen Vererbungshierarchien oder Mehrfachvererbung vermeiden möchte. Um ein Attribut als Implementierungsdetail zu kennzeichnen wird ein führender Unterstrich verwendet. Die ersten beiden Namen sollten nach dem `2` auch die Mehrzahl benennen, denn es sind ja keine Einzelwerte sondern jeweils Listen auf dort abgebildet wird.

Namen sollten dem Leser verraten was der Wert im Kontext des Programms bedeutet. Dazu muss ein Name in der Regel länger als ein oder zwei Zeichen sein.

Bei ``if``-Abfragen sind Klammern um die gesamte Bedingung unnötig.

``return`` ist keine Funktion, also es sind weder Klammern nötig, noch sollte man den Rückgabewert ohne Leerzeichen direkt an das Schlüsselwort dran klatschen.

`set2key()` erfindet die `join()`-Methode auf Zeichenketten neu. Und die ”Methode” hätte auf der Klasse eigentlich auch nichts verloren gehabt, weil es eigentlich eine Funktion ist, und dazu noch eine ziemlich generische.

Wenn man in einer Schleife über die Schlüssel eines Wörterbuchs in der Schleife auch den Wert zum Schlüssel holt, kann man auch gleich über Schlüssel *und* Wert iterieren.

`interset` könnte besser benannt werden. Zum Beispiel `common_tags`.

`sorted()` nimmt jedes iterierbares Objekt als Argument, nicht nur Listen. Das `set` erst in eine Liste umzuwandeln ist also unnötig.

Beim `MaxTag` wurde wieder eine Funktion neu erfunden. Wie man am Syntax-Highlighting sehen kann, ist `max` ein Name den es schon als eingebaute Funktion gibt. Die Dokumentation ist dort auch irreführend. Es wird eine (An)Zahl zurückgegeben, der Docstring behauptet aber es würde ein Tag zurückgegeben.

Dann lande ich bei (ungetestet):

Code: Alles auswählen

import collections


class TagIndexer(object):
    """
    class to help to organize list of comma separated tags
    simple dictionary to organize key <-> tag-list pairs
    with auto-groups on tags
    """
    def __init__(self):
        self._tag2keys = collections.defaultdict(list)
        self._key2tags = collections.defaultdict(list)
        self._groups = collections.defaultdict(set)

    def add(self, key, tags):
        """add new entry to list: key is a string, tags contains all tags as
        comma separated list
        """
        key = key.strip()
        for tag in tags.split(','):
            tag = tag.strip()
            self._tag2keys[tag].append(key)
            self._key2tags[key].append(tag)
    
    def update_groups(self):
        """Update Reverse Dictionary to get tag-groups by key."""
        for key_a, tags_a in self._key2tags.items():
            for key_b, tags_b in self._key2tags.items():
                if key_a != key_b:
                    common_tags = set(tags_a) | set(tags_b)
                    if common_tags:
                        group_name = ','.join(sorted(common_tags))
                        self._groups[group_name].add(key_a)

    @property
    def max_tag(self):
        return max(len(v) for v in self._groups.values())

    def dump(self):
        print('--- Dump Keys Start ---')
        for key, tags in self._key2tags:
            print('Key: ', key)
            print('   Tags: ', tags)
        print('--- Dump Keys End  ---')

        print('--- Dump Tags Start ---')
        for tag, keys in self._tag2keys:
            print('Tag: ', tag)
            print('   Keys: ', keys)
        print('--- Dump Tags End  ---')

        print('--- Dump Groups Start ---')
        for group_key, group_values in self._groups:
            print('Group: <', group_key, '>', group_values)
        print('--- Dump Groups End ---')


def main():
    tag_indexer = TagIndexer()
    for key, tags in [
        ('A_E', 'Ethernet'),
        ('B_M', 'MOST'),
        ('C_EM', 'Ethernet,MOST'),
        ('D_CM', 'CAN,MOST'),
        ('E_CEM', 'Ethernet,MOST,CAN'),
        ('F_EMU', 'Ethernet,MOST,USB'),
    ]:
        tag_indexer.add(key, tags)
    tag_indexer.update_groups()
    tag_indexer.dump()
    print('Max: ', tag_indexer.max_tag)


if __name__ == '__main__':
    main()

lightos · Freitag 10. Mai 2013, 17:01

OK. Danke für die guten Hinweise für einen Python-Anfänger.
Die korrekte Lösung (mit 3.3.1 getestet) muss aber so aussehen:
Wichtig: Die Intersection ist '&'. Damit stimmt nun auch der Output.

Code: Alles auswählen

import collections


class TagIndexer(object):
    """
    class to help to organize list of comma separated tags
    simple dictionary to organize key <-> tag-list pairs
    with auto-groups on tags
    """
    def __init__(self):
        self._tag2keys = collections.defaultdict(list)
        self._key2tags = collections.defaultdict(list)
        self._groups = collections.defaultdict(set)

    def add(self, key, tags):
        """add new entry to list: key is a string, tags contains all tags as
        comma separated list
        """
        key = key.strip()
        for tag in tags.split(','):
            tag = tag.strip()
            self._tag2keys[tag].append(key)
            self._key2tags[key].append(tag)
   
    def update_groups(self):
        """Update Reverse Dictionary to get tag-groups by key."""
        for key_a, tags_a in self._key2tags.items():
            for key_b, tags_b in self._key2tags.items():
                if key_a != key_b:
                    common_tags = set(tags_a) & set(tags_b)
                    if common_tags:
                        group_name = ','.join(sorted(common_tags))
                        self._groups[group_name].add(key_a)

    @property
    def max_tag(self):
        return max(len(v) for v in self._groups.values())

    def dump(self):
        print('--- Dump Keys Start ---')
        for key, tags in self._key2tags.items():
            print('Key: ', key)
            print('   Tags: ', tags)
        print('--- Dump Keys End  ---')

        print('--- Dump Tags Start ---')
        for tag, keys in self._tag2keys.items():
            print('Tag: ', tag)
            print('   Keys: ', keys)
        print('--- Dump Tags End  ---')

        print('--- Dump Groups Start ---')
        for group_key, group_values in self._groups.items():
            print('Group: <', group_key, '>', group_values)
        print('--- Dump Groups End ---')


def main():
    tag_indexer = TagIndexer()
    for key, tags in [
        ('A_E', 'Ethernet'),
        ('B_M', 'MOST'),
        ('C_EM', 'Ethernet,MOST'),
        ('D_CM', 'CAN,MOST'),
        ('E_CEM', 'Ethernet,MOST,CAN'),
        ('F_EMU', 'Ethernet,MOST,USB'),
    ]:
        tag_indexer.add(key, tags)
    tag_indexer.update_groups()
    tag_indexer.dump()
    print('Max: ', tag_indexer.max_tag)


if __name__ == '__main__':
    main()