在Python中高效地进行字符串搜索

3
假设我有一个包含2,000个关键词的数据库,每个关键词都对应几个常见的变体。
例如:
 "Node" : ["node.js", "nodejs", "node js", "node"] 

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

我想搜索一个字符串(好的,一个文档),并返回包含的所有关键字的列表。

我知道我可以通过大量的正则表达式搜索来循环,但是否有更有效的方法?对于 Web 应用程序,是否有类似于“实时”或接近实时的东西?

我目前正在查看 Elastic Search 文档,但我想知道是否有一种 Pythonic 的方法来实现我的结果。

我非常熟悉 regex,但现在不想写太多的正则表达式。如果您能回答我的问题或指导我正确的方向,我将不胜感激。


1
Elasticsearch确实是前进的道路! - Nir Alfasi
你能分享一些好的文档或链接吗?这些文档或链接可以让我快速入门,减少痛苦吗? - python
甚至 Elasticsearch 是否能够从一个包含 10000 个术语(2000 X ~5 同义词)的输入中创建一组匹配单词?但是,下面的倒排字典想法仍然需要用于将搜索器机制过滤到完整的 10000 个单词中,以便返回关键的 2000 个术语。 - jsbueno
2个回答

5
您可以使用一种数据结构来反转这个关键字的字典 - 这样每个["node.js", "nodejs", "node js", "node", "Node"]中的关键字都是一个键,其值为"Node" - 其他10个左右的其他2000个关键字的变体指向其中一个关键字,因此有一个大小为20000的字典,这不算太多。

有了这个字典,您可以重新标记您的文本,只由关键字的规范形式组成,然后进行计数。

 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

关于效率方面,这种方法相当不错,因为文本中的每个单词只会在字典中查找一次,而Python的字典搜索是O(log(n))——这给你提供了一个O(n log(n))的方法。尝试像你想的那样使用单一的超级正则表达式将是O(n²),无论正则表达式匹配有多快(与字典查找相比并不快)。
如果文本太长,用简单的拆分(或正则表达式)进行预分词可能不可行——在这种情况下,您可以每次读取一块文本,并将其小块分成单词。
另一种方法
由于您不需要每个单词的计数,另一种选择是创建包含文档中的单词和列表中所有关键字的Python集合,然后取两个集合的交集。您只需针对上述“words”反向字典中的此交集集合计算关键字即可。
注意事项
这些都没有考虑包含空格的术语——我始终认为单词可以被标记为单独匹配,但str.split和简单的去标点符号的正则表达式不能处理像“ruby on rails”和“node js”这样的组合术语。如果没有其他解决办法,您将不得不编写一个自定义分词器,尝试将文本中的一、二和三个词组与反向字典进行匹配。

不错的答案,但效率不高啊!我的文本是一个大文件,这样会花费很长时间! - python
我已经评论了效率。请注意,你匆忙地认为正则表达式会神奇地更快:它们在本地代码中运行,但它们并不是魔法。 - jsbueno
5
当别人尽力帮助你时,仅仅“猜测”一个方法是否有效有点不合理:至少请测试一下并说:“使用该方法,我每秒只能处理X个单词,但考虑到我的实际文档大小,我需要每秒处理Y个单词才能为用户提供良好的体验”。在准备这样具有建设性的反馈时,你可能会偶尔发现某些方法尽管与你的直觉不符,但已经足够高效。如果不是,至少别人知道他们为什么要寻找替代方案以及接近目标有多远... - Tony Delroy
非常抱歉!这是一个Web应用程序,我需要编写大量代码来测试此功能。但是我要感谢你,给了我一个很好的开端! - python

1

一种用于分词长字符串的替代方法是构建一个单一的万能正则表达式,然后使用命名组来识别标记。这需要一些设置,但识别阶段被推入C/本地代码中,并且只需要一次通过,因此它可以非常高效。例如:

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']。或者如果您想包括任意内部的'b'字符,则使用'bab+y'

这是一个非常好的解释。谢谢 :) 希望我能给你更多的赞! - python

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接