Побудова розподілених суфіксних дерев

Анотація

У статті розглядається задача паралельної побудови суфіксних дерев над великими текстовими масивами без використання кластерної інфраструктури. Проаналізовано еволюцію відповідних алгоритмів – від однопотокових методів Вайнера, МакКрейта та Укконена до розподілених підходів Wavefront, ER та DGST. Виявлено ключове обмеження алгоритму DGST, реалізованого на платформі Apache Spark: суттєві накладні витрати на серіалізацію даних та I/O-звернення до розподіленої файлової системи HDFS. Запропоновано архітектуру адаптації алгоритму DGST до середовища Node.js на основі модуля worker_threads та механізму SharedArrayBuffer. Структурна трансформація забезпечує відображення компонентів Spark на елементи Node.js: керуючий вузол – основний потік, виконавчий вузол – воркерний потік, HDFS – SharedArrayBuffer. Завдяки принципу нульового копіювання (Zero-Copy) та кешуванню декодованого вмісту буфера усуваються накладні витрати на серіалізацію, характерні для Spark, а архітектура переходить від I/O-bound до memory-bound моделі. Описано чотири алгоритмічні фази адаптованого методу: ініціалізація та попередня обробка, ітеративне розбиття на S-префікси, фаза Map з побудовою локальних частотних префіксних дерев, а також Shuffle/Reduce з балансуванням навантаження на основі алгоритмів Bin Packing та Number Partitioning. Експериментальне дослідження на текстовому масиві обсягом до 2 млн рядків підтвердило приблизно лінійне зростання часу обробки відносно розміру датасету та сублінійне зростання споживання пам’яті: при чотириразовому збільшенні обсягу даних показник MemoryLimit зріс лише у 3,6 раза. Пропускна здатність системи на максимальному обсязі склала 77 132 рядки/с.