эффективно Строка поиска в Python

Question

Скажем, у меня была база данных как 2000 ключевых слов, которые каждая карта на несколько общих вариаций

Например:

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

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

и я хочу, чтобы найти строку (ок , документ) и вернуть список всех содержащихся в нем ключевых слов.

Я знаю, что мог бы пройти через тонну regex поисков, но есть ли более эффективный способ сделать это? что-то приближающееся к «реальному времени» или почти в реальном времени для веб-приложения?

В настоящее время я просматриваю документ Elastic Search, но хочу знать, есть ли способ достичь моего результата.

Я довольно хорошо знаком с regex, но сейчас я не хочу писать так много регулярных выражений. Буду признателен за ваши ответы или если вы можете указать мне в правильном направлении.

Answer 1

Вы можете использовать структуру данных, которая инвертирует этот словарь ключевых слов, так что каждый из ["node.js", "nodejs", "node js", "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 

Что касается эффективности, этот подход достаточно хорошо, так как каждое слово по тексту будут смотреть вверх на словарь только один раз, и Пайтона поиск ДИКТ является O (журнал (п)) - что дает вы используете метод O (n log (n)). Попытка одно-мега-regexp, как вы думали, будет O (n²), независимо от того, насколько быстро соответствует регулярное выражение (и это не так быстро по сравнению с поиском dict).

Если это слишком длинный текст, возможно, его предварительная маркировка с простым разделом (или регулярным выражением) не представляется возможным - в этом случае вы можете просто читать кусок текста каждый раз и делить мелкие куски его в слова.

Другой подход

Поскольку вам не нужно счетчик для каждого слова, альтернативой является создание Python устанавливает со словами в документе и все ключевые слова в списке, а затем взять пересечение обоих множеств. Вы можете рассчитывать только ключевые слова этого набора пересечений против перевернутого dict .

Поймайте Ничего из этого не принимать во внимание члены, которые содержат пробелы - Я всегда рассматривает слова могут быть лексемы быть индивидуально подобраны, но str.split, и простые знаки удаляющих регэкспы не может объяснить сложенных терминов например, «ruby on rails» и «node js». Если для вас нет другого обходного пути, вместо «раскола» вам нужно будет написать токенизатор custon, который может попытаться сопоставить наборы из одного, двух и трех слов по всему тексту против перевернутого dict.

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'.