我在我的应用程序中有一个存储了大约10万个字符串的列表。我需要找到包含特定关键词（不区分大小写）的前20个字符串。这很容易做到，我只需运行以下LINQ代码：
from s in stringList
where s.ToLower().Contains(searchWord.ToLower())
select s
然而，我有一种强烈的感觉，我可以更快地完成这项任务，我需要找到方法，因为我需要每秒多次查阅此列表。
在C#中搜索名字列表的最快方法
3
- Niels Brinch
7
4个回答
4
找到子字符串（而不是完全匹配）非常困难。没有内置的方法可以帮助您解决这个问题。我建议您研究后缀树数据结构，它可以有效地用于查找子字符串。
顺便说一下，您可以将
您还可以在查询上添加.AsParallel。
顺便说一下，您可以将
searchWord.ToLower()提取到本地变量中以节省大量的字符串操作。您还可以预先计算stringList的小写版本。如果无法预先计算，请至少使用s.IndexOf(searchWord, StringComparison.InvariantCultureIgnoreCase) != -1。这可以节省昂贵的ToLower调用。您还可以在查询上添加.AsParallel。
- usr
7
谢谢。创建小写字符串列表是个好主意，我会实现的。我本来希望有另一个更好的方法来实现这个，但对我的解决方案进行微调也不错。谢谢。 - Niels Brinch
我刚查了一下 Trie，看起来正是我需要的。甚至还找到有人已经为我实现了它！ :) http://geekyisawesome.blogspot.com/2010/07/c-trie.html - Niels Brinch
Trie 无法解决包含相同字符 'a' 的 100,000 个字符串的问题。对于大多数字符串，您的 Trie 将具有 100,000 个子节点，这些子节点将形成某些短路径。这仍然是相同的反向索引方法。 - Daniel Baktiar
Trie 的成本与输入大小呈线性关系，而非二次方关系。 - usr
嗨usr，不要仅仅按照教科书上的内容：“Trie的成本与输入大小成线性关系，但仅在您从第一个字符开始索引时才是如此”。但是，如果您索引单词内部任何序列出现，它仍将是组合的，因为输入大小是预生成的。
例如，如果单词是“abcd”，“bce”，“ghibc”。如果您仅使用Trie来识别“ab*”，那么是的。但是，如果您想索引“*bc*”，则仍然需要完全扫描或通过组合爆炸进行预索引。 - Daniel Baktiar
显示剩余2条评论
1
另一个选择是预先计算类似于后缀数组（按指向的字符串排序的位置列表）这样的东西，但这需要相当数量的内存。
http://en.wikipedia.org/wiki/Suffix_array
如果你要搜索的字符串列表相对静态，那么这种方法是最可行的。整个字符串索引列表可以存储在一个元组数组(indexOfString, positionInString)中，然后使用 String.Compare(keyword, 0, target, targetPos, keyword.Length) 进行二分查找。
所以，如果你有100,000个平均长度为20的字符串，你需要100,000 * 20 * 2*sizeof(int) 的内存来存储这个结构。你可以通过将indexOfString和positionInString打包成一个32位整数来减少一半的内存使用量，例如将positionInString放在最低的12位中，将indexOfString放在剩余的高位中。你只需要做一点点调整就可以得到这两个值。重要的是要注意，该结构本身不包含任何字符串或子字符串。你要搜索的字符串仅存在一次。
这基本上给你提供了一个完整的索引，并允许非常快速地查找任何子字符串(在后缀数组表示的索引上进行二分查找)，并且实际的字符串比较最小化。
如果内存很昂贵，那么对原始暴力算法进行简单优化的方法是预先计算一个唯一字符的字典，并分配序数来表示每个字符。然后为每个字符串预先计算一个位数组，其中设置了包含在字符串中的每个唯一字符的位。由于您的字符串相对较短，所以结果的BitArrays应该有相当多的变化（如果您的字符串非常长，则不会很好地工作）。然后只需计算搜索关键字的BitArray，并仅在那些keywordBits & targetBits == keywordBits的字符串中搜索关键字。如果您的字符串已经转换为小写，并且只使用英文字母，则BitArray可能适合单个int中。因此，这将需要最少的额外内存，易于实现，并且可以让您快速过滤掉绝对找不到关键字的字符串。由于字符串搜索速度很快，但您需要使用暴力搜索进行大量搜索，因此这可能是一种有用的优化。
编辑 对于那些有兴趣的人，这里是我提出的初步解决方案的基本实现。我使用由OP描述的长度随机生成了100,000个字符串并进行了测试。虽然构建和排序索引需要大约30秒的时间，但一旦完成，使用暴力搜索关键字3000次的速度为49,805毫秒，使用索引搜索速度为18毫秒，快了几千倍。如果您很少构建列表，那么最初构建后缀数组的简单但相对缓慢的方法应该足够了。有更聪明的构建方法可以更快地构建它，但需要比我下面的基本实现更多的编码。// little test console app
static void Main(string[] args) {
var list = new SearchStringList(true);
list.Add("Now is the time");
list.Add("for all good men");
list.Add("Time now for something");
list.Add("something completely different");
while (true) {
string keyword = Console.ReadLine();
if (keyword.Length == 0) break;
foreach (var pos in list.FindAll(keyword)) {
Console.WriteLine(pos.ToString() + " =>" + list[pos.ListIndex]);
}
}
}
~~~~~~~~~~~~~~~~~~
// file for the class that implements a simple suffix array
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1 {
public class SearchStringList {
private List<string> strings = new List<string>();
private List<StringPosition> positions = new List<StringPosition>();
private bool dirty = false;
private readonly bool ignoreCase = true;
public SearchStringList(bool ignoreCase) {
this.ignoreCase = ignoreCase;
}
public void Add(string s) {
if (s.Length > 255) throw new ArgumentOutOfRangeException("string too big.");
this.strings.Add(s);
this.dirty = true;
for (byte i = 0; i < s.Length; i++) this.positions.Add(new StringPosition(strings.Count-1, i));
}
public string this[int index] { get { return this.strings[index]; } }
public void EnsureSorted() {
if (dirty) {
this.positions.Sort(Compare);
this.dirty = false;
}
}
public IEnumerable<StringPosition> FindAll(string keyword) {
var idx = IndexOf(keyword);
while ((idx >= 0) && (idx < this.positions.Count)
&& (Compare(keyword, this.positions[idx]) == 0)) {
yield return this.positions[idx];
idx++;
}
}
private int IndexOf(string keyword) {
EnsureSorted();
// binary search
// When the keyword appears multiple times, this should
// point to the first match in positions. The following
// positions could be examined for additional matches
int minP = 0;
int maxP = this.positions.Count - 1;
while (maxP > minP) {
int midP = minP + ((maxP - minP) / 2);
if (Compare(keyword, this.positions[midP]) > 0) {
minP = midP + 1;
} else {
maxP = midP;
}
}
if ((maxP == minP) && (Compare(keyword, this.positions[minP]) == 0)) {
return minP;
} else {
return -1;
}
}
private int Compare(StringPosition pos1, StringPosition pos2) {
int len = Math.Max(this.strings[pos1.ListIndex].Length - pos1.StringIndex, this.strings[pos2.ListIndex].Length - pos2.StringIndex);
return String.Compare(strings[pos1.ListIndex], pos1.StringIndex, this.strings[pos2.ListIndex], pos2.StringIndex, len, ignoreCase);
}
private int Compare(string keyword, StringPosition pos2) {
return String.Compare(keyword, 0, this.strings[pos2.ListIndex], pos2.StringIndex, keyword.Length, this.ignoreCase);
}
// Packs index of string, and position within string into a single int. This is
// set up for strings no greater than 255 bytes. If longer strings are desired,
// the code for the constructor, and extracting ListIndex and StringIndex would
// need to be modified accordingly, taking bits from ListIndex and using them
// for StringIndex.
public struct StringPosition {
public static StringPosition NotFound = new StringPosition(-1, 0);
private readonly int position;
public StringPosition(int listIndex, byte stringIndex) {
this.position = (listIndex < 0) ? -1 : this.position = (listIndex << 8) | stringIndex;
}
public int ListIndex { get { return (this.position >= 0) ? (this.position >> 8) : -1; } }
public byte StringIndex { get { return (byte) (this.position & 0xFF); } }
public override string ToString() {
return ListIndex.ToString() + ":" + StringIndex;
}
}
}
}
- hatchet - done with SOverflow
11
那么它只返回一个匹配项，然后可以使用“暴力”方法来获取接下来的匹配项，直到不再匹配为止？ - Niels Brinch
@NielsBrinch - 在我的基本实现中，它返回第一个匹配项（指向匹配字符串的位置数组中的第一个元素）。但是，通过查看位置数组的后续元素，将StringPositions添加到结果中，直到找到第一个非匹配项，然后返回结果列表，很容易修改它以返回所有匹配项。这是因为位置按它们所指向的字符串排序，并且二进制搜索位置到第一个匹配项。 - hatchet - done with SOverflow
@NielsBrinch - 另外，我已经编辑了答案中的代码，允许指定是否要进行大小写敏感匹配，并且它将在不将所有字符串转换为小写的情况下尊重这一要求。 - hatchet - done with SOverflow
我从IndexOf方法中删除了EnsureSorted()调用，而是确保在向列表添加新字符串后调用它...似乎每次确保排序可能需要相当长的时间，对吧？ - Niels Brinch
嗯，它只能获取一条记录，因为下一个记录是按其首字母排序的，但搜索词可能在字符串的中间... - Niels Brinch
显示剩余6条评论
0
在这种情况下，您需要的是反向索引。
如果您愿意支付更多的费用，可以使用特定于数据库的全文搜索索引，并调整索引以在每个单词子集上进行索引。
或者，您可以使用一个非常成功的开源项目来实现相同的功能。
您需要使用分词器预先对字符串进行索引，并构建反向索引文件。我们在Java中有类似的用例，需要在大量数据集中拥有非常快速的自动完成。
您可以查看Lucene.NET，它是Apache Lucene（Java中的端口）。
如果您愿意放弃LINQ，则可以使用NHibernate Search。（眨眼）。
另一个选择是在内存中实现预索引，通过预处理和绕过扫描不需要的内容，可以查看Knuth-Morris-Pratt算法。
- Daniel Baktiar
4
嗨usr，关于数据库特定的问题，它是针对特定数据库的。对于Lucene，您可以自定义Lucene分词器以包含所有字符子集序列，这将产生更大的索引文件。 - Daniel Baktiar
1你确定吗？对于一个100个字符的字符串，这将产生大约5000个标记（二次方）！这是不切实际的。而且你不需要使用Lucene。只需使用字典即可。但正如我所说，可能的子字符串太多了。 - usr
你可以限制，例如只索引3个或更多字符。当出现重复时，索引仅生成一个条目。我同意必须进行一些权衡。 - Daniel Baktiar
啊，这正是我在另一个帖子中问过你的问题，连3个字符都一样。做得好，甚至在我提问之前就回答了 :) - Niels Brinch
0
有一种方法会快得多。但这意味着要寻找精确的单词匹配，而不是使用Contains功能。
基本上，如果你有足够的内存，你可以创建一个字典，其中包含某些字符串中单词的ID（或ID）的引用。
因此，字典的类型可能是<string，List<int>>。这里的好处当然是将许多单词合并为一个较小的集合。而且，由于它是建立在哈希表上的，所以字典的查找非常快。
现在，如果这不是你想要的，你可以搜索内存中的全文搜索库。SQL Server支持使用索引进行全文搜索，以加速传统通配符搜索之外的过程。但是，纯内存解决方案肯定会更快。然而，这仍然可能无法给您提供通配符搜索的确切功能。
- Steve Wortham
3
谢谢，是的，它必须是一个完整的子字符串，而不仅仅是单词搜索。还是谢谢。 - Niels Brinch
@NielsBrinch - 我很好奇。您编写的通配符搜索（wildcard search）是否真的是期望的结果？我是说，直到我发现全文搜索的优势之前，我一直编写通配符搜索。全文搜索库提供了3个重要优势：索引（用于加速）、排名（用于相关性）以及搜索词根的备选版本的能力。 - Steve Wortham
理想情况下，我希望搜索实际的英语单词，但是即使它附加到另一个单词上，也需要进行搜索。'bicycle'应该被'cycle'找到。 - Niels Brinch
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
stringList中的所有字符串都转换为小写，而不是每次运行查询时调用ToLower（如果你经常这样做）。 - Servy