Какая структура обеспечивает лучшие результаты производительности; trie (дерево префиксов), дерево суффиксов или массив суффиксов? Существуют ли другие подобные структуры? Каковы хорошие реализации Java этих структур?
Изменить: в этом случае я хочу сделать соответствие строк между большим словарем имен и большим набором текстов на естественном языке, чтобы идентифицировать имена словаря по текстам.
Trie была первой структурой данных такого рода.
Дерево суффиксов является улучшением по сравнению с trie (у него есть суффиксные ссылки, которые позволяют осуществлять поиск по линейной ошибке, дерево суффиксов обрезает ненужные ветки trie, поэтому для этого не требуется столько места).
Суффикс-массив - это урезанная структура данных, основанная на дереве суффиксов (без суффиксных ссылок (медленное совпадение ошибок), но совпадение шаблонов выполняется очень быстро).
Trie не для реального использования в мире, потому что он потребляет слишком много места.
Дерево суффиксов легче и быстрее, чем trie, и используется для индексации ДНК или оптимизации некоторых крупных поисковых машин.
Суффиксный массив медленнее в некоторых поисках шаблонов, чем дерево суффикса, но использует меньше места и более широко используется, чем дерево суффикса.
В том же семействе структур данных:
Существуют и другие реализации, CST представляет собой реализацию дерева суффикса, используя массив суффикса и некоторые дополнительные структуры данных, чтобы получить некоторые возможности поиска дерева суффикса.
FCST берет его дальше, он реализует сэмплированное дерево суффикса с массивом суффикса.
DFCST - это динамическая версия FCST.
Расширение:
Двумя важными факторами являются использование пространства и время выполнения операции. Вы можете подумать, что в современных машинах это не актуально, но для индексации ДНК одного человека потребуется 40 гигабайт памяти (с использованием несжатого и неоптимизированного дерева суффикса). И построить один из этих индексов над этим большим количеством данных может занять несколько дней. Представьте, Google, у него много доступных для поиска данных, им нужен большой индекс по всем веб-данным, и они не меняют его каждый раз, когда кто-то создает веб-страницу. Для этого у них есть какая-то форма кэширования. Однако основной индекс, вероятно, статичен. И каждые две недели они собирают все новые веб-сайты и данные и строят новый индекс, заменяя старый, когда новый закончен. Я не знаю, какой алгоритм они используют для индексации, но это, вероятно, массив суффикса с свойствами дерева суффиксов над многораздельной базой данных.
CST использует 8 гигабайт, однако скорость операций с деревом суффиксов сильно сокращается.
Суффиксный массив может сделать то же самое в некоторых 700 мегаватт до 2 гига. Однако вы не найдете генетических ошибок в ДНК с массивом суффикса (то есть: поиск шаблона с подстановочным знаком намного медленнее).
FCST (полностью сжатое дерево суффиксов) может создать дерево суффикса в 800-150 гигабайт. С довольно небольшим ухудшением скорости в сторону КНТ.
DFCST использует на 20% больше места, чем FCST, и теряет скорость для статической реализации FCST (однако динамический индекс очень важен).
Существует не так много жизнеспособных (пространственных) реализаций дерева суффиксов, потому что очень сложно сделать ускорение скорости операции, компенсируя затраты на объем оперативной памяти.
Это говорит о том, что дерево суффикса имеет очень интересные результаты поиска для сопоставления шаблонов с ошибками. Aho corasick не так быстро (хотя и почти так же быстро для некоторых операций, а не для сопоставления ошибок), и болотный moore остается в пыли.
Какие операции вы планируете делать? libdivsufsort был в свое время лучшей реализацией массива суффиксов в C.
Используя деревья суффикса, вы можете написать что-то, что будет соответствовать вашему словарю, вашему тексту в O (n + m + k), где n - буквы в словаре, m - буквы в вашем тексте, а k - количество совпадений, Для этого более медленные попытки. Я не уверен, что такое Suffix Array, поэтому я не могу комментировать это.
Тем не менее, это нетривиально для кода, и я не знаю каких-либо библиотек Java, которые предоставляют необходимые функции.
EDIT: В этом случае я хочу сделать соответствие строк между большим словарем имен и большим набором тексты на естественном языке, чтобы идентифицировать имена словаря по текстам.
Это звучит как приложение для алгоритм Aho-Corasick: постройте автомат из словаря (в линейном времени), который затем может используется для поиска всех вхождений словаря в несколько текстов (также в линейном времени).
(Описание в эти примечания к лекции, связанные с разделом "Внешние ссылки" на странице Википедии, намного легче читать чем описание на самой странице.)
Trie vs Suffix tree
обе структуры данных обеспечивают очень быстрый поиск, время поиска пропорционально длине слова запроса, время сложности O (m), где m - длина слова запроса.
Это означает, что если у нас есть слово запроса, которое содержит 10 символов, нам нужно не более 10 шагов, чтобы найти его.
Trie: Дерево для хранения строк, в которых есть один node для каждого общего префикса. Строки хранятся в дополнительных узлах листа.
дерево суффиксов: компактное представление trie, соответствующее суффиксам данной строки, где все узлы с одним дочерним элементом объединены с родителями.
def: Словарь алгоритмов и структур данных
обычно Trie используется для индексации словарных слов (лексикон) или любых наборов строк пример D = {abcd, abcdd, bxcdf,....., zzzz}
дерево суффикса, используемое для индексации текста, используя ту же структуру данных "Trie" для всех суффиксов нашего текста Т = abcdabcg все суффиксы T = {abcdabcg, abcdabc, abcdab, abcda, abcd, abc, ab, a}
теперь он выглядит как группы строк. мы строим Trie над этими группами строк (все суффиксы T).
построение обеих структур данных линейно, оно принимает O (n) во времени и пространстве.
в случае dicionary (набор строк): n = сумма символов всех слов. в тексте: n = длина текста.
массив суффикса: является техникой для представления дерева суффикса в сжатом sapce, это массив всех начальных позиций суффиксов строки.
он медленнее, чем дерево суффикса во время поиска.
для получения дополнительной информации перейдите на wikipedia, есть хорошая статья, посвященная этой теме.
Я предпочитаю Suffix Auto Machine. Вы можете найти более подробную информацию на моем сайте: http://www.fogsail.net/2019/03/06/20190306/
введите описание изображения здесь
Во-первых, если вы использовали нормальную конструкцию, потребуется O (n ^ 2), чтобы пройти весь суффикс
Мы используем radix-sort для сортировки суффикса Array по первому символу.
Но, если мы сортируем первый символ, мы можем использовать информацию.
Детали показаны на изображениях (пренебрежение китайским)
Сортируем массив по первому ключу, результат представлен красным прямоугольником
𝑎𝑎𝑏𝑎𝑎𝑎𝑎𝑏, 𝑎𝑏𝑎𝑎𝑎𝑎𝑏,....--> 𝑎𝑎𝑏𝑎𝑎𝑎𝑎𝑏, 𝑎𝑎𝑎𝑎𝑎𝑎𝑏,....
введите описание изображения здесь
#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;
}
}