Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
Если текст представляет собой набор случайных постоянно... 14.09.05 12:40 Число просмотров: 3358
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 14.09.05 12:42 Количество правок: 1
|
> Есть много строк и надо структуру данных, которая позволила
> бы эффективно искать подстроку сказу во всех этих строках и
> получать список вхождений (точнее только номера исходных
> строк, смещение не надо).
Если текст представляет собой набор случайных постоянно меняющихся символов, то придется полным перебором.
Мне тут пришла в голову прикольная мысль. Предлагаю построить табличку по всему набору исходных строк таким образом - перебрать все пары рядомстоЯщих байт. Из них сформировать ключ путем умножения второго байта на 256 и добавления первого. Местоположение этой пары в тексте (строка, позиция) приписать к этому ключу. В худшем случае получим 64к ключей и в четыре раза больше байт координат, чем байт текста. При поиске вычисляем ключ по первым байтам искомого фрагмента и обходим только координаты тех фрагментов, которые начинаются с этой пары байт. Скорость поиска возрастет примерно в 64к раз при нормальном распределении.
А что, настолько большой набор огромных строк и тормознутый процессор, что простой поиск занимает много времени?
> Помню что была такая классная штука, называлась чтото вроде
> сжатого дерева с суффиксными ссылками, но вот никак не могу
> найти его описания. Кто знает эту структуру или может дать
> ссылку на описание - пожалуйста в студию.
Не слышал о такой.
|
|
<theory>
|
Need help по структурам данных 14.09.05 00:55
Автор: KUV Статус: Незарегистрированный пользователь
|
Есть много строк и надо структуру данных, которая позволила бы эффективно искать подстроку сказу во всех этих строках и получать список вхождений (точнее только номера исходных строк, смещение не надо).
Помню что была такая классная штука, называлась чтото вроде сжатого дерева с суффиксными ссылками, но вот никак не могу найти его описания. Кто знает эту структуру или может дать ссылку на описание - пожалуйста в студию.
|
| |
сеньк 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 байт длиной.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
