3

有一股字流传来，非常大。随着单词不断出现，可以询问是否在已经看到的流中出现了一个短语？在不同的时间可能有多个这样的查询。

例如，假设到目前为止看到的单词流是：

hello world 这里是另一个程序员

然后，它被要求判断该短语是否here is another已被看到，在这种情况下是正确的。

如何以最佳方式返回这个？

我一直在尝试使用图形构造并在查询时执行 BFS 来解决解决方案，但这会带来两个问题：

  • 首先，为了达到最佳效果，我还必须将图对中节点的单词 => 地址存储在哈希表中。

  • 其次，当有循环时，算法在流中失败：a b c d a b c e

针对需求提出最佳解决方案。

4

2 回答 2

1

您可以查找“后缀树的在线构建”并找到 Ukkonen 的算法，该算法处理流并且在处理每个字符后始终为您的流准备好后缀树，如果您运行时间和空间为 O(n)到目前为止已经看过n个字符。然后，每次给定一个查询短语时，您可以使用后缀树的子字符串匹配算法来查找给定查询短语的所有匹配项，如果您的查询短语有长度，则查询时间是最佳 O(m) 来找到匹配项米。

于 2013-07-14T19:20:13.440 回答
1

因为您正在接收要以流式方式搜索的文本正文，所以“预处理”文本以进行更有效的搜索是没有意义的。这是 C# 中的一个有效实现，它以流方式处理要搜索的文本。

static IEnumerable<int> Search(string text, string query)
{
    var D = new Dictionary<int, int>();
    //Loop invariant: D[i] == j iff text[i..(i+j)] == query[0..j]
    //                for all pairs (i,j) in D
    for (int i = 0; i < text.Length; i++)
    {
        foreach (var k in D.Keys.ToList())
        {
            D[k] = D[k] + 1;
            if (D[k] == query.Length)
            {
                yield return k;
                D.Remove(k);
            }
            else if (text[i] != query[D[k]])
            {
                D.Remove(k);
            }
        }
        if (text[i] == query[0])
            D.Add(i, 0);
    }
    foreach (var k in D.Keys)
    {
        if (D[k] == query.Length)
            yield return k;
    }
}

基于流的版本可以如下实现。我认为可能无法正确处理流结束的情况，但是您应该能够使该想法适应即使在这种边缘情况下也有效的东西。

class SearcherState
{
    public Dictionary<int, int> D = new Dictionary<int, int>();
    public int i = 0;
}

static Func<char, int?> Searcher(string query)
{
    var state = new SearcherState();
    return c =>
    {
        int? result = null;
        foreach (var k in state.D.Keys.ToList())
        {
            state.D[k] = state.D[k] + 1;
            if (state.D[k] == query.Length)
            {
                result = k;
                state.D.Remove(k);
            }
            else if (c != query[state.D[k]])
            {
                state.D.Remove(k);
            }
        }
        if (c == query[0])
            state.D.Add(state.i, 0);
        state.i++;
        return result;
    };
}
于 2013-07-14T19:46:24.013 回答