给定一个单词列表和一个句子，找出所有在句子中出现过的单词，无论是完整单词还是作为子字符串出现的。

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'且'shared'是'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)，但是在构建Trie后，它的时间复杂度为O(2^n)，这是一次性的多个文本也可以，所以没问题。

我也没有看到任何重叠的子问题可以进行记忆化并提高运行时间。

你能否建议一种方式，可以实现根据给定文本而不是单词列表进行运行时，并且可以对其进行预处理和缓存，比这个还要更快。

- thebenman

---

你尝试过什么？你有自己的工作代码示例吗？ - Jordan Singer

我已经发布了我所做的伪代码。实际代码有很多无关部分，可能会分散注意力，影响到实际问题。 - thebenman

@JordanSinger已经对他的尝试做了相当信息丰富的描述，因此无需发布实际代码，因为实际问题在于算法。 - meowgoesthedog

你有多经常在相同的索引处递归重新开始？（或以其他方式复制以前需要重新执行大量工作的起始点）也许可以基于元组键（word_so_far，index）创建一个计数器来查看是否发生了这种情况。 - Kenny Ostrom

Answer 1

你尝试做的理论上正确的方法被称为Aho--Corasick。如果我没记错，实现后缀链接有点复杂，因此这里提供了一个仅使用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'))

- David Eisenstat

---

Trie解决方案的最坏时间复杂度会是多少呢？有n^2个子字符串，每个子字符串在Trie中的查找都是线性时间。所以是O(n^3)吗？ - thebenman

@thebenman 你可能已经有了一个退化的trie，包含a，aa，aaa，aaaa等等。但是这只会将其推向trie大小乘以文本大小的程度（二次方）。 - David Eisenstat

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))

或者在线运行

- thebenman

Answer 3

如果你想要一个更快的代码，依赖于文本窗口，你可以选择使用集合查找来加速。如果可行的话，将查找列表改为集合，然后在文本中找到所有可能用于查找的窗口。

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

- Paritosh Singh