代码之家 › 专栏 › 技术社区 › thebenman

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

trie search algorithm python

thebenman · 技术社区 · 7 年前

问题

给定一个字符串列表,从出现在给定文本中的列表中查找字符串。

例子

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”

这和 this question 但我们需要查找的单词也可以是子字符串。
列表非常大,并且随着用户数量的增加而增加,而文本的长度几乎相同。
我正在考虑一个解决方案,其中时间复杂性取决于文本的长度,而不是单词列表,这样即使添加了大量用户,它也可以扩展。

解决方案

我从给出的单词列表中创建一个trie
对文本运行df并对照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之后,它对于多个文本来说是一次性的,所以很好。

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

你能给我任何建议吗,我可以实现一个运行时,它取决于给定的文本,而不是单词列表,它可以被每次处理和缓存,而且比这更快。

4 回复 | 直到 7 年前

David Eisenstat 7 年前

理论上讲,你想做的事情是正确的 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'))

nice_dev 7 年前

如果您的目标是获得一个依赖于文本窗口的更快的代码,那么您可以使用设置查找来加快速度。如果可行,将查找列表改为集合,然后在文本中查找用于查找的所有可能窗口。

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

X 47 48 - IR 7 年前

嗯,这个怎么样?简单易懂:d

import re

def WordsInText(text, words):
    found = []
    for index, item in enumerate(words):
        if (re.search(f'{item}', text, re.IGNORECASE) is not None):
            found.append(item)
    return found

thebenman 7 年前

扩展@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))

Or run it online