Оптимизировать предложение, содержащее все данные фразы

Question

Я читаю документ GeeksforGeeks. Есть одна проблема, Sentence that contains all the given phrases.

Подробности ниже: Приведен список предложений и список фраз. Задача состоит в том, чтобы найти, какие предложения содержат все слова фразы, и для каждой фразы выведите номер предложения, который содержит данную фразу.

Например: Ввод:

sent = ["Strings are an array of characters", 
    "Sentences are an array of words"] 
ph = ["an array of", "sentences are strings"]

Выход:

Phrase1:
1 2
Phrase2:
NONE

Код:

# Python program to find the sentence 
# that contains all the given phrases  
def getRes(sent, ph): 
    sentHash = dict() 

    # Loop for adding hased sentences to sentHash 
    for s in range(1, len(sent)+1): 
        sentHash[s] = set(sent[s-1].split()) 

    # For Each Phrase 
    for p in range(0, len(ph)): 
        print("Phrase"+str(p + 1)+":") 

        # Get the list of Words 
        wordList = ph[p].split() 
        res = [] 

        # Then Check in every Sentence 
        for s in range(1, len(sentHash)+1): 
            wCount = len(wordList) 

            # Every word in the Phrase 
            for w in wordList: 
                if w in sentHash[s]: 
                    wCount -= 1

            # If every word in phrase matches 
            if wCount == 0: 

            # add Sentence Index to result Array 
                res.append(s) 
        if(len(res) == 0): 
            print("NONE") 
        else: 
            print('% s' % ' '.join(map(str, res))) 

# Driver Function 
def main(): 
    sent = ["Strings are an array of characters", 
    "Sentences are an array of words"] 
    ph = ["an array of", "sentences are strings"] 
    getRes(sent, ph) 

main() 

Это правильно. Но мне интересно, как оптимизировать ответ, чтобы уменьшить сложность времени или просто заставить его работать быстрее. Я также решаю подобную проблему, поэтому я и спрашиваю. Большое спасибо, если вы могли бы помочь мне.

Answer 1

Ваш текущий алгоритм работает примерно за O (| sent | * | фразу | * k), где k - это среднее количество слов в предложении. Ответ Патрика сводит это k к среднему количеству слов в фразе, которое в вашем случае должно быть меньше 10, так что это большое улучшение.

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

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

from collections import Counter
from collections import defaultdict

def containsQty(sentence, phrase):
    qty = 100000
    for word in phrase:
        qty = min(qty, int(sentence[word] / phrase[word]))
        if qty == 0:
            break
    return qty

sent = ["bob and alice like to text each other", "bob does not like to ski but does not like to fall", "alice likes to ski"] 
ph = ["bob alice", "alice", "like"]

sent = [Counter(word.lower() for word in sentence.split()) for sentence in sent]
ph   = [Counter(word.lower() for word in sentence.split()) for sentence in ph]

indexByWords = defaultdict(list)

for index, counter in enumerate(sent, start = 1):
    for word in counter.keys():
        indexByWords[word].append(index)


for i, phrase in enumerate(ph, start=1):
    print("Phrase{}:".format(i))

    best = None
    minQty = len(sent) + 1
    for word in phrase.keys():
        if minQty > len(indexByWords[word]):
            minQty = len(indexByWords[word])
            best = indexByWords[word]

    matched = False
    for index in best:
        qty = containsQty(sent[index - 1], phrase)
        if qty > 0:
            matched = True
            print((str(index) + ' ') * qty)
    if not matched:
        print("NONE")

Answer 2

Вы можете значительно упростить свою логику, используя класс Counter из модуля collections:

from collections import Counter

def contains(sentence, phrase):
    return all(sentence[word] >= phrase[word] for word in phrase)

sent = ["Strings are an array of characters", 
        "Sentences are an array of words"] 
ph = ["an array of", "sentences are strings"]

sent = [Counter(word.lower() for word in sentence.split()) for sentence in sent]
ph   = [Counter(word.lower() for word in sentence.split()) for sentence in ph]

for i, phrase in enumerate(ph, start=1):
    print("Phrase{}:".format(i))
    matches = [j for j, sentence in enumerate(sent, start=1) if contains(sentence, phrase)]
    if not matches:
        print("NONE")
    else:
        print(*matches)

Это позволяет нам рассчитывать количество каждого слова в каждом предложении один раз, а не один раз для каждой фразы.