给定一个单词列表和一个句子,找到整个句子中出现的所有单词或作为子串

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'因为'共享'有'红色'作为子串

• 这与这个问题非常相似,只是我们需要查找的单词也可以是子字符串.
• 该列表非常大,随着用户数量的增加而增加,而文本的长度几乎相同.
• 我正在考虑一个解决方案,时间复杂度取决于文本的长度而不是单词列表,这样即使添加了大量用户,它也可以扩展.

解

• 我从给出的单词列表中构建了一个trie
• 在文本上运行dfs并检查当前单词与trie

伪代码

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)在构建trie之后以时间复杂度运行,这对于多个文本来说是一次性的事情所以它很好.

我没有看到任何重叠的子问题来记忆和改善运行时.

您是否可以建议我可以实现依赖于给定文本的运行时,而不是可以进行处理和缓存的单词列表,并且速度也更快.

Answer 1

您正在尝试做的事情的理论上合理的版本称为Aho--Corasick。实现后缀链接有点复杂 IIRC，因此这里有一个仅使用 trie 的算法。

我们逐个字母地阅读文本。我们始终在 trie 中维护一组可以进行遍历的节点。最初该集合仅包含根节点。对于每个字母，我们循环遍历集合中的节点，如果可能的话，按新字母递减。如果结果节点匹配，那就太好了，报告它。无论如何，将其放入下一组。下一组还包含根节点，因为我们可以随时开始新的匹配。

这是我在 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'))