Обобщенная реализация дерева суффиксов Java для больших наборов данных

У меня есть коллекция из 50 миллионов строк, каждая из которых содержит около 100 символов. Я ищу очень эффективную (время работы и использование памяти) реализацию обобщенного дерева суффиксов.

Я пробовал https://github.com/npgall/concurrent-trees, но это занимает огромное количество памяти, хотя время работы эффективно. С 2,5 миллионами строк длиной 100. Это заняло уже около 50 ГБ памяти.


full-text-search data-structures suffix-tree suffix-array
person Benjamin Nguyen    schedule 03.11.2015    source источник
comment
То, что мы на самом деле делаем с подобными наборами данных, не делается с обобщенными деревьями суффиксов. Если вы объясните, что вам нужно делать с этими 50 миллионами строк, т. е. какие типы запросов вам нужны, чтобы иметь возможность отвечать, мы, возможно, сможем предложить практическую структуру данных. Также скажите, что это за данные и сколько оперативной памяти у вас есть.   -  person Matt Timmermans    schedule 09.11.2015
comment
для данной подстроки я хотел бы получить все вхождения: строки, содержащие подстроку, и позиции вхождений. Я хотел бы сжать до менее 16 ГБ или 8 ГБ. Здесь может быть торговля временем и пространством. Если это так, я предпочитаю время запроса, и время сборки не будет так сильно снижаться (с логарифмическим коэффициентом все в порядке)   -  person Benjamin Nguyen    schedule 10.11.2015
comment
Пожалуйста, прочитайте О каких темах я могу здесь спросить?, Какие типы вопросов следует избегать? и Как задать хороший вопрос? прежде чем пытаться задать дополнительные вопросы. Чрезмерное количество плохо полученных вопросов, не относящихся к теме, приведет к тому, что вам будет запрещено задавать вопросы, а вы этого не хотите, не так ли?   -  person    schedule 03.03.2016

Ответы (1)


arrow_upward
0
arrow_downward

Не идеальное решение, но вы можете использовать введите здесь описание ссылки. У него есть версия CritBit1D, в которой можно хранить ключи произвольной длины.

Недостаток № 1: вам придется сначала преобразовать ваши строки в long[], т.е. 4-8 символов в длинном.

Недостаток № 2: если вам нужна параллельная версия, вам придется взглянуть на Critbit64COW, которая использует параллелизм копирования при записи. Однако это еще не реализовано для Critbit1D, поэтому вам нужно будет сделать это самостоятельно, используя Critbit64COW в качестве шаблона.

Однако вы можете просто сохранить только 64-битный хэш-код в качестве ключа, тогда вы можете использовать CritBit64 (однопоточный) или CritBit64COW (многопоточный). Кстати, одновременное чтение не проблема, даже с CritBit64.

Отказ от ответственности: я автор CritBit.

person TilmannZ    schedule 06.11.2015