在 Python 中有效地搜索字符串

Question

假设我有一个包含大约 2,000 个关键字的数据库，每个关键字都映射到一些常见的变体

例如：

 "Node" : ["node.js", "nodejs", "node js", "node"] 

 "Ruby on Rails" : ["RoR", "Rails", "Ruby on Rails"]

我想搜索一个字符串（好的，一个文档）和return一个包含所有关键字的列表。

我知道我可以遍历大量 regex 搜索，但是有没有更有效的方法呢？网络应用程序接近 "real time" 或接近实时？

我目前正在查看 Elastic Search 文档，但我想知道是否有 Pythonic 方法可以实现我的结果。

我对regex很熟悉，但我现在不想写那么多正则表达式。如果您能给我指明正确的方向，我将不胜感激。

Answer 1

您可以使用 data-structure 来反转这个关键字字典 - 这样每个 ["node.js", "nodejs", "node js", "node", "Node"] 都是一个值为 "Node" 的键 - 大约 10 个变体中的每个变体对于其他 2000 个关键字，指向其中一个关键字 - 所以一个 20000 大小的字典，这并不多。

使用 taht dict，您可以将您的文本重新标记为仅由关键字的规范化形式组成，然后它们继续计数。

 primary_dict = {
     "Node" : ["node.js", "nodejs", "node js", "node", "Node"] 

      "Ruby_on_Rails" : ["RoR", "Rails", "Ruby on Rails"]
 }

def invert_dict(src):
    dst = {}
    for key, values in src.items():
        for value in values:
            dst[value] = key
    return dst

words = invert_dict(primary_dict)
from collections import Counter

def count_keywords(text):
    counted = Counter()
    for word in text.split(): # or use a regex to split on punctuation signs as well
        counted[words.get(word, None)] += 1
    return counted

至于效率，这个方法还是不错的，因为文本中的每个单词只会在字典中被looked-up一次，而Python的字典搜索是O(log( n)) - 这给了你一个 O(n log(n)) 方法。尝试你所想的 single-mega-regexp 将是 O(n²)，无论正则表达式匹配有多快（与 dict 查找相比它并不那么快）。

如果文本太长，也许 pre-tokenizing 用简单的分割（或正则表达式）是不可行的 - 在这种情况下，你可以每次只读一段文本，然后分成小块用文字表达。

其他方法

由于您不需要计算每个单词的数量，另一种方法是使用文档中的单词和列表中的所有关键字创建 Python 集合，然后取两个集合的交集.你可以只计算 this 交集的关键字与上面的 words inverted dict 的对比。

抓住 None 其中考虑了包含空格的术语 - 我一直在考虑单词可以标记化以单独匹配，但是 str.split，简单的 punctuation-removing 正则表达式不能解释组合术语像 'ruby on rails' 和 'node js'。如果您没有其他解决方法，您将不得不编写一个自定义分词器，而不是 'split'，它可以尝试将整个文本中的一组单词、两个单词和三个单词与倒置字典进行匹配。

Answer 2

另一种对长字符串标记化有用的方法是构造一个综合正则表达式，然后使用命名组来识别标记。它需要一些设置，但识别阶段被推入 C/native 代码，并且只需要一次通过，因此它可以非常有效。例如：

import re

tokens = {
    'a': ['andy', 'alpha', 'apple'],
    'b': ['baby']
}

def create_macro_re(tokens, flags=0):
    """
    Given a dict in which keys are token names and values are lists
    of strings that signify the token, return a macro re that encodes
    the entire set of tokens.
    """
    d = {}
    for token, vals in tokens.items():
        d[token] = '(?P<{}>{})'.format(token, '|'.join(vals))
    combined = '|'.join(d.values())
    return re.compile(combined, flags)

def find_tokens(macro_re, s):
    """
    Given a macro re constructed by `create_macro_re()` and a string,
    return a list of tuples giving the token name and actual string matched
    against the token.
    """
    found = []
    for match in re.finditer(macro_re, s):
        found.append([(t, v) for t, v in match.groupdict().items() if v is not None][0])
    return found

最后一步，运行完成它：

macro_pat = create_macro_re(tokens, re.I)
print find_tokens(macro_pat, 'this is a string of baby apple Andy')

macro_pat 最终对应于：

re.compile(r'(?P<a>andy|alpha|apple)|(?P<b>baby)', re.IGNORECASE)

第二行打印一个元组列表，每个元组都给出标记和与标记匹配的实际字符串：

[('b', 'baby'), ('a', 'apple'), ('a', 'Andy')]

此示例展示了如何将标记列表编译成单个正则表达式，并且可以高效地运行一次通过一个字符串。

未显示的是它的一大优势：不仅可以通过字符串，还可以通过正则表达式定义标记。因此，如果我们想要 b 标记的替代拼写，例如，我们不必详尽地列出它们。正常的正则表达式模式就足够了。假设我们还想将 'babby' 识别为 b 标记。我们可以像以前一样做 'b': ['baby', 'babby']，或者我们可以使用正则表达式做同样的事情：'b': ['babb?y']。或者 'bab+y' 如果你还想包含任意内部 'b' 字符。

在 Python 中有效地搜索字符串

Efficiently String searching in Python

python

regex

tags

algorithm

elasticsearch