如何在4000万字列表中快速搜索

本文关键字：搜索 列表 4000万 | 更新日期: 2023-09-27 17:53:13

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

如何在4000万字列表中快速搜索

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

让我们假设每个解集的大小与词典的大小相比都非常小。

我们还假设字典中每个条目的长度都很短;你不会在里面有任何10000个字母的单词或类似的愚蠢的东西。

给定这两个约束条件，最大的问题是是否需要次线性搜索时间?

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

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

也就是说，假设您有字典

STOPPING
POTSHARD
OPTING
DECORATE

和查询TOPSXZ。按字符排序:OPSTXZ。现在遍历字典，按字符排序:

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

现在很容易判断你是否有四个或更多的匹配;你只要在OPSTXZ和GINOPPST上运行最长公共子序列算法，就会发现最长公共子序列是OPST，它有四个字母，所以它是匹配的。OPSTXZ和ADHOPRST的最长公共子序列也是OPST，所以它是匹配的。OPSTXY和GINOPT的最长公共子序列是OPT，只有3个;OPSTXY和ACDEEORT的最长公共子序列是OT，只有2个。

假设单词都很短，我们知道最长公共子序列问题和排序一堆字符问题可以快速解决。你只需要做4000万次，你就完成了。

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

有很多方法可以解决这个问题，但是在我看来，您可能必须使用某种索引系统。这些索引占用的内存与单词本身一样多，甚至可能多得多。

例如，您可能有指向所有包含字母d的单词的指针，然后指向所有包含字母o的单词的指针，等等。然后你得到一个更小的列表，你可以更容易地通过找到你的字母的交集来搜索(单词中包含所有你需要的字母)。

当然，这只是打乱了工作，使得它需要大量的处理，而不是在搜索时。

你能提前把单词编入索引吗?我将首先索引单词列表，为每个字符创建一个有序的单词列表:

a: baobabisaneviltree
b: baobabisaneviltree
c: 
d: dogging, dopping
e: etc

然后，对于输入字符串中的每个字母，我将收集匹配的单词，将它们放入字典中，并增加每个单词被找到的次数。

dogging: 4
dopping: 4
dapper: 1

然后遍历字典查找大于4的数字。

如果你不能索引，那么你的解决方案是最好的。你必须查看每个单词中的每个字母(O(n*m))，看看给定的字母是否出现在一个单词中，然后你需要检查每个字母。您的解决方案的一个问题是，您将多次向文本框中添加单词，您可能希望将其设置为if(counter == 4)。

代码乐趣(未测试):

// With 40 million words this can use a lot of space.  You would probably
// want to create the index on disk and maybe the intermediate processing
// as well.
var index = wordList.SelectMany(word => word.ToCharArray(), 
                                (word, character) => 
                                  new { word, character})
                    .ToLookup(x => x.character, x => x.word);
var result = letterArray.Distinct()
                        .SelectMany(c => index[c])
                        .GroupBy(word => word)
                        .Where(word => word.Count() > 4)
                        .Select(word => word.Key);
相关文章：