Префикс-дерево для пар элементов - PullRequest
Новая
       15

Префикс-дерево для пар элементов

0 голосов
/ 12 июня 2018

У меня есть вложенный список: 

lists = [['a', 'b', 'c', 'd'],
         ['a', 'b', 'd', 'e'],
         ['a', 'b', 'd', 'f'],
         ['a', 'b', 'd', 'f', 'h', 'i']]

Я знаю, как построить простое префиксное дерево: 

tree = {}
end = "END"
for lst in lists:
    d = tree
    for x in lst:
        d = d.setdefault(x, {})
    d[end] = {}

Результат: 

>>> from pprint import pprint
>>> pprint(tree)
{'a': {'b': {'c': {'d': {'END': {}}},
             'd': {'e': {'END': {}},
                   'f': {'END': {}, 'h': {'i': {'END': {}}}}}}}}

СейчасЯ могу рекурсивно пройти по этому дереву, и всякий раз, когда у узла есть только один дочерний элемент (подчиненный элемент только с одним элементом), присоединяюсь к этим узлам. 

def join(d, pref=[]):
    if end in d:
        yield [' '.join(pref)] if pref else []
    for k, v in d.items():
        if len(v) == 1:
            for x in join(v, pref + [k]): # add node to prefix
                yield x                   # yield next segment
        else:
            for x in join(v, []):         # reset prefix
                yield [' '.join(pref + [k])] + x # yield node + prefix and next

Результат: 

>>> for x in join(tree):
...     print(x)
...
['a b', 'c d']
['a b', 'd', 'e']
['a b', 'd', 'f']
['a b', 'd', 'f', 'h i']

Мне нужен алгоритм, в котором только общие пары элементов становятся единым узлом дерева.В идеале минимальная длина узла = n1, максимальная длина узла = n2.Желаемый вывод: 

[['a b', 'c d'],
 ['a b', 'd e'],
 ['a b', 'd f'],
 ['a b', 'd f', 'h i']]

1 Ответ

0 голосов
/ 12 июня 2018

Просто чередуйте соединение и уступку: 

def paired(d, _prefix=None):
    if end in d:
        yield [_prefix] if _prefix else []
    for k, v in d.items():
        item = [f'{_prefix} {k}'] if _prefix else []
        for rest in paired(v, None if _prefix else k):
            yield item + rest

Таким образом, на каждом уровне, если установлено _prefix, создайте пару, в противном случае оставьте этот уровень «пустым» и вернитесь с текущим ключом в качествепрефикс.

Это дает ожидаемый результат: 

>>> for path in paired(tree):
...     print(path)
...
['a b', 'c d']
['a b', 'd e']
['a b', 'd f']
['a b', 'd f', 'h i']
...