Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 20
спасибо за статью! Доходчиво и реально интересно.
Подскажите пожалуйста, в ходе подготовки статьи — Вам не попадались примеры реализации поиска по регулярному выражению на суффиксном дереве?
Подскажите пожалуйста, в ходе подготовки статьи — Вам не попадались примеры реализации поиска по регулярному выражению на суффиксном дереве?
Спасибо за комментарий. Вы имеете ввиду возможность предварительно построить по тексту суффиксное дерево и затем искать по регулярному выражению не по всей строке, а только в «нужных» ветках дерева, я верно понял? Звучит интересно, но я такого не встречал и сходу не знаю насколько это реализуемо.
поиска по регулярному выражению
Конечные автоматы намного лучше справляются с этой задачей.
Конечно, вы правы. Но здесь задача, как я понимаю, может быть поставлена так: дана довольно длинная строка, в которой периодически ищут по регулярным выражениям какие-то недлинные подстроки. Вместо того, чтобы каждый раз делать проход по всей строке, возможно, может получиться с помощью суффиксного дерева обрабатывать только те части строки, где возможно вхождение регулярного выражения — таких частей может оказаться немного; глупый пример: если первый символ регвыра — буква а, то смотрим только подстроки, начинающиеся с а (фактически, поддерево под символом а). Хотя я понимаю, что это довольно узкая задача.
Да, примерно так. Строка — это индекс пары сотен тысяч сайтов, буквы — это морфологические нормы, в регулярке — классы символов — это принадлежность нормы определенной тематике, определенному классу, в общем вхождение в какое либо множество. Плюс различные дополнительные условия — расстояние между совпадениями, отсутствие определенных символов между совпадениями и все такое.
Мне кажется (возможно ошибаюсь) дерево все таки интереснее традиционных способов. Правда параллельно думаю над графом. Тоже выглядит заманчиво.
Мне кажется (возможно ошибаюсь) дерево все таки интереснее традиционных способов. Правда параллельно думаю над графом. Тоже выглядит заманчиво.
Мне кажется, что вам будет интересно почитать статью Regular Expression Matching with a Trigram Index or How Google Code Search Worked.
В качестве примера использования, я использовал суффиксное дерево для поиска дубликатов картинок в хранилище на миллионы картинок. Алгоритм очень простой: беру картинку, считаю хэш, хэш в дерево. Если в дереве уже есть, то дубликат (на всякий случай еще побайтовое сравнение если хэш совпал).
Хорошая экономия памяти (по сравнению с линейным хранением хэшей), высокая скорость работы и все дубликаты за один проход.
Хорошая экономия памяти (по сравнению с линейным хранением хэшей), высокая скорость работы и все дубликаты за один проход.
а зачем для этого дерево? это же линейное key:value.
Линейное key-value на миллионах объектах сожрет памяти в сотни или тысячи раз больше.
Рекомендую посмотреть на bloom filter.
А какой длины хэш? Он в строковом виде хранится?
если я Вас правильно понял, то Ваша реализация ближе к вертикальному шардингу чем к суффиксному дереву. Вы группировали хэши, разбив их на токены, верно? Это действительно снижает затраты на хранение и поиск, но это не суффиксное дерево. Извините, если неправильно понял.
Вы, наверно, имеете ввиду префиксное дерево? Суффиксное тут совершенно лишнее.
о, вот как оно называется! Спасибо.
В научной литературе популярны названия бор (Trie), словарь (dictionary). Термин «префиксное дерево», кажется, встречается реже.
В этой статье суффиксное дерево. А это существенно более сложная штука.
В этой статье суффиксное дерево. А это существенно более сложная штука.
да разницу между префиксным и суффиксным я вижу. Я Ogoun-у пытался объяснить, что то, что он сделал — это не суффиксное. А бор и словарь настолько затерли, что, на мой взгляд префиксное — более четкий термин, мне лично понятно о чем речь. Бором называют любое перевернутое дерево, а словарем что только не называют — и множества и кортежи, там надо в контекст вникать, что бы понять о чем речь.
Я вскользь просмотрел алгоритм, но похоже у него есть еще один недостаток по сравнению с Укконеном — он оффлайновый, т.е. ему надо знать строку заранее в то время как в Укконене мы можем за амортизированное O(1) добавить символ к концу строки и обновить дерево.
К слову, я бы не сказал, что сам Укконен очень сложный, поначалу в нем сложно разобраться, но если понимать, как он работает, написать его не очень сложно и уйдет не очень много строк кода. Моя реализация лежит вот тут например: e-maxx.ru/algo/ukkonen (в самом низу).
К слову, я бы не сказал, что сам Укконен очень сложный, поначалу в нем сложно разобраться, но если понимать, как он работает, написать его не очень сложно и уйдет не очень много строк кода. Моя реализация лежит вот тут например: e-maxx.ru/algo/ukkonen (в самом низу).
Не совсем так. Он онлайновый, но не слева направо, а справа налево. Большинство онлайновых задач, решаемых Укконеном, (но не все) могут быть решены с помощью упрощённого Вейнера на перевёрнутой строке и, наоборот, есть онлайновые задачи, которые могут быть решены онлайново Вейнером на перевёрнутой строке, но непонятно как их решать Укконеном.
Я видел ваш код. Впечатляет, конечно, как вы его удавили, но он объективно ужасен. Приемлемые короткие реализации Укконена — это что-то типа вот этого. Но код там всё равно больше, а главное в коде больше ветвлений (а значит он сложнее для понимания).
Я видел ваш код. Впечатляет, конечно, как вы его удавили, но он объективно ужасен. Приемлемые короткие реализации Укконена — это что-то типа вот этого. Но код там всё равно больше, а главное в коде больше ветвлений (а значит он сложнее для понимания).
Начал читать статью, сразу попал в место, которое хотел бы уточнить.
Так понимаю, для абсолютно любой строки длины N, минимальное количество вершин в суффиксном дереве всегда будет равно N+1. Где все вершины кроме корня являются листьями с соответствующим суффиксом.
Но сразу же после этого определения приводится картинка дерева, где количество вершин явно больше минимального, т.к. есть еще узловые вершины. Где-то не точность: в определении, в иллюстрирующей картинке или в моем понимании.
Суффиксное дерево для строки s – это минимальное по числу вершин дерево, каждое ребро которого помечено непустой подстрокой s таким образом, что каждый суффикс s[i..n-1] может быть прочитан на пути из корня до какого-нибудь листа и, наоборот, каждая строка, прочитанная на пути из корня до какого-нибудь листа, является суффиксом s.
Так понимаю, для абсолютно любой строки длины N, минимальное количество вершин в суффиксном дереве всегда будет равно N+1. Где все вершины кроме корня являются листьями с соответствующим суффиксом.
Но сразу же после этого определения приводится картинка дерева, где количество вершин явно больше минимального, т.к. есть еще узловые вершины. Где-то не точность: в определении, в иллюстрирующей картинке или в моем понимании.
Если вы рассматриваете строку, в которой последний символ отличается от всех остальных символов (как в примере), то для строки длины N количество вершин в суффиксном дереве всегда будет больше N (корень + по листу на каждый суффикс). Но, естественно, вершин может быть больше, чем N+1. Тем не менее, количество вершин всегда не больше 2N+1. Чтобы в этом убедиться достаточно последовательно вставлять в дерево каждый суффикс: когда вы вставляете суффикс появляется одна или две вершины (лист + вершина, к которой этот лист крепится, если её ещё нет).
В случае произвольной строки ситуация несколько иная: вершин также не больше 2N+1, но может быть и меньше, чем N (например, для строки aaaaaaaaaaa суффиксное дерево содержит всего две вершины).
В тексте я неявно опирался на тот факт, что в дереве с n листьями, в котором у каждой нелистовой вершины есть как минимум два потомка, всегда O(n) вершин. Я не учёл, что это, вообще-то, не очень очевидно.
Надеюсь я смог ответить на ваш вопрос.
В случае произвольной строки ситуация несколько иная: вершин также не больше 2N+1, но может быть и меньше, чем N (например, для строки aaaaaaaaaaa суффиксное дерево содержит всего две вершины).
В тексте я неявно опирался на тот факт, что в дереве с n листьями, в котором у каждой нелистовой вершины есть как минимум два потомка, всегда O(n) вершин. Я не учёл, что это, вообще-то, не очень очевидно.
Надеюсь я смог ответить на ваш вопрос.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Простое суффиксное дерево