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

Question

如何在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，它丑陋的大 :(

Answer 1

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

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

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

考虑到这两个限制，最大的问题是您需要次线性搜索时间吗？

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

• 将每个词典单词的字符按字母顺序排序。
• 将查询的字符按字母顺序排序
• 对排序词典中的每个单词进行排序查询的序列比较。

也就是说，假设你有词典

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的最长公共(public)子序列> 而ACDEEORT是OT，只有两个。

假设单词都是短的，我们知道最长公共(public)子序列问题和排序一串字符问题可以很快解决。您只需执行 4000 万次即可。

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