Три или дерево суффиксов против массива суффиксов

Question

Какая структура обеспечивает лучшие результаты производительности; три (дерево префиксов), дерево суффиксов или массив суффиксов? Есть ли другие подобные структуры? Каковы хорошие реализации этих структур на Java?

Редактировать: в этом случае я хочу сопоставить строки между большим словарем имен и большим набором текстов на естественном языке, чтобы идентифицировать имена словаря по текстам.

Answer 1

Три была первой структурой данных такого типа, обнаруженной.

Дерево суффиксов является улучшением по сравнению с деревом (оно имеет ссылки суффикса, которые позволяют выполнять линейный поиск ошибок, дерево суффиксов обрезает ненужные ветви дерева данных, поэтому оно не требует такого большого пространства).

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

Это не для использования в реальном мире, потому что оно занимает слишком много места.

Дерево суффиксов легче и быстрее, чем дерево, и используется для индексации ДНК или оптимизации некоторых крупных поисковых систем в Интернете.

Массив суффиксов медленнее при поиске по образцу, чем дерево суффиксов, но использует меньше места и используется более широко, чем дерево суффиксов.

В том же семействе структур данных:

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

FCST идет дальше, он реализует семплированное суффиксное дерево с массивом суффиксов.

DFCST является динамической версией FCST.

Расширение:

Двумя важными факторами являются использование пространства и время выполнения операции. Вы можете подумать, что с современными машинами дня это не актуально, но для индексации ДНК одного человека потребовалось бы 40 гигабайт памяти (с использованием несжатого и неоптимизированного дерева суффиксов). И для построения одного из этих индексов по этому большому количеству данных могут потребоваться дни. Представьте себе, что Google имеет много доступных для поиска данных, им нужен большой индекс для всех веб-данных, и они не меняют его каждый раз, когда кто-то создает веб-страницу. У них есть какая-то форма кеширования для этого. Однако основной индекс, вероятно, является статическим. И каждые две недели или около того они собирают все новые веб-сайты и данные и создают новый индекс, заменяя старый, когда новый закончен. Я не знаю, какой алгоритм они используют для индексации, но это, вероятно, массив суффиксов со свойствами дерева суффиксов над многораздельной базой данных.

CST использует 8 гигабайт, однако скорость операций с деревом суффиксов сильно снижена.

Суффиксный массив может делать то же самое в диапазоне от 700 мегабайт до 2 гига. Однако вы не найдете генетических ошибок в ДНК с массивом суффиксов (это означает, что поиск шаблона с подстановочным знаком намного медленнее).

FCST (полностью сжатое дерево суффиксов) может создать дерево суффиксов за 800-1,5 гига. С довольно небольшим ухудшением скорости к CST.

DFCST использует на 20% больше места, чем FCST, и теряет скорость при статической реализации FCST (однако динамический индекс очень важен).

Существует не так много жизнеспособных (с точки зрения пространства) реализаций дерева суффиксов, потому что очень трудно заставить увеличение скорости операций компенсировать стоимость пространства ОЗУ структур данных.

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

Answer 2

Какие операции вы планируете делать? libdivsufsort был когда-то лучшей реализацией суффиксного массива в C.

Answer 3

Используя деревья суффиксов, вы можете написать что-то, что будет соответствовать вашему словарю с вашим текстом за O (n + m + k) время, где n - буквы в вашем словаре, m - буквы в вашем тексте, а k - количество совпадений , Попытки гораздо медленнее для этого. Я не уверен, что такое суффиксный массив, поэтому я не могу это комментировать.

Тем не менее, код нетривиален, и я не знаю ни одной библиотеки Java, предоставляющей необходимые функции.

Answer 4

Я предпочитаю Suffix Auto Machine. Вы можете найти более подробную информацию на моем сайте: http://www.fogsail.net/2019/03/06/20190306/

введите описание изображения здесь

сначала, если вы использовали нормальную конструкцию, вам понадобится O (n ^ 2), чтобы пройти весь суффикс

Мы используем radix-sort для сортировки массива суффиксов по первому символу.

