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

Question

假设我有一个类似于2,000个关键字的数据库,每个关键字映射到一些常见的变体

例如:

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

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

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

我知道我可以进行大量的regex搜索,但是有更有效的方法吗？某个网络应用程序的近似"实时"或接近实时的东西？

我目前正在查看弹性搜索文档,但我想知道有没有Pythonic办法实现我的结果.

我很熟悉,regex但我现在不想写这么多正则表达式.我将非常感谢您的回答,或者您是否可以指出我正确的方向.

Answer 1

你可以使用一个反转这个关键词典的数据结构 - 这样每一个["node.js", "nodejs", "node js", "node", "Node"]都是一个值为"Node"的键 - 其他2000个关键词的10个左右的变体中的每一个都指向一个关键词 - 所以a 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

至于效率,这种方法相当不错,因为文本上的每个单词只会在字典上查找一次,而Python的字典搜索是O(log(n)) - 它会给你一个O(n log( n))方法.正如你所想的那样尝试一个单超级正则表达式将是O(n²),无论正则表达式匹配的速度有多快(并且与dict查找相比并不那么快).

如果文本太长,可能使用简单的拆分(或正则表达式)对其进行预先标记是不可行的 - 在这种情况下,您可以每次只读取一段文本并将其中的小块分成单词.

其他方法

由于您不需要每个单词的计数,另一种方法是使用文档中的单词和列表中的所有关键字创建Python集,然后取两个集的交集.您只能计算此交集的关键字与words上面的 反转字典.

抓住这些 都不包括包含空格的帐户术语 - 我总是认为单词可以被标记为单独匹配,但str.split和简单的标点删除正则表达式无法解释像'ruby on rails'这样的组合术语'node js'.如果没有其他的解决方法,而不是'拆分',你将不得不编写一个custon tokenizer,它可以尝试在整个文本中对着倒置的dict匹配一个,两个和三个单词的集合.