0

这与 stackoverflow 上的大多数 trie 问题有点不同（是的，我已经花时间搜索和阅读），所以请多多包涵。

我有文件 A，其中包含以下词：allow*、apolog* 等。总共有数万个这样的条目。我的文件 B 包含一段文本，最多有数千个单词。我希望能够将文件 B 中的文本中的单词与文件 A 中的单词匹配。

例子：

文件 B 的“道歉”将匹配文件 A 的“道歉*”

文件 B 的 "a" 既不匹配 "allow*" 也不匹配 "apolog*"

文件 B 的“apologizetomenoworelseiwillkillyou”也将匹配文件 A 的“道歉*”

任何人都可以建议一种算法/数据结构（最好在 python 中可行）可以帮助我实现这一目标吗？我研究过的尝试似乎更多是关于将前缀与整个单词匹配，但在这里，我将整个单词与前缀匹配。词干算法是不可能的，因为它们有固定的规则，而在这种情况下，我的后缀可以是任何东西。我不想遍历文件 A 中的整个列表，因为那会花费太多时间。

如果这令人困惑，我很乐意澄清。谢谢。

4

4 回答 4

1

将所有前缀放入哈希表中。然后取出 B 中的每个单词并在哈希表中查找它的所有前缀。你得到的任何命中都表示匹配。

所以哈希表将包含“允许”和“道歉”。对于“apologize”，您会查找“a”然后是“ap”，依此类推，直到您查找“apolog”并找到匹配项。

于 2012-08-03T04:34:47.347 回答
1

如果 FILE B 中的单词数远大于 FILE A 中的前缀，也可以构建前缀的 Trie 并匹配其中的单词。

如果您了解 Trie 的工作方式，将会容易得多。Trie 是由字符串构建的树，如下所示。在 Trie 中匹配字符串是从根走到其中一个叶子的过程。

在您的问题中，如果我们将前缀放在 Trie 中，并查找单词，我们将需要将 Trie 中的一些内部节点标记为前缀的终止。当我们在 Trie 中查找一个单词时，每次我们到达一个标记为前缀终止的节点时，我们都会将该前缀作为“匹配”添加到单词中。（然后我们继续下一个字母）。

这正是@Blckknght 解决方案的逆向解决方案。哪个更有效取决于 FILE A 和 FILE B 中哪个更大。

在@Blckknght 的解决方案中，Trie 中的每个节点都由包含该节点的单词集（其路径）标记。前缀的搜索在前缀的最后一个字母处结束。当它停止时，我们获取搜索停止的 Trie 节点，然后我们将节点上标记为匹配的集合添加到前缀。

如果对任何人有帮助，我会写一些伪代码。

来自wiki的Trie，您可以从中找到“算法”部分的一些代码

在此处输入图像描述

于 2012-08-03T08:18:49.913 回答
1

如果我了解您要查找的内容，您希望能够查看文件 A 中与文件 B 中的给定完整单词匹配的所有前缀。 trie 数据结构可让您将单个前缀与完整单词列表匹配，但你需要去另一个方向。

如果是这样，您可能仍然使用 trie 进行匹配，使用查找表来反转结果。这是算法：

  • 遍历文件 B 中的单词，将它们放入 trie 中。
  • 遍历文件 A 中的前缀，从 trie 中找到匹配项。
    • 对于每个匹配项，将前缀添加到由匹配词索引的列表字典中。

这是一些实现该算法的代码。您需要作为参数传入的 trie 类和Trieiterables （如果您不希望所有值同时在内存中，请使用生成器）：wordsprefixes

def matchPrefixes(words, prefixes):
    """Returns a word-to-prefix lookup table."""

    trie = Trie()
    for word in words:
        trie.add(word)

    lookupTable = defaultdict(list)
    for prefix in prefixes:
        matchedWords = trie.matchPrefix(prefix)

        for word in matchedWords:
            lookupTable[word].append(prefix)

    return lookupTable

这在时间和内存上都应该非常有效，尤其是当单词列表比前缀列表短得多时。与任何单词不匹配的前缀在与 trie 进行检查后将不会使用任何内存。

于 2012-08-03T06:54:18.850 回答
1

假设您在每个文件中有 100,000 个单词。

排序 = n*log(n) 二进制搜索查找 = log(n)

所以这是更糟糕的情况 n*log(n)

这是 100, 000 * log(100, 000) = 100,000 * 11 = 10^6 = 几乎瞬间

我认为你不需要对这么小的文件有任何花哨的东西。简单的排序和二进制搜索：

__author__ = 'Robert'

from bisect import bisect_right

file_a = """hell*
wor*
howard*
are*
yo*
all*
to*""".splitlines()

file_b = """hello world how are you all today too told town""".split()

a_starts = sorted(word[:-1] for word in file_a) #can do this easily if only 100, 000 words as you say.

def match(word):
    pos = bisect_right(a_starts, word)
    #assert 0 <= pos < len(a_starts)
    matched_word = a_starts[pos - 1]
    return matched_word if word.startswith(matched_word) else None

for word in file_b:
    print(word, " -> ", match(word))

"""
hello  ->  hell
world  ->  wor
how  ->  None
are  ->  are
you  ->  yo
all  ->  all
today  ->  to
too  ->  to
told  ->  to
town  ->  to
"""
于 2012-08-03T09:12:43.847 回答