Как ускорить поиск элементов из статичного string[] по подстроке?

Имеется статичный массив из 25 млн строк разной длины ([A-Z0-9А-Я\s]+).
Простой For + string.Contains выполняется в среднем за 1110 ms, а For + Regex.IsMatch за 3410 ms

Вопрос: Если пренебречь памятью и зная что массив статичный в какую структуру его можно преобразовать для ускорения поиска элементов по подстроке (LIKE '%substring%')?

Спасибо.
  • Вопрос задан
  • 936 просмотров
Решения вопроса 3
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Сначала объедините все ваши строки в одну через какой-то раздилитель, которого не может быть в искомой строке (можно и без него, но с ним код чуть проще будет). В конце поставьте этот же разделитель 2 раза. Вроде "строка1$строка2$строка3$...$строкаN$$".

Вот уже ваша задача - быстро искать какую-то остроку в фиксированном тексте, а не куче строк.
Тут есть много вариантов. Например, постройте суффиксное дерево алгоритмом Укконена. Вот эта ваша структура. При запросе, как в боре, поищите искомую строку в этом дереве. Если где-то перехода нет - вхождения вы не нашли. Если вы остановились на какой-то вершине (или ребре в дереве), то вам осталось каким-нибудь обходом в глубину найти все листья в поддереве этого места. Каждый лист соответствует вхождению. Еще при построении суффиксного дерева вы каждый лист пометите началом суффикса. Можно в тот же момент место в строке и конкатенаций перобразовать в номер исходной строки (например, бинпоиском по индексам начал строк в тексте. Или просто заведите массив, где для каждого символа в тексте при построении запишите, какая изначальная строка там была).

Если разделитель не использовать, то могут быть лишние результаты - где искомый шаблон приложился между двух исходных строк в тексте. Их надо будет выкинуть.

Другой вариант - через преобразование Барроуза — Уилера. Вот есть лекция. Этот алгоритм часто упоминается в курсах по биоинформатике. Реализацию может даже найдете где-то. Потом можно найти номера исходных строк из индексов вхождений через тот же бинпоиск по сортированному массиву индексов начал всех строк в тексте.

Да, проблема тут будет, если у вас шаблон короткий, то вы найдете все вхождения, включая повторы в каждой из исходных строк. Тогда эти алгоритмы могут работать не сильно лучше наивного.

Учтите, что построение структуры данных тут будет в несколько раз медленнее простого for+Contains. Выигрыш вы получите, если у вас текст действительно статичный и вы в нем много раз что-то ищите.
Ответ написан
VoidVolker
@VoidVolker Куратор тега C#
Dark side eye. А у нас печеньки! А у вас?
Раз нет ограничений по памяти и надо максимально быстро, то можно разложить весь массив в дерево таблиц переходов с шагом в один символ на таблицу. Самый быстрый и самый затратный по памяти. Таблица на каждый символ - 256 байт. Скорость поиска зависит только от размера строки и не зависит от объема данных: один символ - один переход в таблице к следующей таблице или конец поиска, если ноль. Я так уже делал: использовать имеет смысл на объемах примерно от 4 гигабайт данных (чем больше объем - тем меньше затраты на каждый символ). Но, если память позволяет и цель именно в скорости - то вполне нормальная плата памятью за скорость. Можно сократить расход памяти, если перекодировать строки в кодировку по числу используемых символов. Тогда таблица переходов будет в несколько раз меньше. Более экономный и более медленный вариант - дерево массивов/списков с шагом в 2/4/8 символов, при этом в поиске сравнение не по символам делать, а сразу по 2/4/8 байт: т.е., работаем со строкой как с массивом байтов и получаем оттуда uint16/uint32/uint64 и их и сравниваем, ибо процессору все равно какую инструкцию выполнять - один байт сравнить или 8. Возможно, конечно, оптимизатор в поиске по строке это все и оптимизирует. Я давно уже не смотрю на результаты его работы - так что тут только опытным путем. Ну и щас еще других вариантов накидают с деревьями тоже.

UPD1:
Можно все несколько упростить (или усложнить - смотря с какой стороны смотреть), если перекодировать строки из стандартной кодировки во что-то более компактное либо самостоятельно сделать кодировку под набор данных.

Еще можно ускорить, если искать в несколько потоков, разбив весь набор данных на несколько групп.

UPD2:
Таки нашел немного времени и откопал исходники для шарпа и провел несколько тестов по расходу памяти.

Число строк / общий размер данных / итоговый размер дерева

5 символов:
1000000 / 55.9MB / 13.2GB
2000000 / 111.6MB / 25.2GB

10 символов:
100000 / 8.1MB / 4.1GB
200000 / 16.1MB / 8GB
300000 / 24.2MB / 11.9GB
400000 / 32.2MB / 15.7GB
500000 / 40.3MB / 19.5GB

15 символов:
100000 / 10.5MB / 6.6GB
200000 / 21MB / 13.1GB
300000 / 31.5MB / 19.5GB
400000 / 42MB / 25.8GB

20 символов:
100000 / 13MB / 9.1GB
200000 / 25.9MB / 18.1GB
300000 / 38.9MB / 27GB


Максимальный размер дерева для глубины в 5 символов на платформе х64:
  • Для диапазона 0-255 - до 8Тб и до 4 311 810 305 узлов
  • Для диапазона 0-70 - до 13.5Гб и до 24 357 971 узлов

Максимальный размер дерева для глубины в 4 символа для диапазона 0-255: ~17Гб и ~33Гб для х86 и для х64 соответственно и лимит в 16 843 009 узлов. Ну и в коде есть функция для вычисления максимального числа узлов и размера дерева.

Как видно по результатам - чем выше объем и короче строки, т.е., плотность, тем выше эффективность размещения на единицу памяти. Скорость поиска в таком дереве зависит лишь от числа символов в слове/строке и всегда константа независимо от объема. ТС имеет смысл оптимизировать алгоритм под свои данные, если там обычный текст - то вероятно имеет смысл сделать индекс слов, подобрать компактную кодировку, а далее уже список строк с этим словом. Т.е., сначала идет поиск в дереве по слову, а далее уже по списку строк. И можно будет хоть в гигабайтах искать мгновенно, но памяти там надо будет уже терабайты.

И соответственно код: https://github.com/VoidVolker/search-tree/tree/master (предупреждаю сразу: код старый, по сути экспериментальный, не вылизанный и вероятно приведет кого-то в ужас). Но, главное, что работает.
код

Тестовый код:
static Random rnd = new Random();
static string[] GenStrings(int cnt, int strLen)
{
    string[] arr = new string[cnt];
    var i = 0;
    while (i < cnt)
    {
        var sb = new StringBuilder();
        for (var j = 0; j < strLen; j++)
        {
            sb.Append(rnd.Next(0, 256));
            //sb.Append(TAbc[rnd.Next(0, TAbc.Length)]);
        }
        arr[i++] = sb.ToString();
    }
    return arr;
}

var arraySize = 300000;
var stringSize = 20;

var GCStartArr = GC.GetTotalMemory(true);

var strings = GenStrings(arraySize, stringSize);

var GCEndArr = GC.GetTotalMemory(true);
var GCStart = GC.GetTotalMemory(true);

var tree = new ArrayTree<string>();
foreach (string s in strings)
{
    tree.Add(Encoding.UTF8.GetBytes(s), s);
}

var GCEnd = GC.GetTotalMemory(true);

Console.WriteLine("Array x string size / Array memory used / Tree memory used");
Console.WriteLine($"{arraySize} х {stringSize} / {BytesToString(GCEndArr - GCStartArr)} / {BytesToString(GCEnd - GCStart)}");
Ответ написан
@Degot Автор вопроса
Я сравнил несколько вариантов: Contains, SqliteFTS, Words. И выбрал реализацию Words.
Псевдо-C#:
var strings = new string[]; //25 млн записей

var words = new Dictionary<string,HashSet<int>>();
//формирование "справочника"
var str = string.Empty;
for(var stringId = strings.Length - 1; stringId >= 0; stringId--)
{
    str = strings[stringId];
    var stringWords = NormalizeString(str).Split(' ');
    foreach(var stringWord in stringWords )
    {
        words[stringWord].Add(stringId);
    }
}

//поиск
var searchTermWords= NormilizeString(searchTerm).Split(' ')
var foundIds = new HashSet<int>();
foreach(var searchTermWord in searchTermWords)
{
   foreach(var matchWord in words.Keys.Where(x => x.Contains(searcgTermWord)))
   {
  if (words.TryGetValue(matchWord, out var stringIds))
  {
    if (foundIds  == null)
    {
        foundIds = stringIds;
    }
    else
    {
        foundIds = stringIds.Where(x => foundIds .Contains(x)).ToHashSet();
    }
 }
 else
 {
     foundIds  = null;
 }
}
}

Console.WriteLine($"Найдено строк: {foundIds.Count} ");


Тесты разных вариантов для списка объектов с 4мя строковыми полями:
Поиск: 100 циклов поиска 1-3 символьной подстроки по одному полю

