Python словарь, постоянная сложность способ вернуть все ключи в dict содержат определенную строку

Question

У меня есть словарь типа: mydict = {'A B C':0, 'A B E':1, 'E F':0}

Затем у меня есть поисковый ключ search_string = 'A B'

, где я хотел бы найти все ключи и значения, которые search_string является частью mydict.keys(). Таким образом, в этом случае «AB C» и «ABE» удовлетворят.

Так как mydict может быть очень большим. Есть ли постоянная временная сложность для поиска, а не:

result = [search_string in key for key, val in mydict.items()]

Я также открыт для реструктуризации словаря, если это необходимо.

Answer 1

Если при поиске всегда используются префиксы строки, вы можете использовать дерево префиксов или Tr ie, которое является существующим Python модулем.

Tr ie позволяет найти совпадения за время O (M), где M - максимальная длина строки ссылка (т.е. зависит от максимальной длины ключа, а не от количества ключей).

Код

from pytrie import StringTrie 

def create_prefix(dict):
" Creates a prefix tree based upon a dictionary "
  # create empty trie 
  trie = StringTrie() 

  for k in dict:
    trie[k] = k

  return trie

Тест 1

# Preprocess to create prefix tree
mydict = {'A B C':0, 'A B E':1, 'E F':0}
prefix_tree = create_prefix(mydict)

# Now you can use search tree multile times to speed individual searches
for search_string in ['A B', 'A B C', 'E', 'B']:
  results = prefix_tree.values(search_string) # # .values resturn list that has this as a prefix
  if results:
    print(f'Search String {search_string} found in keys {results}')
  else:
    print(f'Search String {search_string} not found')

Выход

Search String A B found in keys ['A B C', 'A B E']
Search String A B C found in keys ['A B C']
Search String E found in keys ['E F']
Search String B not found

Тест 2 (добавлено для ответа на вопрос из OP)

mydict = {'A B C':0, 'A B C D':0, 'A B C D E':0}
prefix_tree = create_prefix(mydict)
# Now you can use search tree multile times to speed individual searches
for search_string in ['A B', 'A B C', 'A B C D', 'A B C D E', 'B C']:
  results = prefix_tree.values(search_string) # # .values resturn list that has this as a prefix
  if results:
    print(f'Search String {search_string} found in keys {results}')
  else:
    print(f'Search String {search_string} not found')

Выход

Search String A B found in keys ['A B C', 'A B C D', 'A B C D E']
Search String A B C found in keys ['A B C', 'A B C D', 'A B C D E']
Search String A B C D found in keys ['A B C D', 'A B C D E']
Search String A B C D E found in keys ['A B C D E']
Search String B C not found

Answer 2

Здесь у вас есть два возможных решения - первое не имеет сложности O (1), но, вероятно, вы захотите go:

Мы можем попробовать построить дерево и сделать поиск таким образом - по сути, так:

Вы могли бы иметь такой вид, что mydict выглядит так:

test_dict = {
    'A': {
        'B': {
            'C': 0,
            'E': 1
        }
    },
    'E': {
        'F': 1
    }
}

def get_recursive_values(mydict):
    results = []
    for key in mydict:
        if isinstance(mydict[key], dict):
            results.extend(get_recursive_values(mydict[key]))
        else:
            results.append(mydict[key])
    return results


def search(mydict, search_text):
    components = search_text.split(' ')
    if components[0] in mydict:
        next_res = mydict[components[0]]
        if isinstance(next_res, dict):
            if len(components) == 1:
                return get_recursive_values(next_res)
            return search(next_res, " ".join(components[1:]))
        else:
            return [mydict[components[0]]]
    raise KeyError(components[0])

Возможно, это можно было бы написать немного лучше, но это сработает для вас - попробуйте позвонить search(test_dict, 'A B')

и вы получите оба результата.

Другим потенциальным решением было бы, если вам не нужно время вставки, иметь все значения для всех различных клавиш. это может показаться немного нелепым, но вы получите значения за O (1), но время вставки будет большим - т.е.

   'A': [0, 1],
   'A B': [0, 1],
   'A B C': [0],
   'A B E': [1],
   'E': [1],
   'E F': [1]
}

def insert(mydict, key, value):
    for k in mydict:
        if k.startswith(key):
            mydict[k].append(value)
    mydict[key] = [value]