Python - распечатка дерева в алфавитном порядке с рекурсивной функцией - PullRequest
Новая
       74

Python - распечатка дерева в алфавитном порядке с рекурсивной функцией

0 голосов
/ 01 ноября 2019

Я пробираюсь через книгу NLTK Берда, Кляйна и Лопера, и я застрял в проблеме. Я работаю над книгой для своего личного обогащения, а не для класса.

Проблема, на которой я застрял, - 4.29:

Написать рекурсивныйфункция, которая довольно печатает дерево в алфавитном порядке, например:

chair: 'flesh' ---t: 'cat' --ic: 'stylish' ---en: 'dog'

Я использую этот код из книги для создания дерева: 

def insert(trie, key, value):
    if key:
        first, rest = key[0], key[1:]
        if first not in trie:
            trie[first] = {}
        insert(trie[first], rest, value)
    else:
        trie['value'] = value

trie = {}
insert(trie, 'chat', 'cat')
insert(trie, 'chien', 'dog')
insert(trie, 'chair', 'flesh')
insert(trie, 'chic', 'stylish')

Я изменил ответ из этого обсуждения для функции, которая рекурсивно проходит через три и извлекает полные ключи и значения: 

def trawl_trie(trie):
    unsorted = []
    for key, value in trie.items():
        if 'value' not in key:
            for item in trawl_trie(trie[key]):
                unsorted.append(key + item)
        else:
            unsorted.append(': ' + value)

    return unsorted

Но я 'Я не могу использовать рекурсию, чтобы составить алфавитный список, и при этом я не могу понять, как использовать рекурсию, чтобы заменить дублирующиеся части ключей. Лучшее, что я могу сделать, - это создать вспомогательную функцию, которая обрабатывает результаты описанной выше функции: 

def print_trie(trie):

    # sort list alphabetically
    alphabetized = list(sorted(set(trawl_trie(trie))))


    print(alphabetized[0])

    # compare the 2nd item ~ to the previous one in the list.
    for k in range(1, len(alphabetized)):
        # separate words from value
        prev_w, prev_d = (re.findall(r'(\w+):', alphabetized[k - 1]), re.findall(r': (\w+)', alphabetized[k - 1]))
        curr_w, curr_d = (re.findall(r'(\w+):', alphabetized[k]), re.findall(r': (\w+)', alphabetized[k]))
        word = ''

        # find parts that match and replace them with dashes
        for i in range(min(len(prev_w[0]), len(curr_w[0]))):
            if prev_w[0][i] == curr_w[0][i]:
                word += prev_w[0][i]

        curr_w[0] = re.sub(word, '-' * len(word), curr_w[0])
        print(curr_w[0] + ": " + str(curr_d[0]))

Это будет вывод: 

print_trie(trie)

chair: flesh
---t: cat
--ic: stylish
---en: dog

Кто-нибудь знает, еслиможно было бы получить тот же результат с одной рекурсивной функцией? Или я застрял, используя рекурсивную функцию, чтобы пройти три, и вторую вспомогательную функцию, чтобы все выглядело хорошо?

Приветствия,

  • MC

Ответы [ 2 ]

0 голосов
/ 01 ноября 2019

Я изменил ответ DarrylG ( еще раз спасибо! ), добавив список принятых ключей, которые проходят через рекурсию, и пару for -циклов, которые повторяются в этом списке, чтобы увидеть, есть лилюбые общие элементы в начале строки, которые можно заменить.

Редактировать 02.11.19: в этой модификации есть ошибка, которую я не заметил. Он будет работать правильно в первый раз, но при последующих запусках он заменит слишком много символов, например: 

----r: flesh
---t: cat
---c: stylish
----n: dog

def insert(trie, key, value):
    """Insert into Trie"""
    if key:
        first, rest = key[0], key[1:]
        if first not in trie:
            trie[first] = {}
        insert(trie[first], rest, value)
    else:
        trie['value'] = value

def display(trie, s = "", final = []):

    """Recursive function to Display Trie entries in alphabetical order"""

    for k, v in sorted(trie.items(), key = lambda x: x[0]):

        # dictionary sorted based upon the keys
        if isinstance(v, dict):
            display(v, s + k, final)   # s+k is extending string s for display by appending current key k
        else:
            # replace common elements at beginning of strings with dashes
            i = sum([any([f.startswith(string[:j]) for f in final]) for j in range(1, len(string))])
            string = '-' * i + s[i:]

            print(string + ":", v)  # not a dictionary, so print current edited s and value
            final.append(s)


# Create Trie
trie = {}
insert(trie, 'chat', 'cat')
insert(trie, 'chien', 'dog')
insert(trie, 'chair', 'flesh')
insert(trie, 'chic', 'stylish')

#Display Use Recursive function (second argument will default to "" on call)
display(trie)
0 голосов
/ 01 ноября 2019 
def insert(trie, key, value):
    """Insert into Trie"""
    if key:
        first, rest = key[0], key[1:]
        if first not in trie:
            trie[first] = {}
        insert(trie[first], rest, value)
    else:
        trie['value'] = value

def display(trie, s = ""):
  """Recursive function to Display Trie entries in alphabetical order"""
  first = True
  for k, v in sorted(trie.items(), key = lambda x: x[0]):
    # dictionary sorted based upon the keys
    if isinstance(v, dict):
      if first:
        prefix = s + k          # first to show common prefix
        first = False
      else:
        prefix = '-'*len(s) + k  # dashes for common prefix

      display(v, prefix)   # s+k is extending string s for display by appending current key k
    else:
      print(s, ":", v)  # not a dictionary, so print current   # not a dictionary, so print current string s and value

# Create Trie
trie = {}
insert(trie, 'chat', 'cat')
insert(trie, 'chien', 'dog')
insert(trie, 'chair', 'flesh')
insert(trie, 'chic', 'stylish')

#Display Use Recursive function (second argument will default to "" on call)
display(trie)

Выход 

chair : flesh
---t : cat
--ic : stylish
---en : dog
...