我的应用程序的内存中可能有 100,000 个字符串的列表。我需要找到包含某个关键字的前 20 个字符串（不区分大小写）。这很容易做到，我只需运行以下 LINQ。
from s in stringList
where s.ToLower().Contains(searchWord.ToLower())
select s
但是，我有一种明显的感觉，我可以更快地做到这一点，我需要找到方法，因为我需要每秒多次在这个列表中查找。
问问题
5138 次
4 回答
4
查找子字符串（不完全匹配）非常困难。没有任何内置功能可以帮助您解决此问题。我建议您研究可用于有效查找子字符串的后缀树数据结构。
顺便说一句，您可以拉出searchWord.ToLower()一个局部变量来节省大量的字符串操作。您还可以预先计算 stringList 的小写版本。如果你不能预先计算，至少使用s.IndexOf(searchWord, StringComparison.InvariantCultureIgnoreCase) != -1. 这节省了昂贵的 ToLower 调用。
您还可以在查询上添加 .AsParallel。
于 2012-05-15T18:34:03.757 回答
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 位 int 中来将其减半，例如，在最低 12 位中使用 positionInString，在剩余的高位中使用 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;
}
}
}
}
于 2012-05-15T20:46:12.453 回答
0
在这种情况下，您需要的是反向索引。
如果您愿意花很多钱，您可以使用数据库特定的全文搜索索引，并调整索引以索引每个单词子集。
或者，您可以使用一个非常成功的开源项目来实现相同的目标。
您需要使用标记器对字符串进行预索引，并构建反向索引文件。我们在 Java 中有类似的用例，我们必须在大量数据中进行非常快速的自动完成。
您可以查看Lucene.NET，它是 Apache Lucene（Java 中）的一个端口。
如果您愿意放弃 LINQ，可以使用 NHibernate Search。（眨眼）。
另一种选择是在内存中实现预索引，预处理和绕过不需要的扫描，看看Knuth-Morris-Pratt 算法。
于 2012-05-15T18:36:40.777 回答
0
有一种方法会快得多。但这意味着寻找精确的单词匹配，而不是使用该Contains功能。
基本上，如果你有它的记忆，你可以创建一个单词字典，它还为找到该单词的字符串引用某种 ID（或 ID）。
所以 Dictionary 可能是 type <string, List<int>>。当然，这里的好处是您将大量单词合并到一个较小的集合中。而且，字典的查找速度非常快，因为它是建立在哈希表上的。
现在，如果这不是您要查找的内容，您可以搜索内存中的全文搜索库。SQL Server 支持使用索引进行全文搜索，以加快传统通配符搜索的过程。但是纯粹的内存解决方案肯定会更快。但是，这仍然可能无法为您提供通配符搜索的确切功能。
于 2012-05-15T18:43:32.660 回答