Поиск шаблона в словарных ключах - PullRequest
Новая
       2

Поиск шаблона в словарных ключах

0 голосов
/ 13 января 2020

Я хочу найти python словарные ключи по заданному шаблону. Это больше похоже на поиск по подстроке, но с уровнем char. Ниже код работает нормально, но мне нужно немного настроить, так как у него будут проблемы с производительностью, когда у нас есть тысячи ключей. Ха sh Ключи отсортированы по алфавиту. Под алфавитной сортировкой ключей я подразумеваю, что каждый ключ (слово) словаря сортируется сам по себе, а НЕ весь словарь, отсортированный по ключам. т. е. ключ может быть aaklm, а не kamal.

Кроме того, есть ли какая-либо внешняя библиотека / API для этой части поиска? 

import re

def getKey(str, list):
    expr = re.compile(str)
    return [elem for elem in list if expr.match(elem)]


wordDict = {'AADFLORW':['value1'], 'AAAGRU': ['VAL1', 'SOME DIFFERENT VALUE']}
m = re.compile(u'[a-zA-Z]').findall('ADOLF')    # I'm searching ADOLF in the keys
pat = '.*' + '(.*)'.join(sorted(m)) + '.*'

for key in getKey(pat, wordDict.keys()):
    print(key)

1 Ответ

2 голосов
/ 13 января 2020

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

Сначала я строю "мета" словарь, где ключи - это frozenset символов ключей wordDict, а значения - это списки ключей wordDict ,

В getKey(), с помощью этого мета-словаря я проверяю только ключи, где есть возможность совпадения (поэтому не все ключи). 

import re
from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def getKey(string, pat, meta):
    k = ''.join(sorted(set(string)))
    expr = re.compile(pat)
    return [elem for elem in meta[frozenset(k)] if expr.match(elem)] # <--- here I search only valid keys (keys where there's possibility of match)

wordDict = {'AADFLORW':['value1'], 'AAAGRU': ['VAL1', 'SOME DIFFERENT VALUE']}

# build meta information about wordDict.keys()
# This could take a while!!!
meta = {}
for k in wordDict.keys():
    for p in powerset(set(k)):
        if p:
            meta.setdefault(frozenset(p), []).append(k)

# from pprint import pprint
# pprint(meta)

m = re.compile(r'[a-zA-Z]').findall('ADOLF')    # I'm searching ADOLF in the keys
pat = '.*' + '(.*)'.join(sorted(m)) + '.*'

for key in getKey('ADOLF', pat, meta):
    print(key)

Отпечатки: 

ADFLORW

Для иллюстрации словарь "meta" теперь выглядит следующим образом: 

{frozenset({'A'}): ['AADFLORW', 'AAAGRU'],
 frozenset({'D'}): ['AADFLORW'],
 frozenset({'L'}): ['AADFLORW'],
 frozenset({'R'}): ['AADFLORW', 'AAAGRU'],
 frozenset({'W'}): ['AADFLORW'],
 frozenset({'O'}): ['AADFLORW'],
 frozenset({'F'}): ['AADFLORW'],
 frozenset({'A', 'D'}): ['AADFLORW'],
 frozenset({'A', 'L'}): ['AADFLORW'],
 frozenset({'A', 'R'}): ['AADFLORW', 'AAAGRU'],
 frozenset({'W', 'A'}): ['AADFLORW'],

...

Он может быть довольно большим, поэтому теперь вы меняете "space" на "speed".

...