Запись вложенного словаря (леса) огромной глубины в текстовый файл в стиле BFS

Question

Продолжение моего старого вопроса: Запись вложенного словаря (леса) огромной глубины в текстовый файл

Теперь я хочу написать прохождение леса в стиле BFS: У меня есть огромный словарь глубины, который представляет лес (много недвоичных деревьев), который я хочу обработать в лесу и создать текстовый файл с последовательностями отношений (папа, сын) из леса, т.е. с учетом словаря:

{'a': {'b': {'c': {'x': {}}, 'd': {'p': {}}}, 'g': {}, 'f': {}},
 't': {'r': {'o': {}}, 'y': {}}}

сгенерированный текстовый файл будет выглядеть так:

(ROOT,b) (ROOT,g) (ROOT,f) (b,c) (b,d) (c,x) (d,p) \n
(ROOT,r) (ROOT,y) (r,o) \n

Обратите внимание, что я заменяю все корни в лесу словом "ROOT".

Вот простая визуализация леса:

Вложенный словарь большой, и его рекурсивное повторение приводит к ошибке времени выполнения памяти, поэтому лучшим решением будет решение «Стиль генератора», как в ссылке в начале этого вопроса.

Answer 1

Чтобы выполнить поиск в ширину , мы должны хранить список текущих рабочих узлов и деревьев под ними - я решил сохранить их в кортеже.

Например, когда мы работаем на глубине узлов c и d, этот список деревьев будет:

[('c': {'x': {}}), ('d': {'p': {}})]

Теперь , в то время как под нами все еще есть деревья (while len(trees):), нам нужно спуститься к слою ниже в нашем дереве.

Первый шаг, очевидно, состоит в том, чтобы сбросить список trees, так как мы будем генерировать следующий слой.

Затем мы перебираем наш список деревьев и для каждого дерева мы перебираем его дочерние элементы.

Итак, в приведенном выше примере на первой итерации узел будет 'c', а дочерние элементы будут: {'x': {}}, и теперь мы хотим перебрать дочерние элементы. Таким образом, на первой итерации этого дочернего цикла первый дочерний узел будет 'x', а его дочерние элементы (дочерние элементы c) будут пустыми: {}.

Теперь, в этой области (дочернем узле), если у дочернего элемента есть дочерние элементы, мы хотим добавить дочерний элемент и его дочерние элементы (опять же, как кортеж) в список деревьев.

Так, чтобы привести пример, где есть дочерние элементы, когда текущий узел равен b, то один из его дочерних элементов равен c, а поскольку у c есть дочерние элементы, кортеж (c, * 1033) * 's children) добавляется в список деревьев для следующего слоя.

Наконец, независимо от того, были ли у этого ребенка дети или нет, мы хотим, чтобы в текущей строке файла была связь между нами и ними. Это (node, child_node).

И это почти все. Конечно, когда мы заканчиваем целое дерево, нам нужно записать новую строку в файл.

Единственная досадная деталь - проблема пробелов между кортежами, записанными в файл. Если бы мы всегда объединяли пробел в конце каждого кортежа, в конце каждой строки мы могли бы получить паразитный пробел, как показано ниже, что не идеально.

(ROOT, a)S(a,b)S

(где S представляет пробел)

Таким образом, чтобы выкупить это, мы всегда будем объединять пробел перед каждым кортежем, пока мы не первые в новой строке (line_first). Чтобы это работало, в начале каждого дерева (строки) мы устанавливаем флаг line_first на True, но затем в коде мы сразу устанавливаем его на False на первой итерации (но пропускаем запись пробел), иначе (будущие кортежи) мы пишем пробел раньше.

И это все. Вот полный код:

the_tree = {'a': {'b': {'c': {'x': {}}, 'd': {'p': {}}}, 'g': {}, 'f': {}},
            't': {'r': {'o': {}}, 'y': {}}}

with open('the_file', 'w') as file:
    for tree in the_tree.values():
        line_first = True
        trees = [('ROOT', tree)]
        while len(trees):
            new_trees = []
            for node, children in trees:
                for child_node, child_children in children.items():
                    if child_children:
                        new_trees.append((child_node, child_children))
                    if line_first: line_first = False
                    else: file.write(' ')
                    file.write(f'({node}, {child_node})')
            trees = new_trees
        file.write('\n')

предупреждение: использует f-strings, которые были введены в версии 3.6!

---

И выдает намеченный результат:

(ROOT, b) (ROOT, g) (ROOT, f) (b, c) (b, d) (c, x) (d, p)
(ROOT, r) (ROOT, y) (r, o)

Answer 2

d = {'a': {'b': {'c': {'x': {}}, 'd': {'p': {}}}, 'g': {}, 'f': {}}, 't': {'r': {'o': {}}, 'y': {}}}
with open('file', 'w') as f:
    for r, s in d.items():
        q = []
        p = r
        while True:
            for k, v in s.items():
                f.write('(%s,%s) ' % ('ROOT' if p == r else p, k))
                if v:
                    q.append((k, v))
            if not q:
                break
            p, s = q.pop(0)
        f.write('\n')

Это выводит:

(ROOT,b) (ROOT,g) (ROOT,f) (b,c) (b,d) (c,x) (d,p) 
(ROOT,r) (ROOT,y) (r,o) 

Answer 3

Проще всего рекурсивно пройти по структуре с помощью генератора:

def flatten_forest(forest, write=True):
  def flatten(d, seen = None):
    for a, b in d.items():
      if seen is None:
       yield ('ROOT', a)
      else:
        yield (seen, a)
      if b:
        yield from flatten(b, a)
  if write:
    with open('full_flattened_tree.txt', 'a') as f:
      f.write(' '.join(map(str, flatten(forest)))+'\n')

data = {'a': {'b': {'c': {'x': {}}, 'd': {'p': {}}}, 'g': {}, 'f': {}}, 't': {'r': {'o': {}}, 'y': {}}}
for i in data.values():
  flatten_forest(i)

Вывод файла:

('ROOT', 'b') ('b', 'c') ('c', 'x') ('b', 'd') ('d', 'p') ('ROOT', 'g') ('ROOT', 'f')
('ROOT', 'r') ('r', 'o') ('ROOT', 'y')

Это будет работать с большими словарями:

import random, string, time
def create_structure(_len, _depth = 5, _count = 0):
 return {string.ascii_lowercase[i]:{} if _depth == _count else create_structure(random.randint(1, 26), _count = _count + 1) for i in range(_len)}

d = create_structure(26)
c = time.time()
flatten_forest(d, write=True)
print(time.time()-c)

Выход:

11.871491193771362