Но, если мы отсортируем первый символ, мы можем использовать информацию.

Детали показаны на изображениях (пренебрежение китайским)

Сортируем массив по первому ключу, результат представлен красным прямоугольником

????????, ???????, ....--> ????????, ???????, ....

введите описание изображения здесь

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1001 * 100 + 10;

struct suffixArray {
    int str[maxn], sa[maxn], rank[maxn], lcp[maxn];
    int c[maxn], t1[maxn], t2[maxn];
    int n;

    void init() { n = 0; memset(sa, 0, sizeof(sa)); }

    void buildSa(int Rdx) {
        int i, *x = t1, *y = t2;
        for(i = 0; i < Rdx; i++) c[i] = 0;
        for(i = 0; i < n; i++) c[x[i] = str[i]]++;
        for(i = 1; i < Rdx; i++) c[i] += c[i-1];
        for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;

        for(int offset = 1; offset <= n; offset <<= 1) {
            int p = 0;
            for(i = n-offset; i < n; i++) y[p++] = i;
            for(i = 0; i < n; i++) if(sa[i] >= offset) y[p++] = sa[i] - offset;

            // radix sort
            for(i = 0; i < Rdx; i++) c[i] = 0;
            for(i = 0; i < n; i++) c[x[y[i]]]++;
            for(i = 1; i < Rdx; i++) c[i] += c[i-1];
            for(i = n-1; i >= 0; i--) { sa[--c[x[y[i]]]] = y[i]; y[i] = 0; }

            // rebuild x and y
            swap(x, y); x[sa[0]] = 0; p = 1;
            for(i = 1; i < n; i++)
                x[sa[i]] = y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+offset] == y[sa[i]+offset] ? p-1 : p++;
            if(p >= n) break;
            Rdx = p;
        }
    }

Answer 5

Три и Суффикс дерево

обе структуры данных обеспечивают очень быстрый поиск, время поиска пропорционально длине слова запроса, время сложности O (m), где m - длина слова запроса.

это имеет значение, если у нас есть слово запроса, содержащее 10 символов, поэтому нам нужно не более 10 шагов, чтобы найти его.

Trie : Дерево для хранения строк, в котором есть один узел для каждого общего префикса. Строки хранятся в дополнительных листовых узлах.

дерево суффиксов : компактное представление дерева, соответствующего суффиксам данной строки, где все узлы с одним дочерним элементом объединены со своими родителями.

def от: Словарь алгоритмов и структур данных

обычно три используется для индексации словарных слов (лексикон) или любых наборов строк пример D = {abcd, abcdd, bxcdf, ....., zzzz}

дерево суффиксов, используемое для индексации текста с использованием одинаковой структуры данных "Trie" для всех суффиксов нашего текста Т = abcdabcg все суффиксы T = {abcdabcg, abcdabc, abcdab, abcda, abcd, abc, ab, a}

теперь это похоже на группу строк. мы строим Trie над этими группами строк (все суффиксы T).

конструкция обеих структур данных линейна, она занимает O (n) во времени и пространстве.

в случае словарей (набор строк): n = сумма символов всех слов. в тексте: n = длина текста.

массив суффиксов: это метод для представления дерева суффиксов в сжатом файле, это массив всех начальных позиций суффиксов строки.

это медленнее, чем дерево суффиксов во время поиска.

для получения дополнительной информации перейдите в Википедию, на эту тему есть хорошая статья.

Answer 6

РЕДАКТИРОВАТЬ: В этом случае я хочу сделать сопоставление строк между большим словарем имен и большим набором тексты на естественном языке, для идентификации названий словаря по текстам.

Это звучит как приложение для алгоритма Aho-Corasick : создать автомат из словаря (по линейному времени), который затем можно использовать для поиска всех вхождений любого из словарных слов в несколько текстов (также в линейном времени).

(описание в этих примечаниях к лекции , ссылки на которые есть в разделе "Внешние ссылки" на странице Википедии, намного проще для чтения, чем описание на самой странице.)

Answer 7

Эта реализация алгоритма индуцированной сортировки (называемая sais) имеет версию Java для построения массивов суффиксов.