快速字符串 "Startswith" 匹配字典类对象

Question

我目前有一些代码需要非常高效，我实际上是在进行字符串字典键查找：

class Foo:
    def __init__(self):
        self.fast_lookup = {"a": 1, "b": 2}

    def bar(self, s):
        return self.fast_lookup[s]

self.fast_lookup 的查找时间为 O(1)，并且没有 try/if 等会减慢查找速度的代码

有没有办法在执行“startswith”查找时保持这个速度？上面的代码在 s="az" 上调用 bar 会导致键错误，如果将其更改为“startswith”实现，那么它将 return 1.

注意：我很清楚如何使用 regex/startswith 语句执行此操作，我正在寻找专门针对 startswith dict 查找的性能

Answer 1

我不完全理解这个问题，但我会尝试想办法减少查找甚至必须要做的工作。如果您知道 startswith 将要执行的基本搜索，您可以将它们作为键添加到字典中，并将指向同一对象的值添加到字典中。你的字典会很快变得很大，但我相信它会大大减少查找。因此，也许对于更动态的方法，您可以为第一组字母添加字典键，每个条目最多三个。

如果不主动存储每次搜索的引用，您的代码将始终需要获取每个 dict 对象的值，直到它获得一个匹配的值。你不能减少它。

Answer 2

执行此操作的一种有效方法是使用 the pyahocorasick module to construct a trie with the possible keys to match, then use the longest_prefix method 来确定给定字符串的匹配程度。如果 no "key" 匹配，它 returns 0，否则它会说传递的字符串的 much 是如何存在的在自动机中。

安装 pyahocorasick 后，它看起来像：

import ahocorasick

class Foo:
    def __init__(self):
        self.fast_lookup = ahocorasick.Automaton()
        for k, v in {"a": 1, "b": 2}.items():
            self.fast_lookup.add_word(k, v)

    def bar(self, s):
        index = self.fast_lookup.longest_prefix(s)
        if not index:  # No prefix match at all
            raise KeyError(s)
        return self.fast_lookup.get(s[:index])

如果发现最长前缀实际上并未映射到值（例如，'cat' 已映射，但您正在查找 'cab'，并且没有其他条目实际映射 'ca' 或 'cab'), 这将以 KeyError 结束。根据需要进行调整以实现所需的精确行为（例如，您可能需要使用 longest_prefix 作为起点并尝试 .get() 为该长度或更短的所有子字符串，直到您获得成功）。

请注意，这不是 Aho-Corasick 的主要目的（它是一种有效的方法，可以一次搜索一个或多个长字符串中的多个固定字符串） , 但作为一个整体的尝试是处理这种形式的前缀搜索的有效方法，Aho-Corasick 是根据尝试实现的，并提供了尝试的大部分有用特性，使其更广泛有用（如本例） .

快速字符串 "Startswith" 匹配字典类对象

Fast String "Startswith" Matching for Dict like object

python

string

dictionary

startswith

python-3.x