Блог

Я пытаюсь определить самый быстрый способ поиска во вложенном словаре с помощью регулярного выражения и возврата путей к каждому вхождению этой строки. Меня интересуют только значения, которые являются строками, а не другие значения, которые могут явно не быть строками. Рекурсия не является моей сильной стороной. Вот пример JSON, допустим, я ищу все абсолютные пути, которые содержат ‘blah’.

 d = {'id': 'abcde',
 'key1': 'blah',
 'key2': 'blah blah',
 'nestedlist': [{'id': 'qwerty',
   'nestednestedlist': [{'id': 'xyz', 'keyA': 'blah blah blah'},
    {'id': 'fghi', 'keyZ': 'blah blah blah'}],
   'anothernestednestedlist': [{'id': 'asdf', 'keyQ': 'blah blah'},
    {'id': 'yuiop', 'keyW': 'blah'}]}]}
  

Я нашел следующий фрагмент кода, но мне не удалось заставить его возвращать пути, а не просто печатать их. Помимо этого, не должно быть слишком сложно добавить «ЕСЛИ значение является строкой и содержит re.search(), ТО добавьте путь к списку».

 def search_dict(v, prefix=''):
    
    if isinstance(v, dict):
        for k, v2 in v.items():
            p2 = "{}['{}']".format(prefix, k)
            search_dict(v2, p2)
    elif isinstance(v, list):
        for i, v2 in enumerate(v):
            p2 = "{}[{}]".format(prefix, i)
            search_dict(v2, p2)
    else:
        print('{} = {}'.format(prefix, repr(v)))
  

Оба ответа здесь с готовностью вычисляют результат, исчерпывая весь входной dict, прежде чем возвращать первый (если таковой имеется) доступный результат. Мы можем использовать yield from для кодирования более питоновской программы —

 def search_substr(t = {}, q = ""):
  def loop(t, path):
    if isinstance(t, dict):
      for k, v in t.items():
        yield from loop(v, (*path, k))  # <- recur
    elif isinstance(t, list):
      for k, v in enumerate(t):
        yield from loop(v, (*path, k))  # <- recur
    elif isinstance(t, str):
      if q in t:
        yield path, t                   # <- output a match
  yield from loop(t, ())                # <- init

for (path, value) in search_substr(d, "blah"):
  print(path, value)
  

Результат —

 ('key1',) blah
('key2',) blah blah
('nestedlist', 0, 'nestednestedlist', 0, 'keyA') blah blah blah
('nestedlist', 0, 'nestednestedlist', 1, 'keyZ') blah blah blah
('nestedlist', 0, 'anothernestednestedlist', 0, 'keyQ') blah blah
('nestedlist', 0, 'anothernestednestedlist', 1, 'keyW') blah
  

Обратите внимание, мы проверяем наличие подстроки q в target t с помощью q in t . Если вы действительно хотите использовать regexp для этого —

 from re import compile

def search_re(t = {}, q = ""):
  def loop(t, re, path):                      # <- add re
    if isinstance(t, dict):
      for k, v in t.items():
        yield from loop(v, re, (*path, k))    # <- carry re
    elif isinstance(t, list):
      for k, v in enumerate(t):
        yield from loop(v, re, (*path, k))    # <- carry re
    elif isinstance(t, str):
      if re.search(t):                        # <- re.search
        yield path, t
  yield from loop(t, compile(q), ())          # <- compile q
  

Теперь мы можем выполнять поиск с помощью регулярного выражения —

 for (path, value) in search_re(d, r"[abhl]{4}"):
  print(path, value)
  

Результат —

 ('key1',) blah
('key2',) blah blah
('nestedlist', 0, 'nestednestedlist', 0, 'keyA') blah blah blah
('nestedlist', 0, 'nestednestedlist', 1, 'keyZ') blah blah blah
('nestedlist', 0, 'anothernestednestedlist', 0, 'keyQ') blah blah
('nestedlist', 0, 'anothernestednestedlist', 1, 'keyW') blah
  

Давайте попробуем другой поиск, используя другой запрос —

 for (path, value) in search_re(d, r"[dfs]{3}"):
  print(path, value)
  

 ('nestedlist', 0, 'anothernestednestedlist', 0, 'id') asdf
  

Наконец, search_substr и search_re ничего не выдают, когда запрос не соответствует —

 print(list(search_re(d, r"zzz")))
# []
  

Вам просто нужно инициализировать выходной список, append элементы, найденные в текущем вызове, и extend его по результатам, возвращаемым рекурсивными вызовами.

попробуйте это:

 def search_dict(v, prefix=''):
    result = []
    if isinstance(v, dict):
        for k, v2 in v.items():
            p2 = "{}['{}']".format(prefix, k)
            result.extend(search_dict(v2, p2))
    elif isinstance(v, list):
        for i, v2 in enumerate(v):
            p2 = "{}[{}]".format(prefix, i)
            result.extend(search_dict(v2, p2))
    else:
        result.append('{} = {}'.format(prefix, repr(v)))
    return result
  

Adam.Er8 точен, я просто хотел дать более четкий ответ на вопрос:

 def search_dict(v, re_term, prefix=''):

    re_term = re.compile(re_term)
    result = []
    if isinstance(v, dict):
        for k, v2 in v.items():
            p2 = "{}['{}']".format(prefix, k)
            result.extend(search_dict(v2, re_term, prefix = p2))
    elif isinstance(v, list):
        for i, v2 in enumerate(v):
            p2 = "{}[{}]".format(prefix, i)
            result.extend(search_dict(v2, re_term, prefix = p2))
    elif isinstance(v, str) and re.search(re_term,v):
        result.append(prefix)
    return result