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

Question

Задача

По заданному списку строк найдите строки из списка, которые появляются в данном тексте.

Пример

list = ['red', 'hello', 'how are you', 'hey', 'deployed']
text = 'hello, This is shared right? how are you doing tonight'
result = ['red', 'how are you', 'hello']

'red', потому что у него 'shared' есть 'red' в качестве подстроки

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

Решение

• Я строю дерево из списка слов
• Запустите dfs для текста и проверьте текущее слово по дереву

псевдопользователей-код

def FindWord (trie, text, word_so_far, index):
    index > len(text)
        return
    //Check if the word_so_far is a prefix of a key; if not return
    if trie.has_subtrie(word) == false:
       return 
    //Check if the word_so_far is a key; if ye add to result and look further 
    if trie.has_key(word) == false:
        // Add to result and continue
    //extend the current word we are searching
    FindWord (trie, text, word_so_far + text[index], index + 1)
    //start new from the next index 
    FindWord (trie, text, "", index + 1)

Проблема в том, что время выполнения теперь зависит от len(text), которое выполняется с временной сложностью O(2^n) после построения дерева, которое является единовременным для нескольких текстов, так что все в порядке.

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

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

Answer 1

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

def getAllWindows(L):
    tracker = set()
    for w in range(1, len(L)+1):
        for i in range(len(L)-w+1):
            sub_window = L[i:i+w]
            if sub_window not in tracker:
                tracker.add(sub_window)
                yield sub_window


lookup_list = ['red', 'hello', 'how are you', 'hey', 'deployed']
lookup_set = set(lookup_list)
text = 'hello, This is shared right? how are you doing tonight'
result = [sub_window for sub_window in getAllWindows(text) if sub_window in lookup_list]
print(result)
#Output:
['red', 'hello', 'how are you']

Answer 2

Расширение предложения @David Eisenstat для реализации этого с использованием алгоритма aho-corasick. Я нашел простой модуль Python ( pyahocorasic ), который может сделать это.

вот как будет выглядеть код для примера, приведенного в вопросе.

import ahocorasick

def find_words(list_words, text):
    A = ahocorasick.Automaton()

    for key in list_words:
      A.add_word(key, key)

    A.make_automaton()

    result = []
    for end_index, original_value in A.iter(text):
      result.append(original_value)

    return result

list_words = ['red', 'hello', 'how are you', 'hey', 'deployed']
text = 'hello, This is shared right? how are you doing tonight'
print(find_words(list_words, text))

Или запустите онлайн

Answer 3

Теоретически обоснованная версия того, что вы пытаетесь сделать, называется Aho - Corasick .Реализация суффиксных ссылок является довольно сложной задачей IIRC, так что вот алгоритм, который просто использует три.

Мы используем текст буква за буквой.Мы всегда поддерживаем набор узлов в дереве, где может быть проход.Первоначально этот набор состоит только из корневого узла.Для каждой буквы мы перебираем узлы в наборе, спускаясь по новой букве, если это возможно.Если полученный узел совпадает, замечательно, сообщите об этом.Независимо от этого, поместите его в следующий набор.Следующий набор также содержит корневой узел, так как мы можем начать новое совпадение в любое время.

Вот моя попытка быстрой реализации на Python (без проверки, без гарантии и т. Д.).

class Trie:
    def __init__(self):
        self.is_needle = False
        self._children = {}

    def find(self, text):
        node = self
        for c in text:
            node = node._children.get(c)
            if node is None:
                break
        return node

    def insert(self, needle):
        node = self
        for c in needle:
            node = node._children.setdefault(c, Trie())
        node.is_needle = True


def count_matches(needles, text):
    root = Trie()
    for needle in needles:
        root.insert(needle)
    nodes = [root]
    count = 0
    for c in text:
        next_nodes = [root]
        for node in nodes:
            next_node = node.find(c)
            if next_node is not None:
                count += next_node.is_needle
                next_nodes.append(next_node)
        nodes = next_nodes
    return count


print(
    count_matches(['red', 'hello', 'how are you', 'hey', 'deployed'],
                  'hello, This is shared right? how are you doing tonight'))