информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Атака на InternetВсе любят мед
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Линуксовый ботнет, распространяющийся... 
 Конец поддержки Internet Explorer 
 Рекордное число уязвимостей в 2021 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Need help по структурам данных 14.09.05 00:55  
Автор: KUV Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Есть много строк и надо структуру данных, которая позволила бы эффективно искать подстроку сказу во всех этих строках и получать список вхождений (точнее только номера исходных строк, смещение не надо).
Помню что была такая классная штука, называлась чтото вроде сжатого дерева с суффиксными ссылками, но вот никак не могу найти его описания. Кто знает эту структуру или может дать ссылку на описание - пожалуйста в студию.
суффиксное дерево 14.09.05 15:47  
Автор: paganoid Статус: Member
<"чистая" ссылка>


http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/
сеньк 14.09.05 23:48  
Автор: KUV Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Если текст представляет собой набор случайных постоянно... 14.09.05 12:40  
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 14.09.05 12:42  Количество правок: 1
<"чистая" ссылка>
> Есть много строк и надо структуру данных, которая позволила
> бы эффективно искать подстроку сказу во всех этих строках и
> получать список вхождений (точнее только номера исходных
> строк, смещение не надо).

Если текст представляет собой набор случайных постоянно меняющихся символов, то придется полным перебором.
Мне тут пришла в голову прикольная мысль. Предлагаю построить табличку по всему набору исходных строк таким образом - перебрать все пары рядомстоЯщих байт. Из них сформировать ключ путем умножения второго байта на 256 и добавления первого. Местоположение этой пары в тексте (строка, позиция) приписать к этому ключу. В худшем случае получим 64к ключей и в четыре раза больше байт координат, чем байт текста. При поиске вычисляем ключ по первым байтам искомого фрагмента и обходим только координаты тех фрагментов, которые начинаются с этой пары байт. Скорость поиска возрастет примерно в 64к раз при нормальном распределении.

А что, настолько большой набор огромных строк и тормознутый процессор, что простой поиск занимает много времени?

> Помню что была такая классная штука, называлась чтото вроде
> сжатого дерева с суффиксными ссылками, но вот никак не могу
> найти его описания. Кто знает эту структуру или может дать
> ссылку на описание - пожалуйста в студию.

Не слышал о такой.
Ну, допустим эдак миллиона 3 строк, каждая по 100-200 байт... 14.09.05 23:47  
Автор: KUV Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> А что, настолько большой набор огромных строк и тормознутый
> процессор, что простой поиск занимает много времени?

Ну, допустим эдак миллиона 3 строк, каждая по 100-200 байт длиной.
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2022 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach