Как быстро определить наличие строки в файле, при этом не засорять ОЗУ?

Question

Есть код. Он находится в цикле. Каждый раз генерируется случайная строка. Его переделывать не нужно, это просто пример:

bool F = true;
HashSet<string> HS = new(File.ReadAllLines(path));
Random rnd = new();
string Alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890";
int Length= 42;
while (F)
{
  StringBuilder sb = new(Lenght - 1);
  int Position = 0;
  for (int i = 0; i < Lenght; i++)
  {
    Position = rnd.Next(0, Alphabet.Lenght - 1);
    sb.Append(Alphabet[Position]);
  }
  Console.WriteLine(sb);
  if (HS.Contains(sb.ToString())
  {
    F = false;
  }
}

Также есть текстовый файл (250 Мб+, загружается в начале, строки в нём никогда точь в точь не повторяются, но все начинаются на "7L"):

7LbOa94610KaBUfMR945BaQiaPxmvvzg92640HaMCO
7L9MzBxk8F4anfi284B639Ksmgb72laHsJOF72Mapx
7L2VzMqPie96MzvBROha724Hsu8R1N09BxM7S6a7w0
7LXxos73JsgfoHzHs9264HdvxppalndGd629HskUqm
7LNdifvaSj39Hd6ri3Jd7wvfisgskdY7xbdkGsjcNx
...

Мне нужно при каждой генерации проверять, есть ли сгенерированная строка в файле.

Но такой метод не вариант, жрёт слишком много ОЗУ (получается 1,1 Гб занятой ОЗУ из ~250 Мб файла). И это я не использую файлы от ~3Гб.

Можно как-то экономнее использовать данные файла, чтобы и скорость проверки строк была высокой? P.S.: Попробовал использовать алгоритм - фильтр Блума. Первое время он работал отлично, но с более большими файлами количество коллизий тоже только увеличивается. Также мне не нужно никуда добавлять только что сгенерированные строки, только проверка.

Answer 1

Используйте дерево поиска. Упростим задачу: алфавит: [A, B, C, D] длинна слова - до 4 символов. Создайте структуру в файловой системе:

+--- A
|    +--- A
|    |    +--- A
|    |    +--- B
|    |    +--- C
|    |    \--- D
|    +--- B
|    |    +--- A
|    |    +--- B
|    |    +--- C
|    |    \--- D
|    +--- C
|    |    +--- A
|    |    +--- B
|    |    +--- C
|    |    \--- D
|    \--- D
|         +--- A
|         +--- B
|         +--- C
|         \--- D
+--- B
|    +--- A
|    |    +--- A
|    |    +--- B
|    |    +--- C
|    |    \--- D
|    +--- B
|    |    +--- A
|    |    +--- B
|    |    +--- C
|    |    \--- D
|    +--- C
|    |    +--- A
|    |    +--- B
|    |    +--- C
|    |    \--- D
|    \--- D
|         +--- A
|         +--- B
|         +--- C
|         \--- D
+--- C
|    +--- A
|    |    +--- A
|    |    +--- B
|    |    +--- C
|    |    \--- D
|    +--- B
|    |    +--- A
|    |    +--- B
|    |    +--- C
|    |    \--- D
|    +--- C
|    |    +--- A
|    |    +--- B
|    |    +--- C
|    |    \--- D
|    \--- D
|         +--- A
|         +--- B
|         +--- C
|         \--- D
+--- D
     +--- A
     |    +--- A
     |    +--- B
     |    +--- C
     |    \--- D
     +--- B
     |    +--- A
     |    +--- B
     |    +--- C
     |    \--- D
     +--- C
     |    +--- A
     |    +--- B
     |    +--- C
     |    \--- D
     \--- D
          +--- A
          +--- B
          +--- C
          \--- D

В папке B/A/C храните файл со всеми строками, которые начинаются на BAC (без префикса). Таким образом, в файле по пути B/A/C будут только строки [A, B, C, D], которые соответствуют строкам ["BACA", "BACB", "BACC", "BACD"]. Чтобы проверить, что вашей строки нет, просто перейдите на нужный файл и проверьте его содержимое. Если большая часть дерева заполнена - никакое сжатие не поможет. Энтропия данных очень велика (по крайней мере исходя из того примера, который вы предоставили). Если вы предоставите больше информации о данных, возможно, будут иметь место оптимизации.

Answer 2

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

Answer 3

Используйте базу данных, ведь она будет быстрее любого неструктурированного файла. Представьте, например, что вы отсортировали все слова в файле и используете бинарный поиск, чтобы определить, есть ли слово в файле. Это очень эффективно. Но вот, вы определили, что файл не содержит очередного слова. Что вы будете делать, чтобы добавить слово в файл и сохранить его сортировку? Правильно, вы будете вынуждены добавить слово в середину файла, что является очень дорогостоящим как по памяти так и по времени для такого огромного файла. Если бы речь шла о базе данных, вы могли бы создать иерархические таблицы и вставка нового слова сводилась бы к добавлению новой записи в очередную таблицу, что выполняется за O(1) (амортизированно). Поиск же будет осуществляться эффективно средствами самой базы данных.

Answer 4

Используйте радужные таблицы, чтобы выяснить, что слова нет в файле. Для применения этого метода вам нужно предварительно сгенерировать радужные таблицы из вашего файла (и, возможно, дополнять по мере необходимости), чтобы использовать их для быстрого выяснения, есть ли слово в таком большом массиве данных. Этот метод немного более гибок, чем фильтр Блума, поскольку он позволяет заранее определить отношение память/производительность для вашей задачи, путём генерации радужной таблицы необходимой конфигурации.

По большому счёту, все решения сводятся к одной простой идее "Разделяй и властвуй"

БЛОГ НА HUSL

Как быстро определить наличие строки в файле, при этом не засорять ОЗУ?

Ответы (4 шт):