1

我正在用 C# 构建一个自然语言处理器，我们数据库中的许多“单词”实际上是指一个名词或动作的多词短语。请不要讨论这个设计调用，只要说它目前不可更改就足够了。我有我需要测试这些短语和单词的句子相关单词（块）的字符串数组。 什么是处理子数组提取的适当惯用方法，因此我运行溢出错误等的风险最小？

为了给出所需逻辑的示例，让我逐步使用示例块进行运行。出于我们的目的，假设数据库中唯一的多词短语是“quick brown”。

Full phrase: The quick brown fox -> encoded as {"The", "quick", "brown", "fox"}
First iteration: Test "The quick brown fox" -> returns nothing
Second iteration: Test "The quick brown" -> returns nothing
Third iteration: Test "The quick" -> returns nothing
Fourth iteration: Test "The" -> returns value
Fifth iteration: Test "quick brown fox" -> returns nothing
Sixth iteration: Test "quick brown" -> returns value
Seventh iteration: Test "fox" -> returns value

Sum all returned values and return.

我对如何解决这个问题有一些想法，但我越是关注事情，我就越担心数组寻址错误和其他困扰我的代码的恐怖事件。该短语以字符串数组的形式出现，但我可以将其放入 IEnumerable。我唯一担心的是 Enumerable 缺少索引。

4

4 回答 4

2

这听起来像是 Aho-Corasick 字符串匹配算法的完美应用。我有一本包含大约 1000 万个短语的字典，我可以在这些短语中运行短字符串。它非常快。只需通过一次，它就会告诉您所有匹配的短语。因此，如果“the”、“fox”和“quick brown”都在字典中，则单次传递将返回所有三个索引。

这很容易实现。在网上找到原论文，一个下午就可以完成。

高效的字符串匹配：书目检索的辅助工具

于 2011-08-15T20:43:27.183 回答
1

会ArraySegment或有DelimitedArray帮助吗？

于 2011-08-15T20:40:10.503 回答
1

像这样的东西怎么样：

    string[] words = new string[] { "The", "quick", "brown", "fox" };

    for (int start = 0; start < words.Length - 2; start++) // at least one word
    {
        for (int end = start + 1; end < words.Length - 1; end++)
        {
            ArraySegment<string> segment = new ArraySegment<string>(words, start, end - start);
            // test segment
        }
    }

这假设您可以使用 ArraySegment 段进行测试。

于 2011-08-15T20:48:06.843 回答
0

前进的道路在于结合马克和菲利普的答案。在理想情况下，我会用它编辑他们的一篇文章，但看起来我的编辑被拒绝了。

无论如何，我使用了 Mark 链接的 DelimitedArray 并在其中更改了一些内容：

构造函数更改为：

    public DelimitedArray(T[] array, int offset, int count, bool throwErrors = false)
    {
        this.array = array;
        this.offset = offset;
        this.count = count;
        this.throwErrors = throwErrors;
    }

索引参考更改为：

public T this[int index]
    {
        get
        {
            int idx = this.offset + index;
            if (idx > this.Count - 1 || idx < 0)
            {
                if (throwErrors == true)
                    throw new IndexOutOfRangeException("Index '" + idx + "' was outside the bounds of the array.");
                return default(T);
            }
            return this.array[idx];
        }
    }

然后我将其用于 Philipp 的循环使用。这变成：

        for (var start = 0; start < words.Length - 2; start++) // at least one word
        {
            for (var end = start + 1; end < words.Length - 1; end++)
            {
                var segment = new DelimitedArray<string>(words, start, end - start);
                lemma = string.Join(" ", segment.GetEnumerator()); // get the word/phrase to test
                result = this.DoTheTest(lemma);

                if (result > 0)
                {
                    // Add the new result
                    ret = ret + result;

                    // Move the start sentinel up, mindful of the +1 that will happen at the end of the loop
                    start = start + segment.Count - 1;
                    // And instantly finish the end sentinel; we're done here.
                    end = words.Length;
                }
            }
        }

如果我可以接受多个答案，我会标记他们的两个答案，但由于它们都不完整，我必须在明天能够接受时接受我自己的答案。

于 2011-08-16T14:07:56.330 回答