records: ~5 000 000

TestContains (ms):
  -> Max: 434, Avg: 295.56, Median: 281

TestSqliteFTS (ms):
  CREATE -> 111
  INSERT DATA -> 34697 //INSERT INTO temp_table(object_id, поле0, поле1, поле2,  поле3)
  INSERT INDEX -> 161683 // INSERT INTO fts_index(object_id, поле0, поле1, поле2,  поле3 ) SELECT * FROM temp_table
  DROP DATA -> 1191
  VACUUM -> 15849

  -> sqlite.db (FTS5: 1.6GB, tokenize = 'trigram', content='',columnsize=0, detail='column')
  -> Max: 10, Avg: 1.16, Median: 0
  
TestWords (ms):
  CREATE -> 89
  INSERT DATA -> 98851 //INSERT INTO temp_table(word_id, object_id)
  AGGREGATE DATA -> 28504 //SELET object_id FROM temp_table WHERE @word_id  -> FastPFor -> INSERT word_id, object_ids_as_bytes
  DROP DATA -> 1360
  CREATE INDICES-> 9
  VACUUM -> 262

  -> sqlite.db (CUSTOM: 9.5MB, (tbl: fields -> id, value), (tbl: words -> id, field_id, value), (tbl: data -> word_id INTEGER, integersQty INTEGER, bytes BLOB))
  -> Max: 128, Avg: 18.78, Median: 1
  
  Статы:
    field_id    wordsQty   maxRefsQty  avgRefsQty  maxRefsBytes    avgRefsBytes
    0           24075	    6461929	    271         910000          52
    1	        5339	    23858735	4515	    3336816         667
    2       	3602	    6766040     1913        952808          295
    3	        11825	    7595099     744         1069508         123


records: ~25 000 000

TestContains (ms):
  -> Max: 2568, Avg: 1524.47, Median: 1437.5

TestSqliteFTS (ms):
  CREATE -> 135
  INSERT DATA -> 255882 //INSERT INTO temp_table(object_id, поле0, поле1, поле2,  поле3)
  INSERT INDEX -> 1022499 // INSERT INTO fts_index(object_id, поле0, поле1, поле2,  поле3 ) SELECT * FROM temp_table
  DROP DATA -> 370118
  VACUUM -> 1230845
  
  -> sqlite.db (FTS5: 8.1GB, tokenize = 'trigram', content='',columnsize=0, detail='column')
  -> Max: 587, Avg: 11.53, Median: 0

TestWords (ms):
  CREATE -> 107
  INSERT DATA -> 581050 //INSERT INTO temp_table(word_id, object_id)
  AGGREGATE DATA -> 132700 //SELET object_id FROM temp_table WHERE @word_id  -> FastPFor -> INSERT word_id, object_ids_as_bytes
  DROP DATA -> 6855
  CREATE INDICES-> 32
  VACUUM -> 1161

  -> sqlite.db (CUSTOM: 35MB, (tbl: fields -> id, value), (tbl: words -> id, field_id, value), (tbl: data -> word_id INTEGER, integersQty INTEGER, bytes BLOB))
  -> Max: 492, Avg: 64,87, Median: 1
  
  Статы:
    field_id    wordsQty   maxRefsQty  avgRefsQty  maxRefsBytes    avgRefsBytes    
    0       	24075	    32570729	1355        4586324         205
    1	        5339	    120257135	22577       16818780        3192
    2	        3602	    34103240	9566        4802092         1372
    3	        11825	    38282299	3723        5390372         542


P.S. После тестирования FastPFor, WAH, RoamingBitmap и LZO для хранения индексов (слово -> индекс строки[]) остановился на Delta + LZO. Итоговый размер индекса: 17MB. Максимальное время поиска 600ms, среднее 7ms.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
mindtester
@mindtester Куратор тега C#
http://iczin.su/hexagram_48
как вариант (да простят коллеги) - многосвязный граф из уникальных подстрок с глубиной..
25 млн строк
не хилая заявка..
все что повторяется - узлы графа, уникальные хвосты - их содержимое
тут появляется возможность использовать графовые БД.
раз у нас тег C# brightstardb возможно? это умозаключения, не имел достаточной практики утверждать уверенно

ps если память не изменяет - brightstardb легковесная, может работать как сервис, так и встраиваемая, мозгами пораскинуть придется.. производительна.. но все познается в сравнении бенчмарков

pps естественно это не единственная графовая бд, в тч под шарп ))

ppps ... а обход массива с plinq не пробовали?... ну может ядер много? ;)))
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы