Какая структура обеспечивает лучшие результаты производительности; trie (дерево префиксов), дерево суффиксов или массив суффиксов? Существуют ли другие подобные структуры? Каковы хорошие реализации Java этих структур?Trie против дерева суффикса против суффикса
Редактировать: в этом случае я хочу сделать соответствие строк между большим словарем имен и большим набором текстов на естественном языке, чтобы идентифицировать имена словаря по текстам.
Три были первой структурой данных такого рода.
Дерево суффикса является улучшением по сравнению с trie (оно имеет суффиксные ссылки, которые позволяют осуществлять поиск по линейной ошибке, дерево суффиксов обрезает ненужные ветви trie, поэтому для этого не требуется столько места).
Суффикс-массив - это урезанная структура данных, основанная на дереве суффиксов (без суффиксных ссылок (медленное совпадение ошибок), но совпадение шаблонов очень быстро).
Trie не для использования в реальном мире, потому что он потребляет слишком много места.
Дерево суффиксов легче и быстрее, чем trie, и используется для индексации ДНК или оптимизации некоторых крупных поисковых систем.
Суффикс-массив медленнее в некоторых поисках шаблонов, чем дерево суффикса, но использует меньше места и более широко используется, чем дерево суффикса.
В том же семействе структур данных:
Есть и другие варианты реализации, ДКБ является реализация дерева суффиксов с использованием массива суффиксов и некоторые дополнительные структуры данных, чтобы получить некоторые из возможностей поиска суффикса дерева.
FCST берет его дальше, он реализует семантику суффикса с суффиксом с массивом суффикса.
DFCST - это динамическая версия FCST.
Расширение:
Двумя важными факторами являются использование пространства и времени выполнения операции. Вы можете подумать, что в современных машинах это не актуально, но для индексации ДНК одного человека потребуется 40 гигабайт памяти (с использованием несжатого и неоптимизированного дерева суффикса). И построить один из этих индексов над этим большим количеством данных может занять несколько дней. Представьте, Google, у него много доступных для поиска данных, им нужен большой индекс по всем веб-данным, и они не меняют его каждый раз, когда кто-то создает веб-страницу. Для этого у них есть какая-то форма кэширования. Однако основной индекс, вероятно, статичен. И каждые две недели они собирают все новые веб-сайты и данные и строят новый индекс, заменяя старый, когда новый закончен. Я не знаю, какой алгоритм они используют для индексации, но это, вероятно, массив суффикса с свойствами дерева суффикса по многораздельной базе данных.
В CST используется 8 гигабайт, однако скорость операций с деревом суффиксов сильно уменьшается.
Суффикс-массив может делать то же самое в некоторых 700 мегаватах до 2 гига. Однако вы не найдете генетических ошибок в ДНК с массивом суффикса (то есть: поиск шаблона с подстановочным знаком намного медленнее).
FCST (полностью сжатое суффиксное дерево) может создать дерево суффикса в 800-150 гигабайт. С довольно небольшим ухудшением скорости в сторону КНТ.
DFCST использует на 20% больше пространства, чем FCST, и теряет скорость до статической реализации FCST (однако динамический индекс очень важен).
Существует не так много жизнеспособных (пространственных) реализаций дерева суффиксов, потому что очень сложно сделать ускорение скорости операции, компенсируя затраты на объем оперативной памяти.
Это говорит о том, что дерево суффикса имеет очень интересные результаты поиска для сопоставления шаблонов с ошибками. Aho corasick не так быстро (хотя и почти так же быстро для некоторых операций, а не для соответствия ошибкам), а боярский лес остался в пыли.
Что такое «линейный поиск ошибок "? –
Поиск по линейной ошибке - это поиск по ошибкам, который возвращает все возможные совпадения ошибок в линейном времени. Например, в тексте есть слова «Дом», «Хауса», «Хотце». Постоянное совпадение ошибок будет возвращать все ошибки за одну операцию. Линейное совпадение ошибок возвращает все ошибки (совпадения) в COUNT (совпадения). В этом случае 2. Некоторые могут интерпретировать это как линейный поиск по размеру текста (текстовое сканирование ошибки), и поэтому стоимость будет равна размеру текста. Это относится ко всем алгоритмам поиска ошибок, однако это не относится к дереву суффиксов. –
Преимущество суффикс-массива заключается в использовании меньше пространства, чем дерево суффикса. Но как мы можем это знать? Есть ли какое-либо математическое доказательство или мы основываемся на практических экспериментах? –
Используя деревья суффикса, вы можете написать что-то, что будет соответствовать вашему словарю, вашему тексту в O (n + m + k), где n - буквы в вашем словаре, m - буквы в вашем тексте, а k - количество Матчи. Для этого более медленные попытки. Я не уверен, что такое Суффикс-массив, поэтому я не могу комментировать это.
Это говорит о том, что это нетривиально для кода, и я не знаю каких-либо библиотек Java, которые предоставляют необходимые функции.
О массивах Суффикса: http://en.wikipedia.org/wiki/Suffix_array –
Да, я читал в массивах Суффикса. Оказывается, они имеют ту же асимптотическую скорость, что и деревья суффикса, но более эффективны по площади. Это определенно вариант. – swestrup
EDIT: В этом случае я хочу сделать соответствие между строками большого словарем имен и большим набором текстов на естественном языке, для того, чтобы определить имена словаря по текстам.
Это звучит как приложение для Aho-Corasick algorithm: построить автомат из словаря (в линейное время), который затем может быть использован, чтобы найти все вхождения любых из словарных слов в разных текстах (также в линейном время).
(описание в these lecture notes, связанный из раздела «Внешние ссылки» на странице Википедии, это намного проще, чем читать описание на самой странице.)
Какие операции вы планируете делать? libdivsufsort был когда-то наилучшим вариантом реализации суффикса в C.
Какова методика достижения этой эффективности для конструкции массива суффикса? – curious
Своевременный вопрос. AmpLab только что выпустил параллельную версию с подробным объяснением, https://amplab.cs.berkeley.edu/publication/parallel-lightweight-wavelet-tree-suffix-array-and-fm-index-construction/ –
This Реализация алгоритма индуцированной сортировки (называемого sais) имеет версию Java для построения массивов суффикса.
Trie против суффикса дерева структуры
оба данных обеспечивают очень быстрый смотреть вверх, время поиска пропорционально длине слова запроса, временная сложность O (м), где т является длина запроса слово.
Это означает, что если у нас есть слово запроса, которое содержит 10 символов, нам нужно не более 10 шагов, чтобы найти его.
Trie: Дерево для хранения строк, в которых есть один узел для каждого общего префикса. Строки хранятся в дополнительных листовых узлах.
suffix tree: компактное представление trie, соответствующее суффиксам заданной строки, где все узлы с одним дочерним элементом объединены с родителями.
Защиту взяты из: Словаря алгоритмов и структур данных
обычно Trie используется для индексных слов из словаря (лексикон) или любого набора строк примера D = {ABCD, abcdd, bxcdf, ....., ZZZZ}
суффикс дерево используется для индекса текста, используя ту же структуру данных «TRIE» на все суффиксы нашего текста Т = abcdabcg всех суффиксов Т = {abcdabcg, abcdabc, abcdab, abcda, ABCD, abc, ab, a}
теперь это похоже на группы строк. мы строим Trie над этими группами строк (все суффиксы T).
Конструкция обеих структур данных линейна, она принимает O (n) во времени и пространстве.
в случае dicionary (набор строк): n = сумма символов всех слов. в тексте: n = длина текста.
массив суффикса: представляет собой технику для представления дерева суффикса в сжатом sapce, это массив всех начальных позиций суффиксов строки.
он медленнее, чем дерево суффиксов во время поиска.
для получения дополнительной информации перейдите по ссылке в Википедии, есть хорошая статья, посвященная этой теме.
Лучшая производительность для каких операций? –