问在字典关键字中搜索模式
EN

Stack Overflow用户

提问于 2020-01-13 17:29:02

回答 1查看 68关注 0票数 0

我想搜索一些给定模式的python字典关键字。这更像是子字符串搜索，但使用的是char级别。下面的代码运行良好，但我需要一些调整，因为它将有性能问题时，我们有数千个键。哈希键有排序的字母表。通过关键字的字母顺序排序，我的意思是字典中的每个关键字(单词)本身都是排序的，而不是整个字典根据关键字进行排序。也就是说，key可以是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)

substring

python

python-3.x

dictionary

单节点MySQL

低成本高体验，解决您的基础业务数据需求

回答 1

Stack Overflow用户

发布于 2020-01-13 20:58:27

与现在一样，搜索的主要部分将是根据模式检查wordDict中的每个键。我能想到的一种优化是减少这种搜索。

首先，我构建了“元”字典，其中键是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'],

...