c# - 如何在 4000 万字的列表中快速搜索？

如何在包含 4000 万个单词的列表中快速搜索？

我需要找到包含至少 4 个我在继续之前指定的字母的单词。

示例:在列表中有几个词:

dogging
dopping
baobabisaneviltree

我的字符串格式“odxxini”中的特定字母。我需要从我的字符串中找到包含任何 (4+) 个字符的任何单词。

结果:

dopping
dogging

(因为，这两个词都包含 'o' 'd' 'i' 'n')
我希望我解释得很好。对不起英语。请纠正错误。

如果有人对这个问题有任何了解，我会很高兴听到他的消息。 :)

到目前为止我写了(因为它是开始..)这段代码:

private void seeksearcher()
        {
            double counter = 0, k=0;
            double licznik = (double)listwords.Capacity;

            char[] letterarray = stringletters.ToCharArray();
            foreach(String word in listwords)
            {

                for(int i=0;i<letterarray.Length;i++)
                    if(word.Contains(letterarray[i]))
                        counter++;
                if(counter > 4)
                    textBox2.Text+=word + Environment.NewLine;

            }
        }

我很确定现在的复杂性是 n*7n，它丑陋的大:(

最佳答案

首先，显然没有解决方案比解决方案集的大小更快。如果您碰巧有一个匹配词典中每个单词的搜索字符串，那么枚举解决方案集需要枚举词典。

假设与词典的大小相比，每个解决方案集的大小都非常小。

我们还假设词典中每个条目的大小都很短；你那里没有任何一万个字母的单词或类似的东西。

鉴于这两个限制，最大的问题是您是否需要次线性搜索时间？

线性时间算法很简单。例如:

将每个词典单词的字符按字母顺序排序。

将查询的字符按字母顺序排序

对已排序查询与已排序词典中的每个单词进行序列比较。

也就是说，假设你有词典

STOPPING
POTSHARD
OPTING
DECORATE

和查询 TOPSXZ 。按字符对查询进行排序: OPSTXZ 。现在浏览词典，按字符排序:

STOPPING --> GINOPPST
POTSHARD --> ADHOPRST
OPTING   --> GINOPT
DECORATE --> ACDEEORT

现在很容易判断您是否有四个或更多匹配项；你只是在 OPSTXZ 和 GINOPPST 上运行最长公共(public)子序列算法，发现最长公共(public)子序列是 OPST ，它是四个字母，所以它匹配。 OPSTXZ 和 ADHOPRST 的最长公共(public)子序列也是 OPST ，所以匹配。 OPSTXY 和 GINOPT 的最长公共(public)子序列是 OPT ，只有三个，而 OPSTXY 和 ACDEEORT 的最长公共(public)子序列是 OT ，只有两个。

假设单词都是短的，我们知道最长公共(public)子序列问题和Sort A Bunch of Characters问题可以很快解决。你只需要做 4000 万次就完成了。

现在，如果你想要一个次线性的解决方案，在这个解决方案中你尽早从考虑中消除这 4000 万个词典单词中的一堆，那会更难。您需要次线性解决方案吗？

关于c# - 如何在 4000 万字的列表中快速搜索？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5810811/