Ось опис проблеми.Припустимо, у вас є набір рядків (до 10 мільярдів рядків, довжина кожного рядка - до 10 тисяч символів, з них можна побудувати 1000 унікальних символів). Як я можу знайти візерунки довжиною від 2 до довжини N (скажемо 10 для простоти). Також я хотів би бачити лише ті візерунки, які зустрічаються принаймні в 1% усіх рядків (деякий поріг).
Я хотів би знайти алгоритм, який може допомогти мені вирішити цю проблему. Цифри не є точними, але мають той самий порядок величини, що і в проекті.
Дякую
Відповіді:
1 для відповіді № 1Індексуйте всі свої рядки в суфіксальному дереві (посилання). Це може бути O (кількість символів), і це потрібно зробити лише один раз перед початком роботи.
Дерево суфіксів дозволяє швидко (O (довжина шаблону)) визначити, чи з’являється візерунок у будь-якому з рядків, які ви проіндексували, і скільки разів.
Ви можете зробити ще один прохід через структуру іпідрахуйте кількість листків у кожному піддереві (O (N) знову), і це говорить вам, як часто ви можете знайти підрядок від кореня до цього вузла, щоб ви могли скинути їх або робити все, що завгодно, виходячи з того, наскільки вони поширені.
Тепер 10 мільярдів рядків довжиною 10k, з 2байтових символів (щоб вмістити 1000 унікальних символів) досить великий (18 ТБ, якщо моя математика правильна), що не вміщується в оперативній пам'яті. Отже, вам потрібно буде почекати деякий час, або отримати більше комп’ютерів і налаштувати розподілене рішення. Ви можете застосувати наведене вище рішення до пакетів рядків, щоб вони помістились у вашій доступній пам’яті, але пошук у структурі потрібно помножити на кількість пакетів, які ви робите.
Якщо все по партіях, то найбільшеефективним способом було б зробити партії якомога більшими, тоді, коли ви будуєте дерево суфіксів для партії, запускаєте через неї всі ваші запити, зберігаєте результати та скидаєте дерево, щоб звільнити пам'ять для наступної партії вхідних рядків.