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

Question

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

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

Answer 1

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

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

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

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

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