Выбор подходящей структуры данных (хеш-таблица или суффиксное дерево) для индексации очень большого набора похожих строк.

У меня есть большой набор строк порядка ~ 10 ^ 12 или около того, и мне нужно выбрать подходящую структуру данных, чтобы при наличии строки я мог получить и связанное целочисленное значение в чем-то вроде O (log (n)) или O(m) раз, где «n» — длина списка строк, а «m» — длина каждой строки.

Мы можем ожидать, что наш набор строк, каждая из которых имеет длину «m» и закодирован в некотором алфавите размера «q», покрывает почти все возможные строки этой длины. Например, представьте, что у нас есть 10 ^ 12 уникальных двоичных строк длины m = 39. Это означает, что мы покрыли ~ 54% набора всех возможных двоичных строк этой длины.

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

Или я должен пойти с деревом суффикса? Мы знаем, что алгоритм Укконена позволяет построить линейное время, и я предполагаю, что это сэкономит место, учитывая большое количество похожих строк?


string hash prefix-tree
person Bob    schedule 22.10.2012    source источник
comment
каков максимальный «m», который вы ожидаете? в вашем алфавите размера «q» каждый элемент представляет собой символ или группу символов? если это группа, каков максимальный размер каждого элемента алфавита?   -  person Leaurus    schedule 22.10.2012
comment
@Leaurus Максимальное значение «m», которое я ожидаю, находится в порядке от m = 40 до 100. Каждый элемент в алфавите является символом (т. Е. q = 6 означает, что символы представляют собой целые числа от 1 до 6).   -  person Bob    schedule 23.10.2012

Ответы (3)


arrow_upward
1
arrow_downward

Учитывая ваше чрезвычайно большое количество строк, ваш выбор должен быть сосредоточен на нескольких моментах:

1. Are your indexing structures going to fit in memory?

Для хеш-таблиц однозначно нет. Таким образом, время доступа будет намного медленнее, чем O (1). Тем не менее вам просто нужен доступ к одному диску (весь процесс вставки будет O (N)).

Для b-tree я провел некоторые теоретические расчеты, предполагая 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 + дерево). Это также отлично подходит для запросов диапазона (что, я думаю, не так). Если ваш доступ полностью случайный, то хэш-таблица работает быстрее, так как ей всегда требуется только один доступ к диску, а btree требуется доступ к диску для каждого уровня, хранящегося на диске.

  • Если вы собираетесь делать небольшое количество обращений, хэш-таблица предпочтительнее из-за того, что вставка всегда будет быстрее.

  • Поскольку вы знаете общее количество ваших строк, вы можете указать его в хэш-таблице, и вы не будете терять время на операции масштабирования ведра (что подразумевает повторное хеширование всех элементов).

Примечание. Я нашел кое-что о вашем ukkonens суффиксное дерево. Вставка является линейной, и доступ также является последовательным. Однако я обнаружил, что он используется только с некоторыми ГБ. Вот несколько ссылок на алгоритмы дерева суффиксов: [ref1], [ref2] и [ref3].

Надеюсь, это как-то поможет...

person Leaurus    schedule 24.10.2012

arrow_upward
1
arrow_downward

Хэш-таблицы полезны, когда ключей мало, но когда ключей много, хеширование не требуется; вы можете использовать сам ключ (строку) для индексации. Для поддержки простых запросов на членство можно использовать битовый вектор. Если ваши данные представляют собой 39-битные двоичные строки, у вас будет битовый вектор длиной 2 ^ 39. 1 означает, что строка присутствует, 0 означает, что она отсутствует. Битовый вектор не будет очень большим, поскольку он составляет всего 2^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

Ссылка на википедию говорит о сжатии, которое может быть применимо.

person user1951747    schedule 25.07.2013

arrow_upward
0
arrow_downward

...

Привет боб,

короткий ответ: классический подход HASH + BTREE силен и сверхбыстр.

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

Ну, вам нужно 10 ^ 12 = 1 000 000 000 000 - но это 1 триллион, это меня удивляет - даже мои массивы тяжелых строк находятся в диапазоне 1 миллиарда.

Просто проверьте мою реализацию на C по адресу: http://www.sanmayce.com/#Section13Level.

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

Самая быстрая функция поиска хэш-таблицы в C находится здесь:

http://www.sanmayce.com/Fastest_Hash/index.html#KT_torture3

Это на 300-500% быстрее, чем сильные варианты CRC32 8slice (как у Кастаньоли, так и у Купмана), но с аналогичными коллизиями.

person Georgi    schedule 22.10.2012