Выбор подходящей структуры данных (хэш-таблица или дерево суффиксов) для индексации очень большого набора похожих строк
У меня есть большой набор строк, порядка ~10^12 или около того, и мне нужно выбрать подходящую структуру данных, чтобы при наличии строки я мог получить и связать целочисленное значение в чем-то вроде O(log(n)) или O(m) время, где "n" - длина списка строк, а "m" - длина каждой строки.
Мы можем ожидать, что наш набор строк, каждая из которых имеет длину "m" и закодирована в некотором алфавите размера "q", охватывает почти все возможные строки этой длины. Например, представьте, что у нас есть 10 ^ 12 полностью уникальных двоичных строк длиной m = 39. Это означает, что мы покрыли ~54% множества всех возможных двоичных строк этой длины.
Поэтому я обеспокоен поиском подходящей функции хеширования для строк, которая позволяет избежать столкновений. Есть ли хороший, который я могу использовать? Сколько времени мне понадобится, чтобы проиндексировать мой набор из n строк?
Или я должен пойти с деревом суффиксов? Мы знаем, что алгоритм Укконена учитывает линейное построение времени, и я предполагаю, что это сэкономит пространство, учитывая большое количество похожих строк?
3 ответа
Учитывая ваше чрезвычайно большое количество строк, ваш выбор должен сосредоточиться на нескольких моментах:
1. Are your indexing structures going to fit in memory?
Для хеш-таблиц ответ однозначно нет. Таким образом, время доступа будет намного медленнее, чем O(1). Тем не менее, вам нужен только один доступ к диску (весь процесс вставки будет O(N)).
Для b-дерева я сделал некоторые теоретические вычисления, предполагая, что b + tree (чтобы сэкономить больше места во внутренних узлах), а также что внутренние узлы полностью заняты. Этот анализ не уместится в памяти:
- Обычный размер страницы диска составляет 4096 байт. Это размер одного узла b-дерева.
- Средний размер ваших строк составляет 70 байт (чем меньше, тем лучше).
- Адрес дочернего узла имеет 4 байта.
- Внутренний узел содержит d ключей и имеет d+1 дочерние адреса:
** 4096B = 4 * (d+1) + 70 * d <=> d = 4096/75 => d = 54 **
* # внутренние узлы в памяти -> # оставляет узлы на диске -> # сопоставленные строки *
0 внутренних узлов -> 1 покидает узел -> 53 сопоставленных строки
1 внутренний узел -> 54 оставленных узлов (каждый с 53 листами) -> 53² сопоставленных строк
1+54 внутренних узла -> 54² оставляют используемые узлы -> 53³ отображенных строк
...
... + 54⁵ внутренних узлов -> 54⁶ оставляет узлы = 53⁷ сопоставлены строки
53⁷ > 10^12 , but 54⁵*4096 bytes > 1TB of memory
Если ваши строки распределены неравномерно, вы можете изучить общие префиксы. Таким образом, внутренний узел сможет адресовать больше дочерних элементов, что позволит вам сэкономить память. BerkeleyDB имеет такую возможность.
2. What kind of access are you going to employ? Large or small number of reads?
If you have large number of reads, are they random or sequential?
Если ваш доступ последовательный, вы все равно можете воспользоваться btree, потому что вы будете часто использовать кэшированные узлы (не требующие доступа к диску), а листья будут последовательно связаны (дерево b +). Это также отлично подходит для запросов диапазона (что, я думаю, не так). Если ваш доступ полностью случайный, тогда hashtable быстрее, так как ему всегда нужен только один доступ к диску, а btree нужен доступ к диску для каждого уровня, хранящегося на диске.
Если вы собираетесь сделать небольшое количество обращений, предпочтительнее использовать хеш-таблицу из-за того, что вставка всегда будет быстрее.
Поскольку вы знаете общее количество ваших строк, вы можете указать его в хеш-таблице, и вы не потеряете время в операциях масштабирования сегмента (что подразумевает перефразирование всех элементов).
Примечание: я нашел кое-что о вашем дереве суффиксов ukkonens. Вставка является линейной, и доступ также является последовательным. Однако я обнаружил, что он используется только с некоторыми ГБ. Вот некоторые ссылки на алгоритмы дерева суффиксов: [ref1], [ref2] и [ref3].
Надеюсь, это поможет как-то...
Хеш-таблицы полезны, когда ключи редки, но когда ключи плотные, хешировать не нужно; Вы можете использовать ключ (строку) для индексации. Для поддержки простых запросов членства вы можете использовать битовый вектор. Если ваши данные представляют собой 39-битные двоичные строки, у вас будет битовый вектор длиной 2^39. 1 означает, что строка присутствует, 0 означает, что она отсутствует. Битовый вектор не будет ужасно большим, поскольку он составляет всего 2 39 39 бит = 2^31 байт = 2 ГБ.
Чтобы перейти от строки над алфавитом q к целому числу, вы рассматриваете его как число в базе q. Например, если q=4 и строка 3011, найдите целое число 3*4^3 + 0*4^2 + 1*4^1 + 1*4^0, что равно 197.
Соответствующие целочисленные значения будут занимать много места. Вы можете хранить их в массиве, индексированном строкой; поэтому в вашем примере у вас будет массив из 2 ^ 39 целых чисел с пустыми слотами. Это вряд ли уместится в памяти, так как он будет потреблять терабайт, даже если каждое целое число будет только один байт. В этом случае вы можете хранить их последовательно в файле на диске.
Возможно, вам будет полезно найти информацию о битовых векторах / битовых массивах: http://en.wikipedia.org/wiki/Bit_array
Ссылка в Википедии говорит о сжатии, которое может быть применимо.
...
Привет боб,
длинный ответ короткий: классический подход HASH+BTREE сильный и сверхбыстрый.
Независимо от того, нужно ли хранить 10 или 10 миллиардов строк в вышеуказанной структуре, не имеет значения - у вас всегда очень низкий порог поиска MAX.
Ну, вам нужно 10^12 = 1 000 000 000 000 - но это 1 триллион, это меня удивляет - даже мои тяжелые струнные тела находятся в диапазоне 1 миллиарда.
Просто проверьте мою реализацию в C по адресу: http://www.sanmayce.com/
Поэтому я обеспокоен поиском подходящей функции хеширования для строк, которая позволяет избежать столкновений. Есть ли хороший, который я могу использовать?
Самая быстрая функция поиска в хеш-таблице в C находится здесь:
http://www.sanmayce.com/Fastest_Hash/index.html
Он на 300-500% быстрее, чем сильные варианты 8-срезов CRC32 (как Castagnoli's, так и Koopman's), при этом демонстрируя аналогичные столкновения.