我可以通过匹配关键字作为前缀来保留字典中的生词吗

Question

我有一本字典说

stringToListDict = {'foo' : [], 'bar' : []}

现在让我们假设是这样

+福福

stringToListDict = {'foo' : ['foofoo'], 'bar' : []}

+芭芭拉

stringToListDict = {'foo' : ['foofoo'], 'bar' : ['barbar']}

+巴巴拉

stringToListDict = {'foo' : ['foofoo', 'foobarbar'], 'bar' : ['barbar']}

+不匹配任何键

Simply discard this new string.

如您所见，添加的字符串将匹配键作为前缀。你知道吗

我可以通过逐个遍历字典中的每个键来实现这一点，直到得到匹配的前缀。但是，还有其他优雅或有效的方法吗？您不必担心边缘场景，例如如果：

stringToListDict = {'foo' : ['foofoo'], 'foobar' : [], 'bar' : ['barbar']}

then +foobarbar

仅供参考，这不是任务。你知道吗

Answer 1

如果您使用的是dict，那么是的，您将不得不迭代所有键以找到任何匹配项。dict是建立在哈希表上的，哈希函数没有任何可以利用的“start with”或“close”的概念（事实上，它们是专门为close输入提供非常不同的输出的）。你知道吗

做你想做的事一点都不难：

for k, v in d.items():
    if s.startswith(k):
        v.append(s)
        break
else:
    # whatever you want to do if no prefix exists

但是如果dict很大，那么效率就很低，因为你在做线性搜索。你知道吗

---

您可以使其与键的长度成线性关系，而不是与dict的长度成线性关系（在您的测试用例中，dict实际上会慢一些，但在性能重要的大多数情况下可能会快一些）：

for i in range(len(s), 0, -1):
    try:
        d[k[:i]].append(s)
        break
    except KeyError:
        pass
else:
    # whatever you want to do if no prefix exists

---

但是，如果您需要最佳效率，您需要查看对数数据结构，比如平衡二叉搜索树、b-树、skiplist、trie，甚至只是按排序顺序保存的普通旧列表。在PyPI或ActiveState配方库中可以找到的大多数此类类型的实现都有一个方法，可以按排序顺序查找键的插入位置。或者，如果您使用的是普通的旧列表，只需使用stdlib中的bisect模块即可。只需在插入位置之前检查密钥，要么它以您的密钥开始，要么什么都不做。你知道吗

例如，使用^{}：

i = d.bisect(s)
if d.iloc[i].startswith(s):
    d[d.iloc[i]].append(s)
else:
    # whatever you want to do if no prefix exists

如果你有一个庞大而密集的密钥集，并且你要做大量的查询和插入，那么前缀trie可能是最有效的。但由于不同的特点，其他人可能会胜出。所以，如果这很重要的话，你可以试一下。你知道吗

Answer 2

您可以尝试：

_dict = {'foo' : [], 'bar' : []}

def _add(_str):
    for _key in _dict.keys(): # loop _dict keys
        if _str.startswith(_key): # check if _str starts with _dict _key
            _dict[_key].append(_str) # append _str to _dict based on _key

_add("foofoo")
_add("barbar")
_add("foobarbar")
_add("notMatchingAnyKey")

# {'foo': ['foofoo', 'foobarbar'], 'bar': ['barbar']}

---

Ideone Demo

Answer 3

可以使用以下函数执行前缀匹配：

代码：

def append_longest_prefix(data_dict, to_append):
    for i in range(1, len(to_append)):
        if to_append[:-i] in data_dict:
            data_dict[to_append[:-i]].append(to_append)
            return

测试代码：

data = {'foo': [], 'bar': []}

append_longest_prefix(data, 'foofoo')
append_longest_prefix(data, 'barbar')
append_longest_prefix(data, 'foobarbar')
append_longest_prefix(data, 'notMatchingAnyKey')

print(data)

data = {'foo' : ['foofoo'], 'foobar' : [], 'bar' : ['barbar']}
append_longest_prefix(data, 'foobarbar')
print(data)

结果：

{'foo': ['foofoo', 'foobarbar'], 'bar': ['barbar']}

{'foo': ['foofoo'], 'foobar': ['foobarbar'], 'bar': ['barbar']}