Лучший способ сопоставить, присутствует ли подстрока в ключах словаря Python

Question

У меня есть словарь Python, пример структуры которого приведен ниже (отрывок):

items = {
    "Google": "Mountain View",
    "Johnson & Johnson": "New Brunswick",
    "Apple": "Cupertino",
}

Теперь у меня есть строка, а именно str1. Я хочу посмотреть, есть ли в строке str1 какой-либо из ключей из словаря items, например, если у меня есть строка типа Where is Google based out of?. Первоначально я написал этот псевдокод:

for str_word in str1.split():
    if str_word in items:
       print("Key found. Value is = ".format(items[str_word]))

Теперь это хорошо, так как ключи словаря проиндексированы / хешированы. Таким образом, время выполнения оператора in является постоянным, но, как вы можете заметить, это прекрасно работает для таких слов, как Google или Apple, но это не будет работать для Johnson & Johnson (если моя строка Where is Jonhnson & Johnson based out of?).

Другой способ, о котором я могу подумать, - это сначала извлечь все ключи из словаря, а затем выполнить итерацию по одному для каждого ключа и посмотреть, присутствует ли он в str1 (обратный способ первого подхода). Это увеличит время выполнения, так как мой словарь огромен с сотнями или тысячами ключей.

Я хочу знать, есть ли способ, которым я могу изменить свой первый подход, чтобы подсчитать возможность сопоставления подстроки с ключами словаря, который может содержать несколько слов, таких как Johnson & Johnson?

Answer 1

для сопоставления с несколькими шаблонами в словаре, рекомендуемое решение: Aho-Corasick , алгоритм aho-corasick, используемый для статического и динамического сопоставления с образцом

также вы можете использовать это решение для динамического сопоставления с образцом по суффиксному дереву

Answer 2

Если ваша строка всегда одна и та же / имеет структуру, вы можете использовать регулярное выражение для соответствия ключу, который вы ищете.

import re

string = 'Where is Johnson and Johnson based out of?'
match = re.search(r'Where is (.*) based out of?',string)
key = match.group(1)

Конечно, вы должны изменить это, чтобы соответствовать тому, что вам нужно.

В противном случае, я думаю, я бы пошел с вашим подходом итерации по ключам dict, чтобы посмотреть, соответствуют ли они вашей строке. Разделение str1 может создать проблемы, если у вас более одной клавиши, например, &.

Answer 3

Подход может быть следующим:

items = {
        "Google":"Mountain View",
        "Johnson & Johnson": "New Brunswick",
        "Apple": "Cupertino"
}

words = "Where is Johnson & Johnson based out of?".rstrip("?").split()

#find the max number of words in a key
len_max = max([len(s.split()) for s in items])

#split the sentence in consecutive words according to the maximum number of words in a key, i.e., in consecutive groups of size 1,2,...,len_max_words_in_key
to_check = [" ".join(words[i:i+j]) for j in range(1,len_max + 1) for i in range(0,len(words)+1-j)]


#check for the key
for el in to_check:
     if el in items:
        print("Key found. Value is = {}".format(items[el]))

Поскольку предложения короткие, количество проверок, которые необходимо выполнить, невелико.
Например, для предложения, составленного из 20 слов, и ключа, состоящего из максимум 5 слов, у вас есть 90 = (20 + 19 + 18 + 17 + 16) проверок в словаре, которые необходимо выполнить.

Answer 4

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

Первый шаг алгоритма предварительно обрабатывает строки в вашем словаре, и это делается только один раз, независимо от входной строки, в O(m) времени и пространстве, где m - сумма длин ключей в словарь.

Затем алгоритм найдет все вхождения во входной строке в O(n + m + k), где n - длина входной строки, а k - общее количество вхождений любого ключа в качестве подстроки входной строки.

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