Другой вариант, хотя он потребует достаточного количества памяти, состоял бы в том, чтобы прекомпилировать что-то вроде массива суффикса (список позиций внутри строк, отсортированных по строкам, на которые они указывают).
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, например с positionInString в младших 12 битах, и indexOfString в остальных верхних битах. Вам просто нужно немного поиграть, чтобы вернуть два значения. Важно отметить, что структура не содержит ни строк, ни подстрок. Строки, которые вы ищете, существуют только один раз.
Это даст вам полный индекс и позволит быстро найти любую подстроку (бинарный поиск по индексу, представленному массивом суффикса) с минимальными фактическими сопоставлениями строк.
Если память дорога, простая оптимизация первоначального алгоритма грубой силы будет заключаться в прекомполяции словаря уникальных символов и присвоении порядковых номеров для представления каждого. Затем предкоммутите бит массива для каждой строки с битами, установленными для каждого уникального символа, содержащегося в строке. Поскольку ваши строки относительно короткие, должна существовать значительная изменчивость рестринга BitArrays (это не сработает, если ваши строки были очень длинными). Затем вы просто вычисляете BitArray или ключевое слово поиска и выполняете поиск только для ключевого слова в тех строках, где keywordBits & targetBits == keywordBits. Если ваши строки предварительно преобразуются в нижний регистр и являются только английским алфавитом, BitArray, вероятно, будет соответствовать одному int. Таким образом, это потребует минимум дополнительной памяти, будет простым в реализации и позволит вам быстро отфильтровать строки, в которых вы определенно не найдете ключевое слово. Это может быть полезной оптимизацией, поскольку поиск строк выполняется быстро, но у вас их так много, чтобы использовать поиск грубой силы.
EDIT Для заинтересованных, вот базовая реализация начального решения, которое я предложил. Я запускал тесты с использованием 100 000 случайно генерируемых строк длин, описанных OP. Хотя для создания и сортировки индекса потребовалось около 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;
}
}
}
}
Если это было точное совпадение или операция запуска с начала работы, существует ряд способов значительно ускорить его, но с помощью содержит не так много, что вы можете сделать. Один маленький совет, хотя должен был бы сделать все строки в строчном строчке 'stringList', а не вызывать' ToLower' каждый раз, когда вы запускаете запрос (если вы это делаете). – Servy
«Моя фантастическая машина» содержит ключевое слово «муравей»? Определите, что значит содержать ключевое слово. – hatchet
Да, это чистый поиск подстроки, как указано в коде LINQ. –